前缀和算法，这个名字听起来像是大学《数据结构》里随手翻过的一页，但实际上，它是区间查询类问题里复用率最高的基础技巧之一。不管是刷 LeetCode、打蓝桥杯、写 ACM，还是工作中处理一段连续数据的聚合统计，我都会先想一想能不能用前缀和。它的核心思想特别简单：把大量重复的区间求和，提前预处理成一个累计数组，然后用两次下标访问代替一整段循环。但前缀和也有一个明显的短板——怕修改。数组一更新，后续的累计值就全得重算。这篇文章我想顺着这个痛点往下聊，从一维前缀和的原理说起，引入二维前缀和、差分，再重点拆解一个能动态维护前缀和的进阶方案：树状数组。尤其是当你维护一个长度为 n = 16 的序列时，查询 sum(11) 和单点修改 add(3, x) 到底是怎么运作的，二进制在里面扮演了什么角色，我会一步一步推给你看。
适宜人群：刚学完基础语法的初学者、准备算法面试的求职者，以及希望把“知其然”升级成“知其所以然”的竞赛选手。这篇内容不会停留在背模板的层面，我会把公式背后的拆解逻辑、更新路径、常踩的坑全部摊开讲。
1. 前缀和的本质：用预处理空间换查询时间
1.1 一维前缀和：累计数组的诞生
先从一个最常见的场景说起。假设你有一个数组 a，长度为 n，比如 n = 16，那么 a[1] 到 a[16] 就是原始数据。现在有人连续问你一百个问题：“第 3 个元素到第 11 个元素的和是多少？”最直白的做法是每次从下标 3 加到下标 11，循环 9 次。一百个问题就是 900 次加法，看起来也不多，但当 n 变成 100000、问题数量变成 100000 次的时候，复杂度就是 O(n * m)，在算法竞赛里基本就是超时警告。
前缀和的做法是：提前维护一个新数组 s，让 s[i] = a[1] + a[2] + ... + a[i]。也就是说，s[i] 表示“从开头到第 i 个位置”的累计和。这个数组的构建只要一次遍历：s[i] = s[i - 1] + a[i]。构建完成之后，想求 a[l] 到 a[r] 的和，一句公式就能解决：sum(l, r) = s[r] - s[l - 1]。
为什么能这样减？因为 s[r] 包含了 a[1] 到 a[r] 的全部元素，s[l - 1] 包含了 a[1] 到 a[l - 1] 的全部元素，两者相减，恰好把前 l - 1 个元素“抵消”掉，剩下的一定就是 a[l] 到 a[r] 这一段。这个过程只做了一次减法，时间复杂度 O(1)。
这里有一个初学者特别容易犯迷糊的点：前缀和数组到底从下标 0 开始还是从 1 开始？我个人强烈建议，只要不是处理那种强制下标从 0 的题目，一律从 1 开始。原因很简单：s[0] 天然等于 0，这样求 a[1] 到 a[r] 的和就是 s[r] - s[0]，不用特判边界，代码清爽很多。如果从 0 开始，那么求 a[0] 到 a[r] 的区间和就要处理 s[-1]，需要额外写条件判断，非常别扭。
1.2 二维前缀和：容斥原理的经典应用
一维会了，二维其实也只是换了个维度。现在是二维矩阵 a，问你左上角 (x1, y1) 到右下角 (x2, y2) 的子矩阵和是多少。如果不用前缀和，每次暴力遍历子矩阵里的每个元素，复杂度很容易爆掉。二维前缀和的思路是同样的：先构建一个 s[i][j]，表示从 (1, 1) 到 (i, j) 这个矩形内所有元素的和。
构建公式要费一点脑子：s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j]。为什么减一次 s[i - 1][j - 1]？因为 s[i - 1][j] 和 s[i][j - 1] 都包含了左上角 (1,1) 到 (i - 1, j - 1) 那块公共区域，加了两遍，所以需要减掉一次。这就是容斥原理在数组上的直白体现。
查询子矩阵和的公式对称地写成：sum = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]。同样是一次 O(1) 的操作。二维前缀和非常适合处理图像模糊、区域统计、棋盘类问题，比如让你求一个区域里的黑色像素总数，或者统计矩阵内某个数字出现的次数，基本都能用这个结构轻松撑住。
1.3 前缀和的局限：一改就崩
但是，我必须把前缀和的软肋说透。前缀和天然是“静态”的。你构建 s 数组之后，如果原始数组的某个值 a[k] 被修改成了新值，那么 s[k]、s[k + 1]、一直到 s[n] 全部要跟着变。因为在定义上，s[i] 依赖前 i 个元素的总和，一个元素变了，后面所有前缀和都失效了。这意味着在“单点修改 + 区间查询”混合出现的动态场景里，朴素前缀和的每次修改复杂度是 O(n)，和查询的 O(1) 相比，一快一慢，整体依然可能超时。
也许你会想：那我干脆不用前缀和，每次查询直接暴力不就好了？查询 O(r - l + 1)，修改 O(1)。当查询多、修改少的时候可以接受，但如果查询和修改都是 10 万次级别，两种做法都可能拉垮。这时候就需要一个更聪明的结构，既能快速维护修改带来的影响，又能快速回答前缀和查询——树状数组就是为解决这个矛盾而生的。
2. 树状数组：动态前缀和的入门钥匙
2.1 为什么需要 lowbit：二进制视角下的区间划分
树状数组，英文叫 Fenwick Tree，或者 Binary Indexed Tree，中文有时候也叫二叉索引树。我第一次看到“树状数组”这个名字时还以为是拿指针建一棵树，后来发现它只是用了一个普通数组 c[]，然后通过下标的二进制特征来组织区间信息，根本不用建树。
这里必须先把 lowbit 这个概念讲明白。lowbit(x) 表示 x 的二进制表达中，最低位的 1 所对应的数值。比如 x = 6，二进制是 110，最低位的 1 在第二位，对应数值是 2，所以 lowbit(6) = 2。计算方式一句话：lowbit(x) = x & (-x)。为什么可以这样算？因为在补码表示下，一个数取负，相当于把所有位按位取反再加一，这会导致原来的最低位 1 保持不变，而它右边的所有位全部变成 0，左边则是取反后的值。拿 6 举例：6 的二进制 0110，-6 的补码 1010，两者按位与，得到 0010，正好是 2。
树状数组的关键设计是：c[i] 负责维护一个区间，区间的左端点是 i - lowbit(i) + 1，右端点是 i。换句话说，c[i] 存储的是 a[i - lowbit(i) + 1] 到 a[i] 这一段连续元素的和。举个例子，c[8] 对应的区间是 [8 - 8 + 1, 8]，也就是 [1, 8]；c[6] 对应的区间是 [6 - 2 + 1, 6]，也就是 [5, 6]；c[7] 对应的是 [7, 7]。这样划分的目的，就是让每个区间长度都是 2 的某次幂，而且区间之间呈现出一种类似二进制的拼接关系，下面会看到这个性质有多巧妙。
2.2 树状数组的存储姿态：c[] 与原始数组 a[] 的关系
现在明确一下定义。假设下标从 1 开始，原始数组长度为 n = 16。那么树状数组 c 也开 16 个位置（我通常直接开 n + 2，怕边界问题）。c[i] 的取值不是单独的 a[i]，而是一段区间和。按 lowbit 划分的话：
- c[1] = a[1]，因为 lowbit(1) = 1，区间 [1, 1]
- c[2] = a[1] + a[2]，因为 lowbit(2) = 2，区间 [1, 2]
- c[3] = a[3]，因为 lowbit(3) = 1，区间 [3, 3]
- c[4] = a[1] + a[2] + a[3] + a[4]，因为 lowbit(4) = 4，区间 [1, 4]
- 一直到 c[16] = a[1] + ... + a[16]，因为 lowbit(16) = 16，区间 [1, 16]
如果你把每个 i 对应的 lowbit 值列出来，会看到它和 i 的二进制里最低位 1 的位置严格对应。这种组织方式很反直觉：c 的下标不是一层层堆上去的父子关系，而是通过“当前下标取 lowbit 后加减”来从一个区间跳到另一个区间。理解了这个跳跃规则，树状数组的两个核心操作就都通了。
3. 核心操作逐步推演：以 n = 16 的 sum(11) 与 add(3, x) 为例
3.1 单点修改 add(3, x) 的完整传播路径
假设我们对原始序列做一次单点修改：a[3] 增加了 x。现在需要保证树状数组仍然保持正确，也就是说，所有包含 a[3] 的 c[i] 都要同步增加 x。
哪些 c[i] 包含 a[3]？刚才说了，c[i] 负责的区间是左端点 i - lowbit(i) + 1 到右端点 i。包含 a[3] 的条件就是左端点 <= 3 且右端点 >= 3。一个一个看太慢，树状数组给了一条固定规则：从 i = 3 开始，先更新 c[3]，然后 i += lowbit(i)，重复直到 i > n。具体推演如下：
- 起点 i = 3，lowbit(3) = 1，所以更新 c[3]，然后 i = 3 + 1 = 4
- 此时 i = 4，lowbit(4) = 4，更新 c[4]，然后 i = 4 + 4 = 8
- 此时 i = 8，lowbit(8) = 8，更新 c[8]，然后 i = 8 + 8 = 16
- 此时 i = 16，lowbit(16) = 16，更新 c[16]，然后 i = 16 + 16 = 32，超出 n = 16，停止
所以在 n = 16 的序列中，add(3, x) 实际需要修改四个位置：c[3]、c[4]、c[8]、c[16]。你可能会问，为什么跳过了 c[5]、c[6]、c[7]？因为根据区间定义，c[5] 只负责 a[5]，c[6] 负责 a[5] 到 a[6]，c[7] 只负责 a[7]，它们都不包含 a[3]；而 c[4] 负责 [1,4]，c[8] 负责 [1,8]，c[16] 负责 [1,16]，所以必须更新。这就是 lowbit 加法的语义：从一个点出发，沿着“包含当前区间的更大区间”逐步向上爬，直到覆盖整个序列。
这个过程的时间复杂度是多少？每次 i 至少翻出原 lowbit 翻倍大小的块，最坏情况下要跳 log(n) 步，而 n = 16 只有 4 步，n 很大时是 O(log n)。这就是树状数组修改高效的原因。
3.2 前缀和查询 sum(11) 的二进制拆分
查询前缀和 sum(11)，也就是求 a[1] + a[2] + ... + a[11]。树状数组不能直接给出这个结果，但我们可以用 c 数组快速拼接出来，规则是：从 i = 11 开始，累加 c[i]，然后 i -= lowbit(i)，直到 i = 0。展开来就是：
- 起点 i = 11，lowbit(11) = 1（因为 11 的二进制是 1011，最低位 1 对应数值 1），所以累加 c[11]，i = 11 - 1 = 10
- 此时 i = 10，lowbit(10) = 2（1010 的最低位 1 对应 2），累加 c[10]，i = 10 - 2 = 8
- 此时 i = 8，lowbit(8) = 8，累加 c[8]，i = 8 - 8 = 0
- i = 0，终止
因此 sum(11) = c[11] + c[10] + c[8]。验证一下：c[11] 对应区间 [11, 11]，只含 a[11]；c[10] 对应区间 [9, 10]，含 a[9]、a[10]；c[8] 对应区间 [1, 8]，含 a[1] 到 a[8]。三块拼起来恰好覆盖 [1, 11]，没有重叠也没有遗漏。这就是树状数组查询看起来“跳跃”但结果完整的秘密。
换个角度看，11 的二进制是 1011，可以拆成 8 + 2 + 1 三部分，而这三部分正好对应了 8、2、1 三个区间长度。树状数组之所以能以 O(log n) 查询前缀和，本质上就是在做二进制的分段求和。这一点想通之后，你会觉得它比线段树还“性感”。
3.3 区间和怎么通过前缀和互相转换
有了 sum 函数，任意区间 [l, r] 的和就非常简单：sum(r) - sum(l - 1)。比如求 a[4] 到 a[11] 的和，就是 sum(11) - sum(3)。sum(3) 查询过程为：累加 c[3]，i = 2；累加 c[2]，i = 0；所以 sum(3) = c[3] + c[2]，也就是 a[3] + (a[1] + a[2])，合起来是 a[1] + a[2] + a[3]。因此区间 [4, 11] 的和就是 (c[11] + c[10] + c[8]) - (c[3] + c[2])。不要觉得这里绕，分段求和正是树状数组能代替原来 O(n) 暴力的底层依赖。
在实际写代码时，只要 sum 和 add 两个函数都正确，区间查询就是一行调用。这也是为什么我觉得树状数组是很多动态区间题里最顺手的数据结构：它不像线段树需要维护标记下传、合并左右子树、递归建树，它就只有两个循环，代码量少，常数也小。
4. 完整实现与实战对照
4.1 C++ 实现：从建树到查询的完整代码
接口设计上，我习惯把 n 声明成全局变量，然后写一个 add 和一个 sum。这里给一份可以直接用的实现，适用于“单点修改 + 区间查询”的经典问题。
#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; int n, q; long long c[MAXN]; // 树状数组本体 inline int lowbit(int x) { return x & (-x); } // 单点修改：a[pos] += value void add(int pos, long long value) { while (pos <= n) { c[pos] += value; pos += lowbit(pos); } } // 前缀和查询：返回 a[1] + ... + a[pos] long long sum(int pos) { long long res = 0; while (pos > 0) { res += c[pos]; pos -= lowbit(pos); } return res; } int main() { scanf("%d %d", &n, &q); // 初始建树 for (int i = 1; i <= n; i++) { long long x; scanf("%lld", &x); add(i, x); } while (q--) { int op, l, r; scanf("%d %d %d", &op, &l, &r); if (op == 1) { // 单点修改 add(l, r); } else { // 区间查询 printf("%lld\n", sum(r) - sum(l - 1)); } } return 0; }这段代码的建树方式是最容易理解的：直接用 add(i, x) 逐个把 a[i] 插进去。复杂度是 O(n log n)，对于大多数题目足够了。如果你追求极致性能，可以用线性建树：先读入原数组 a，再算出前缀和 s[]，然后 c[i] = s[i] - s[i - lowbit(i)]。因为 c[i] 存储的本来就是区间 [i - lowbit(i) + 1, i] 的和，所以用前缀和直接构造是 O(n) 的。这个优化我一般在 n 非常大、操作次数非常多的时候用，平时差别不大。
4.2 与朴素前缀和、线段树的复杂度对比
每次提到树状数组，就有人问：那我直接用朴素前缀和行不行？什么情况下必须上树状数组？这里我列一张对比表，方便你按需选取。
| 数据结构 | 构建复杂度 | 单点修改 | 区间查询 | 适用场景 |
|---|---|---|---|---|
| 朴素前缀和 | O(n) | O(n) | O(1) | 一建多查，几乎不修改 |
| 差分数组 | O(n) | O(1)（区间端点修改） | O(n)（单点查询 O(1)） | 多次区间加，最后统一查询 |
| 树状数组 | O(n log n) 或 O(n) | O(log n) | O(log n) | 动态修改 + 区间求和 |
| 线段树 | O(n) | O(log n) | O(log n) | 动态修改 + 区间求和、最值、其他复杂标记 |
从这个表能看出一个清晰的取舍：如果你的数据是“固定不变”的，朴素前缀和就是最优解，查询 O(1)，无敌；如果你只需要前缀进行“区间加”但最终只是单点查询，差分数组更好；只有当你确实需要“改一个点，马上查一段区间的和”，并且这种操作会反复出现时，树状数组才真正发光。
相比线段树，树状数组能做的事情要局限一些：它天然只能维护满足“可减性”的信息，例如和、积、异或和，不能直接维护最大值、最小值这类不支持减法的信息。但优点是代码短、速度快，在没有复杂标记需求的时候，我通常优先选择它，特别是在算法竞赛和面试手撕代码场景里，写线段树出错概率会高一些。
4.3 经典问题模板：动态数组区间和
几乎每本算法书都会用一道题介绍树状数组——洛谷 P3374。题意很简单：给你一个长度为 n 的序列，接下来有 m 次操作，操作分两种：把某个位置的数加上 k，或者查询某个区间内所有数的和。这就是树状数组的标准场景。用上面的模板代码，核心逻辑不到二十行。
我在刷题时会把这类题抽象成三步走：第一步，读完 n 和初始序列，建好树状数组；第二步，逐条处理操作指令，遇到修改就调 add，遇到查询就调 sum；第三步，输出结果。看起来简单，但真正决定你能否 AC 的往往是一些细节：题目可能要求你开 long long，因为前缀和累加很容易超过 int 范围；数组要开 n + 2 而不是 n，防止 while 循环里访问越界；读入优化要加，否则数据量大时 scanf 也吃力。
我还想提醒一个容易被忽略的进阶玩法：当遇到“区间修改 + 区间查询”的时候，很多人以为树状数组就无能为力了，其实可以用差分思想，维护两个树状数组，一个存差分数组 d[i]，另一个存 i * d[i]，最后利用公式 sum = (r + 1) * sum(d, r) - sum(i * d, r) 减去对应的左边界部分。这个技巧我实际用过好几次，效果不比线段树差，代码量却小一截。
5. 常见问题与排查技巧实录
5.1 下标从 0 开始的灾难
我最早学树状数组时，下标从 0 开始，写出来的查询函数经常死循环。后来彻底改成从 1 开始，问题立刻消失。原因是 lowbit 操作在处理 0 的时候没有意义——i = 0 时，lowbit(0) = 0，查询就是死循环。如果你遇到的是原始数据下标从 0 给的题目，不要去改树状数组的结构，直接在读入时把下标整体加 1，让内部逻辑全部基于 1 索引，这样最简单。
5.2 lowbit 计算错误与更新方向混乱
lowbit 的写法有很多种，有人写 x & -x，有人写 x & (~x + 1)，还有人写 x - (x & (x - 1))，结果都等价。但我见过不少人把查询循环和更新循环写反，或者把 i += lowbit(i) 写成 i -= lowbit(i)。判断标准只有一个：add 是要向上传播修改，所以 i 应该变大；sum 是要向下拆分前缀和，所以 i 应该变小。你可以把 c 数组当成一块块盖在原始数组上的“盖子”，修改时要把消息传给所有盖住它的更大的盖子，查询时要把当前前缀拆成几段互不重叠的盖子。
5.3 整型溢出与边界判断
前缀和的累加值很容易超过 int 范围，特别是当 a[i] 的值本身很大、n 是 10 的 5 次方时。我在写树状数组时，c 数组、sum 返回值、add 的 value 参数全部用 long long。还有一个容易翻车的点：add 循环里条件是 pos <= n，如果写成 pos < n，就会漏掉最后一个元素；如果 pos 本身就是 n，而 lowbit(n) 不是 1，那么更新循环会先更新 c[n]，然后跳到 n + lowbit(n)，这一步不会越界写入，因为条件已经检查过了。所以数组长度开 n + 1 是安全的，开大一点到 n + 5 也无妨。
5.4 调试技巧：暴力对照与输出中间过程
树状数组最难的地方在于，你很难直接肉眼看出来 c 数组哪里有错。所以我的习惯是：写完代码第一件事，生成小数据（比如 n = 16），用暴力法算出预期结果，再用树状数组跑一遍，对比输出。如果发现错误，就在 add 和 sum 里加几行打印，输出每一步的 i 和当前累加值。比如 add(3, x) 打印“更新 i = 3, 4, 8, 16”，sum(11) 打印“累加 i = 11, 10, 8”，然后和手推对比。这个操作我称之为“人工模拟树状数组”，虽然笨，但很有效。
5.5 离线离散化：当值域很大时怎么办
有些题不是直接给数组让你维护，而是需要你统计“某个值出现过几次”并支持后续查询，比如求逆序对。此时你需要的不是原始下标的树状数组，而是按值域建立的树状数组。如果值域太大，比如 1e9，那就必须先做离散化：把所有出现的数值收集起来，排序去重，然后把每个元素映射成 1 到 m 的小整数，再在映射后的下标上建树状数组。这里的难度在于你要确保离散化后的大小关系不变，排序去重后 index 越小，原值越小。
我在做逆序对的时候就是这么用的：从后往前扫描原数组，每遇到一个数 a[i]，先查到它在离散化数组中的排名 pos，然后 sum(pos - 1) 统计出后面有多少个比它小的元素，累加到答案，然后 add(pos, 1)。整个过程 O(n log n)，比归并排序的写法直观不少。
5.6 面试官偏爱的问题：为什么 lowbit 能做到 O(log n)
如果你在面试里手写树状数组，面试官大概率会追问一句：为什么 update 的循环次数是 log n 而不是 n？这里的核心在于 lowbit 的性质：每次 i += lowbit(i)，i 的最低位的 1 会至少向左移动一位，或者让更高位进位，但绝不会原地踏步。换一种说法，每跳一次，i 的二进制表示中从最低位数起的 0 的数量会增加，所以最多跳 O(log n) 次就会超出范围。哪怕达不到 n，也一定在 log 级别内结束。
为了加深理解，你可以拿 n = 16 举例，直接观察 add(1, x) 的路径：1 -> 2 -> 4 -> 8 -> 16，一共 4 步。add(7, x) 的路径是 7 -> 8 -> 16，3 步。最坏情况是 add(15, x)：15 -> 16，2 步。从这些例子里能感受到，跳的步数和二进制分段数是同一个量级，也就是 O(log n)。把这个逻辑讲清楚，面试官通常就会放过你了。
6. 一些值得收藏的进阶扩展
树状数组能做的并不只是简单的“单点改、区间查”。在实际工程和竞赛里，我还常用它处理：
- 求第 k 小/第 k 大：在值域树状数组上做二分，每次二分 mid，sum(mid) 看是否达到 k，复杂度 O(log^2 n)，配合倍增可以优化到 O(log n)；
- 区间异或和：把相加改成异或，树状数组依然成立，因为异或也有可减性（自反性）；
- 二维树状数组：把一维树状数组嵌套到第二维，支持二维单点修改和子矩阵查询，复杂度 O(log^2 n)，代码量也不算大；
- 配合差分的进阶形态：前面提到的双树技巧，解决区间修改 + 区间查询，是树状数组里最有性价比的玩法。
很多人以为树状数组只是个“简化版线段树”，但我觉得它更本质的魅力在于，让你重新理解了“前缀和”这种思想在不同动态维护场景下的变形。它不是静态前缀和谐的替代品，而是一种延续。
我个人在实际操作中感受最深的一点是：永远不要在不理解 lowbit 拆分逻辑的时候硬背模板。花二十分钟，自己拿 n = 16 的数组手动推一遍 sum(11) 和 add(3, x)，比背十遍代码都管用。数据结构这种东西，一旦你从“为什么它要这么跳”的层面想通了，写代码就只剩肌肉记忆了，排查 bug 也会快很多。最后再分享一个小技巧：遇到区间求和 + 单点修改的题，先问自己一句“数据是静态的吗”，如果不是，别犹豫，直接把树状数组模板写好，它大概率是整份代码里最让你省心的那部分。
