motivation · 前缀和

前缀和与一次减法

问题：给一个数组 a，反复问「 $a[l] + a[l+1] + \dots + a[r]$ 是多少」。每次都实时把这段加一遍是 $O(n)$ ，问一万次便是一万次扫描。最简单的提速：先花 $O(n)$ 预处理出一个前缀和数组，之后每次查询只要一次减法。

1 · 两个前缀之差

约定 $pre[0] = 0$ ， $pre[k] = a[0] + a[1] + \dots + a[k-1]$ ，即前 $k$ 个的和。于是任意区间和 $sum(l, r) = pre[r+1] - pre[l]$ ：长一段的前缀减去短一段的前缀，中间 $a[l..r]$ 恰好剩下。

警示 · 这一步用到了减法，前提是聚合落在可逆的结构上（阿贝尔群）。区间和、区间异或都满足，前缀积只在元素非零时才谈得上（用除法还原，数组含 0 即整段失效，另有溢出与精度问题），而区间最值、区间 gcd 根本没有逆元，前缀技巧对它们完全不适用——那类聚合要么上线段树，要么在静态数据上用稀疏表（要求聚合幂等）。

图 1-1 · 区间和作为两段前缀之差。可拖动

l

与

r

，观察被减去的短前缀与保留下来的区间。

2 · 修改的代价

前缀和是把答案预先固定了。一旦改动某个 $a[i]$ ，所有包含 $i$ 的前缀（即 $pre[i+1], pre[i+2], \dots, pre[n]$ ）都要随之重算，这是 $O(n)$ 。

图 2-1 · 单点改值波及的前缀范围。可改任一位置的值，观察从该位置起的整段前缀被标红重算。

建议 · 前缀和的三项代价是查询 $O(1)$ 、修改 $O(n)$ 、预处理 $O(n)$ 。对建好后基本不变、只需查询的静态数据（离线统计、二维矩形和、图像积分图）尤其合适。一旦数据边查边改， $O(n)$ 的修改就是瓶颈，树状数组正是把修改也降到 $O(\log n)$ 的结构。

3 · 实际应用

二维前缀和 / 积分图（summed-area table） [1]： $O(1)$ 求任意矩形区域和，OpenCV 的 cv::integral() 即是它，也是 box blur 与 Haar 特征（Viola-Jones 人脸检测 [2]）的基石。 报表 / BI：某时间段 GMV、累计活跃用户这类「区间求和」，预计算前缀后查询恒为一次减法。 差分数组是它的逆运算：对「区间整体加、最后才查」的离线场景（如批量调价、日程占用统计），先在差分上 $O(1)$ 打两个标记，最后一次前缀和还原。 各类前缀统计：前缀异或、前缀计数同样把区间问题变成两个端点之差；前缀积则要换成两个端点之商，且只在元素非零时可用。

4 · 参考文献

Crow, F. C. (1984). Summed-area tables for texture mapping. ACM SIGGRAPH Computer Graphics, 18(3), 207–212.
Viola, P., & Jones, M. (2001). Rapid object detection using a boosted cascade of simple features. In Proceedings of CVPR 2001, 1, I-511–I-518.