形式陈述

对序列 $a_1,\dots ,a_n$，定义

$$P_0=0,P_i=\sum _{j=1}^i{a}_j.$$

则任意区间和满足

$$\sum _{j=l}^r{a}_j=P_r-P_{l-1}.$$

构建耗时 $O(n)$，每次查询 $O(1)$。在一般可逆结合运算下，可把减法替换为群逆。

直觉

每个前缀保存从起点到当前位置的全部累计信息；一个区间正是两个前缀之间的差。

例子与边界

二维前缀和通过容斥回答矩形和。若运算只有幺半群而没有逆元，不能仅用两个前缀恢复任意区间结果。

推论与应用

它是差分、积分图、扫描线、Fenwick 树和许多离线统计的最小机制。

参考资料

• Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 4th ed. (2022), prefix computations and range sums.
• OI-Wiki contributors, OI-Wiki (2026), prefix sum and difference.