prefix sum（前缀和）：一种常用的算法/数据处理技巧，用一个数组（或序列）的“从开头到当前位置的累计和”来快速回答区间求和等查询。
常见形式：令 P[i] = A[0] + A[1] + ... + A[i]，则区间和 A[l..r] = P[r] - P[l-1]（边界需特殊处理）。
（在部分语境中也可泛指“累计和/累积和”，但“prefix sum”通常强调“从起点开始的前缀累计”。）
/ˈpriːfɪks sʌm/
A prefix sum array can answer range-sum queries quickly.
前缀和数组可以快速回答区间求和查询。
By computing prefix sums once, we reduce each query from O(n) to O(1), which is crucial when there are many queries.
先计算一次前缀和后，我们能把每次查询从 O(n) 降到 O(1)，在查询很多时非常关键。
prefix 来自拉丁语 praefixus（意为“固定在前面/置于前面”），在英语中常指“前缀”或“位于前面的部分”；sum 源自拉丁语 summa（“总和”）。合起来 prefix sum 直译为“前缀的总和”，即“从开头到某个位置这一段（前缀）的累计和”。该术语在算法与竞赛编程中广泛使用。
Select Language