prefix sum（前缀和/前缀累加和）：在数组或序列中，指从开头开始到某个位置为止的元素累计总和；常用于把区间求和等问题从“逐项相加”优化为“用两次相减快速得到结果”。（在算法与数据结构语境中最常见；有时也称 cumulative sum。）
/ˈpriːfɪks sʌm/
We can use a prefix sum to get the total quickly.
我们可以用前缀和来快速得到总和。
After building the prefix sum array, the sum from index l to r can be computed in O(1) time as pre[r] - pre[l-1].
构建前缀和数组后，从下标 l 到 r 的区间和可以用 pre[r] - pre[l-1] 在 O(1) 时间内计算出来。
prefix 来自拉丁语 *prae-*（“在前”）+ fixus（“固定的”），本义是“加在词前的成分”；sum 来自拉丁语 summa（“总量、总和”）。合起来 prefix sum 字面意思就是“前面部分的总和”，在计算机算法中被用来表示“从起点累加到当前位置的和”。
Select Language