洛谷 P3374 是一道树状数组模板题题面长得非常朴素给定一个序列支持两种操作一是把某个位置的值加上一个数二是查询某个区间的和。正因为它足够简单几乎所有学数据结构的人都会从这里入手树状数组。我当年第一次提交的时候觉得代码不过十几行应该闭着眼睛就能过结果连续踩了好几个下标和类型的坑才把这道题真正吃透。今天就把我对这道题的理解、AC 模板、以及一些排查经验一起说一下给正在刷模板题的读者一个可以直接参考的版本。1. 先拆题面P3374 到底让你干什么1.1 单点修改与区间查询题目给的原始序列长度为 n之后有 m 次操作。操作分为两类1 x k把第 x 个元素加上 k2 x y查询第 x 个元素到第 y 个元素的和这类操作组合在一起有一个固定的叫法单点修改、区间求和。它是最经典的“动态前缀和”问题。如果只是静态查询预处理一遍前缀和数组就够了但问题在于第 1 种操作会修改数组修改之后所有受影响的前缀和都要跟着改这就不能再用静态前缀和硬撑了。我见过不少初学者第一反应是维护一个a数组和一个prefix数组每次修改a[x]后把prefix[x..n]全部更新一遍。这个思路在 n 很小的时候没问题但 P3374 的数据范围是 n 和 m 都能到 500000 级别的。如果每次修改都重算前缀和最坏情况基本就是平方复杂度测试点一大直接超时。1.2 暴力做法的真实开销假设 n500000m500000每次操作要么查询、要么修改。就算所有操作都是修改每次重算前缀和是 O(n)总共就是 2500 亿次加法这个数量级在普通 OJ 上完全跑不动。即便你优化到只重算从 x 到 n 的部分最坏也还是 O(nm)。那为什么不用线段树线段树当然能解决这个问题区间求和和单点修改都是 O(log n)。但线段树的常数比树状数组大代码量也更多。对于 P3374 这种“只需要单点加、区间求和”的模板题树状数组是更轻量、更贴合题意的选择。这也是题目名字里直接写着“树状数组”的原因。1.3 为什么这道题最适合树状数组树状数组的英文名是 Binary Indexed Tree也有叫 Fenwick Tree 的。它的核心优势是一次更新、一次查询都只需要 O(log n) 的时间。和线段树相比它的代码量小得多内存也省线段树通常要开 4 倍空间而树状数组只需要和原数组一样长的数组。当然树状数组不是万能的它适合处理“前缀信息可以合并”的问题。求和是最典型的场景因为sum(1..r) - sum(1..l-1)可以直接得到区间和。P3374 恰好就是这个模型所以它成了树状数组最好的入门载体。2. 树状数组为什么快lowbit、管辖区间与二进制的配合2.1 lowbit树状数组的“定位器”树状数组基于一个非常关键的位运算函数int lowbit(int x) { return x -x; }lowbit(x)的返回值是 x 的二进制表示中最低位的 1 所对应的值。比如lowbit(6)6 的二进制是110最低位的 1 在第二位对应的值是 2所以lowbit(6) 2。再比如lowbit(8)8 的二进制是1000最低位的 1 在第四位对应的值是 8所以lowbit(8) 8。为什么x -x能算出这个值因为在计算机中负数是以补码形式存储的-x等于把 x 按位取反再加 1。这个操作会让 x 最低位的 1 保留下来同时让所有更高的位变成反码再按位与之后只有最低位的 1 以及它后面的 0 会被保留。这个细节一开始不理解没关系记住结论就行。lowbit 是树状数组一切操作的基础。更新时靠它向上跳查询时靠它向下合并区间。2.2 c[i] 的管辖范围一张表看懂树状数组不直接存原始数组而是用一个辅助数组c。c[i]存的是原始数组 a 中某个区间的和具体区间是[i - lowbit(i) 1, i]这句话是树状数组最重要的一句话。比如ilowbit(i)c[i] 负责的区间11a[1]22a[1] 到 a[2]31a[3]44a[1] 到 a[4]51a[5]62a[5] 到 a[6]71a[7]88a[1] 到 a[8]你会发现负责区间越长i 的 lowbit 值越大。这个规律不是巧合而是二进制和区间划分天然结合的结果。树状数组并没有真正建出一棵“树”它是把这种树形结构压缩进了数组下标里。2.3 查询和更新为什么都只走 O(log n)因为更新一个位置 a[pos] 时不需要把所有前缀和都改一遍只需要改所有“管辖范围包含 pos”的 c[i]。这些节点的下标规律是从 pos 开始不断执行i lowbit(i)。比如修改 a[3]需要更新c[3]、c[4]、c[8]因为这三者都包含了 a[3]。更新的路径是 3 - 4 - 8。最多跳 O(log n) 次因为每次 lowbit 的值至少翻倍下标增长很快。查询前缀和sum(1..x)时只需要把 x 不断的i - lowbit(i)累加沿途的 c[i]。比如查询前 7 个数的和路径是 7 - 6 - 4对应累加c[7]、c[6]、c[4]。这个路径最多也是 O(log n) 次。所以不管是修改还是查询树状数组都只需要 O(log n) 的时间。两个操作都很快整体复杂度从暴力的 O(nm) 降到了 O((nm)log n)在这个数据规模下是完全能过的。3. 核心操作实现add、sum 和区间求和的完整推导3.1 add 的更新路线单点修改对应这个函数void add(int pos, long long val) { for (int i pos; i n; i lowbit(i)) { c[i] val; } }它做的事情是把所有管辖范围包含 pos 的 c[i] 都加上 val。因为树状数组不直接记录原始数组 a所以每次修改都要靠这个上跳过程把影响扩散到所有需要变更的区间节点。这里容易犯的一个错是给 add 传的 pos 必须是 1 到 n 之间的有效下标。如果题目给出的位置是 1 开始的那就直接用如果题目是 0 开始就需要在调用处加 1。P3374 的序列下标默认从 1 开始所以直接传 x 就行。3.2 sum 的累加路线前缀和查询对应这个函数long long sumPrefix(int pos) { long long res 0; for (int i pos; i 0; i - lowbit(i)) { res c[i]; } return res; }它返回的是 a[1] 到 a[pos] 的和。循环条件是i 0不是i 0因为 lowbit 不断减下去i 不可能等于 0 之后还有意义如果把 0写成 0在 i 变成 0 的时候还会进入循环然后0 - lowbit(0)会出问题。幸好 lowbit(0) 是 0如果遇到这种代码很可能会死循环。3.3 区间和为什么要写 sum(y) - sum(x-1)有了前缀和区间和就很简单了。要求 a[l] 到 a[r] 的和可以写成long long rangeSum(int l, int r) { return sumPrefix(r) - sumPrefix(l - 1); }我见过有的初学者会尝试单独写一个“从 l 到 r 的累加”的循环比如从 r 开始往回走只累加与区间有关的部分。这个想法没有错但在树状数组里没有必要因为前缀和已经足够表达区间和直接做一次减法最清晰也最不容易写错。为什么不是sumPrefix(r) - sumPrefix(l)因为前缀和sumPrefix(t)的含义是前 t 个元素的总和。前 r 个的和减去前 l 个的和剩下的其实是a[l1]到a[r]把a[l]漏掉了。所以必须减l-1这在写题的时候特别容易忽略。4. 可以直接粘贴的 AC 模板与关键选型说明4.1 模板代码下面这段代码针对 P3374 可以 AC我把它写成比较保守的版本便于理解#include bits/stdc.h using namespace std; const int MAXN 500005; int n, m; long long c[MAXN]; int lowbit(int x) { return x -x; } void add(int pos, long long val) { for (int i pos; i n; i lowbit(i)) { c[i] val; } } long long sumPrefix(int pos) { long long res 0; for (int i pos; i 0; i - lowbit(i)) { res c[i]; } return res; } long long rangeSum(int l, int r) { return sumPrefix(r) - sumPrefix(l - 1); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n m; for (int i 1; i n; i) { long long a; cin a; add(i, a); } while (m--) { int op; cin op; if (op 1) { int x; long long k; cin x k; add(x, k); } else { int l, r; cin l r; if (l r) swap(l, r); cout rangeSum(l, r) \n; } } return 0; }核心就三个函数lowbit、add、sumPrefix。理解了这三个函数整道题就崩不了。很多人在学树状数组时喜欢背代码我不建议只背一定要在草稿纸上用一个小数组手动模拟一遍 3 和 4 的更新轨迹才能真正记住。4.2 模板背后的几个选型理由先说MAXNP3374 的 n 最大到 500000所以开 500005 就够。有人喜欢开1000005求稳这个看个人习惯但数组开太大浪费不多主要是心理踏实。我自己一般取上限加 5避免边界溢出。再说long long虽然原始数组和单次增加的数看起来可能在 int 范围内但区间求和是累加结果最坏情况下多个大数据叠加之后很容易超过 int 范围。所以c数组和返回类型都用long long这个习惯在数据范围较大的题目里非常重要。最后是ios::sync_with_stdio(false); cin.tie(nullptr);。这段代码能明显提高 cin/cout 的输入输出速度。P3374 的 m 是 500000 级别不用输入加速也能过但用了更稳也不会在极端数据下因为 IO 拖后腿。5. 我提交 P3374 时踩过的几个坑5.1 下标从 1 开始这件事比想象中重要我第一次写树状数组时习惯性地从 0 开始遍历数组结果 add 和 sum 全都乱了。树状数组的下标本身就依赖 lowbit 的二进制性质从 1 开始才能真正表达“最低位 1”的含义。如果硬要从 0 开始每次传入位置都要先加 1非常容易忘记。所以在读入初始序列时我直接用for (int i 1; i n; i) { long long a; cin a; add(i, a); }不要用 0 到 n-1 的循环再费力转换为 1 到 n。5.2 查询参数 l 和 r 的顺序模板题输入通常保证 l r但偶尔会遇到数据不按套路出牌的情况。我在写模板时习惯加上一行if (l r) swap(l, r);这句不影响复杂度还能让代码更健壮。如果以后遇到类似题目时输入没有保证也不会直接 WA。5.3 读入操作类型时别和下标混淆题目里操作编号是 1 或 2操作 1 的参数是x k操作 2 的参数是x y。我见过有人把操作编号直接当成修改值使用或把op和x的顺序看反。这种错误特别隐蔽因为编译不会报错运行也能过样例但数据一多就错。我的建议是先明确下面这个状态op 为 1单点加调用 add(x, k)op 为 2区间查询调用 rangeSum(l, r)千万不要在 op 为 1 的时候去调用 sumPrefix否则答案就全乱了。5.4 输出别用 endl很多人在调试时喜欢用endl换行但它除了换行还会强制刷新缓冲区输出量大的时候性能差别很明显。在 OJ 上提交时我习惯用\n换行这个习惯在 P3374 这种 m 很大的题里能省下不少时间。如果你使用 printf/scanf 风格那输出就用printf(%lld\n, ans)。不要混用 iostream 和 stdio 的同步输出否则可能会出现输出顺序错乱。关闭同步后混用更危险尽量避免。6. 模板题只是入口树状数组的常见进阶方向6.1 差分思想把区间修改变成单点修改树状数组不仅支持单点修改、区间求和配合差分数组还能做区间修改、单点查询。做法是对原数组 a 求差分数组 d令d[i] a[i] - a[i-1]那么 a[x] 就是 d[1..x] 的前缀和。区间修改 a[l..r] 加上 k等价于d[l] k和d[r1] - k这就是两次单点修改。这种变形在很多题里都能见到。P3374 本身虽然不考这个但理解差分之后树状数组的适用范围会一下子宽很多。6.2 离散化加树状数组求逆序对经典逆序对问题可以用归并排序也可以用树状数组。做法是先把数值离散化然后从右往左扫描数组每扫到一个 x就查询已经出现过的、比 x 小的数字个数累加到答案再把 x 插入树状数组。这个过程是在动态维护一个“出现次数”的计数数组利用树状数组的 O(log n) 前缀和实现。一开始会觉得这和区间求和没关系但树状数组的本质就是维护可合并的前缀信息计数也是一种求和只是把“加值”换成了“加 1”。6.3 树状数组上的二分与第 k 小如果树状数组维护的是权值出现次数还可以在树状数组上做二分快速找到第 k 小的数。原理是利用 c[i] 的管辖区间从高位到低位逼近答案。这个技巧在一些平衡树替代题里经常出现被称为“树状数组上倍增”。我自己的体会是不要把 P3374 当成一道刷完就忘的模板题。低bit 的思想、前缀和转换差分的思想、以及在树状数组上对值域做统计的思想后面会反复出现。先把这道题吃透后面很多题目都会顺很多。最后分享一个调试小技巧如果区间求和结果不对不要急着看代码逻辑先输出sumPrefix(l)和sumPrefix(r)看看是前缀和的问题还是区间转换的问题。只要这两个前缀和单独检查是对的那sum(r) - sum(l-1)基本不会错。做树状数组题最怕的就是只盯着代码看不往数据里走。