motivation · 前缀和

引子：前缀和把区间和压成一次减法

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

约定 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]$ 恰好剩下。拖动下面的 l / r，实时观察这两段「前缀」相减。

1 · 查询 O(1) 固然高效，代价藏在「修改」里

前缀和是把答案预先固定了。一旦改动某个 $a[i]$ ，所有「包含了 i 的前缀」—— 也就是 $pre[i+1], pre[i+2], \dots , pre[n]$ ——全都需随之重算，这是 $O(n)$ 。点击下面的「改值」，即可看到这片被波及的前缀：

复杂度小结：前缀和 = 查询 O(1) / 修改 O(n) / 预处理 O(n)。对「建好后基本不变、只需查询」的静态数据（离线统计、二维前缀和算子矩形和、图像积分图）非常合适。可一旦数据边查边改，这个 $O(n)$ 的修改便成了瓶颈—— 树状数组正是用来把「修改」也降到 $O(\log n)$ 的结构。

2 · 实际应用

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