前缀和算法这个名字听起来像是大学《数据结构》里随手翻过的一页但实际上它是区间查询类问题里复用率最高的基础技巧之一。不管是刷 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 3lowbit(3) 1所以更新 c[3]然后 i 3 1 4此时 i 4lowbit(4) 4更新 c[4]然后 i 4 4 8此时 i 8lowbit(8) 8更新 c[8]然后 i 8 8 16此时 i 16lowbit(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 11lowbit(11) 1因为 11 的二进制是 1011最低位 1 对应数值 1所以累加 c[11]i 11 - 1 10此时 i 10lowbit(10) 21010 的最低位 1 对应 2累加 c[10]i 10 - 2 8此时 i 8lowbit(8) 8累加 c[8]i 8 - 8 0i 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 - 163 步。最坏情况是 add(15, x)15 - 162 步。从这些例子里能感受到跳的步数和二进制分段数是同一个量级也就是 O(log n)。把这个逻辑讲清楚面试官通常就会放过你了。6. 一些值得收藏的进阶扩展树状数组能做的并不只是简单的“单点改、区间查”。在实际工程和竞赛里我还常用它处理求第 k 小/第 k 大在值域树状数组上做二分每次二分 midsum(mid) 看是否达到 k复杂度 O(log^2 n)配合倍增可以优化到 O(log n)区间异或和把相加改成异或树状数组依然成立因为异或也有可减性自反性二维树状数组把一维树状数组嵌套到第二维支持二维单点修改和子矩阵查询复杂度 O(log^2 n)代码量也不算大配合差分的进阶形态前面提到的双树技巧解决区间修改 区间查询是树状数组里最有性价比的玩法。很多人以为树状数组只是个“简化版线段树”但我觉得它更本质的魅力在于让你重新理解了“前缀和”这种思想在不同动态维护场景下的变形。它不是静态前缀和谐的替代品而是一种延续。我个人在实际操作中感受最深的一点是永远不要在不理解 lowbit 拆分逻辑的时候硬背模板。花二十分钟自己拿 n 16 的数组手动推一遍 sum(11) 和 add(3, x)比背十遍代码都管用。数据结构这种东西一旦你从“为什么它要这么跳”的层面想通了写代码就只剩肌肉记忆了排查 bug 也会快很多。最后再分享一个小技巧遇到区间求和 单点修改的题先问自己一句“数据是静态的吗”如果不是别犹豫直接把树状数组模板写好它大概率是整份代码里最让你省心的那部分。
