2026年1月12号我把树状数组从头到尾又过了一遍。说不上是什么新东西但这一遍复盘下来我确实把不少以前半懂不懂的细节彻底理清了。树状数组在很多算法社区里也叫 Fenwick Tree表面上是个数组骨子里却是一棵用二进制索引维护前缀信息的树。前缀和、差分、逆序对、区间改查、二维偏序、第 K 大值……这些年刷过的题里树状数组出现的频率高得吓人。如果你刚开始学数据结构这篇文章可以当作一份带避坑点的学习总结如果你已经写过不少树状数组的题下面这些关于常数、初始化和进阶用法的记录应该也能帮你绕开几个我曾经踩过的坑。1. 树状数组到底是个什么东西1.1 从一个简单前缀和问题说起先看最朴素的问题有一个长度为 n 的数组 a需要支持两类操作一是修改某个位置的值二是查询 [1, x] 区间和。直接维护前缀和数组修改一次要重新算一遍复杂度 O(n)直接暴力累加查询一次要扫一遍复杂度也是 O(n)。当 n 和操作次数 q 都到 1e5 甚至 1e6 的时候这两种做法都会被时间卡死。树状数组就是为这类“单点更新 前缀查询”问题量身定做的单次修改和单次查询都能做到 O(log n)而且代码量比线段树少一截。不少初学者会把树状数组误认为“另一个前缀和数组”其实它每个位置存的不是原始值而是某个特定区间里的累加结果。比如长度为 8 的情况下树状数组的 c[6] 并不是 a[6]它保存的是 a[5] 到 a[6] 两个元素的和。这种“一个节点负责一段区间”的设计才是它能高效完成修改和查询的关键。想理解它只需要抓住一个核心工具二进制分解。1.2 二进制拆分的核心原理树状数组的奥妙在于任意一个正整数 x 都可以拆成若干个互不重叠的二进制区间而每个区间的长度正好是 2 的若干次幂。树状数组把节点 c[i] 设计成保存区间 (i - lowbit(i), i] 的和注意这里 lowbit(i) 是 i 最低位的 1 所对应的数值。举个例子i6 时 i 的二进制是 110lowbit(6)2所以 c[6] 负责 a[5] 和 a[6] 的和i4 时二进制是 100lowbit(4)4c[4] 负责 a[1] 到 a[4] 的和。查询前缀和的时候要求 sum(1..x)我们并不需要逐个加 a[1] 加到 a[x]而是按 x 的二进制表示切块。以 x6 为例642所以查询 1..6 的和可以拆成 c[6] 加 c[4]也就是 [5,6] 和 [1,4] 两个区间求和。代码里对应的操作是 x - lowbit(x)从 6 减到 4再从 4 减到 0。修改某个点 a[i] 时只需要找到哪些区间覆盖了这个点这些节点正是从 i 开始不断 i lowbit(i) 跳到的位置。你会发现修改和查询完全是相反方向的跳转一个向上传播一个向下切块这也就是整个算法的全部秘密。1.3 lowbit 为什么是 x -x很多初学者卡在 lowbit 函数的写法上为什么 lowbit(x) x -x要理解这个需要回忆负数在计算机里的补码表示。x 的相反数 -x 在补码上等于把 x 的二进制位取反再加 1结果是从 x 的最低位 1 开始向左一直到符号位都和原来的 x 相反而最低位 1 及其右边的 0 保持不变。所以 x -x 恰好只保留 x 最低位的 1其他位全部归零。比如 x6二进制 110-x 是 010按补码理解 x -x 得到 010也就是十进制 2。这个最低位 1 的意义在于它决定了当前节点管辖区间的长度和位置。查询时用 x - lowbit(x) 来把当前处理的区间切掉更新时用 x lowbit(x) 来跳到下一个需要更新的父节点。两种跳法最多发生 O(log n) 次原因很简单加 lowbit 时当前最低位 1 的位置至少抬高一位二进制里 1 的数量逐步减少减 lowbit 时至少去掉了一个 1。建议你在纸上从 1 写到 16把每个 i 的 lowbit 算一遍再对应画出 c[i] 覆盖的区间这个过程做完之后再看代码会通透很多。2. 树状数组标准模板和常见变形2.1 单点修改、区间查询的标准范式最常用的树状数组代码也是网上流传最广的那一版通常长下面这样。我加了注释重点看循环条件。#include vector using namespace std; class Fenwick { public: int n; vectorlong long tree; Fenwick(int n) : n(n), tree(n 1) {} int lowbit(int x) { return x -x; } void add(int idx, long long delta) { while (idx n) { tree[idx] delta; idx lowbit(idx); } } long long prefixSum(int idx) { long long res 0; while (idx 0) { res tree[idx]; idx - lowbit(idx); } return res; } long long rangeSum(int l, int r) { return prefixSum(r) - prefixSum(l - 1); } };这里有一个关键点add(idx, delta) 是增量修改不是赋值修改。如果题目说“把位置 idx 的值改成 v”那你得先知道这个位置现在的值是多少再算出 delta v - old然后执行 add(idx, delta)。另一个关键点下标必须从 1 开始。如果你代码里的业务数组是 0 下标习惯那么在调用 add 和 rangeSum 之前要把所有下标整体加 1。这个问题看起来小实际上树状数组最常见的错误就是下标问题后面我会单独列一节来说。Fenwick fw(n); for (int i 1; i n; i) fw.add(i, a[i]); int q; cin q; while (q--) { int op, l, r; cin op l r; if (op 1) { fw.add(l, r); // 位置 l 增加 r } else { cout fw.rangeSum(l, r) \n; } }这套模板复杂度稳定在 O(log n)n 到 1e6 量级也能轻松跑起来唯一需要注意的是把求和结果用 long long 存因为区间累加极有可能超过 int 范围。2.2 差分树区间修改、单点查询如果把树状数组里存的东西从原数组换成差分数组就能处理一类新问题区间 [l, r] 统一加上一个值 k最后要查询某个位置的值是多少。差分数组 d 定义为 d[i]a[i]-a[i-1]区间加 k 等价于 d[l] 加上 kd[r1] 减去 k。查询 a[i] 只需要求 d[1] 到 d[i] 的前缀和这正好是树状数组最擅长的操作。实现起来就是在同一棵树上做两件事add(l, k) 和 add(r 1, -k)查询时直接返回 prefixSum(i)。这里有一个边界细节当 r 等于 n 时r1 等于 n1而 add 的循环条件是 idx n所以这次修改会被自动忽略这其实是合理的因为 n 后面根本没有元素需要减回来。不过为了保险我习惯把树大小开成 n2这样即使代码逻辑有偏差也不会因为越界造成不可预估的行为。Fenwick diffTree(n 1); diffTree.add(l, k); if (r 1 n) diffTree.add(r 1, -k); // 查询 a[x] long long val diffTree.prefixSum(x);用一句话概括差分树我们仍然维护树状数组但视角从“值”切换成了“变化量”。这个切换在很多区间操作题里非常常见理解了它后面双差分树和二维差分树都是同一个套路。2.3 双差分树区间修改、区间查询如果题目既要区间加又要区间求和一棵差分树就不够用了。因为单棵差分树查询只能是单点值要查询区间和需要额外维护一个辅助树。推导过程值得你亲手写一遍公式是设 d[i] 为差分数组那么 a[x] sum(d[1..x])。前缀和 S[x] sum(a[1..x])继续展开可以得到S[x] sum_{i1..x} d[i] * (x - i 1) (x 1) * sum(d[i]) - sum(i * d[i])所以我们需要两棵树一棵维护 d[i]另一棵维护 i * d[i]。区间 [l, r] 加 k 时第一棵树 add(l, k)add(r1, -k)第二棵树 add(l, l*k)add(r1, -(r1)*k)。查询 [L, R] 的区间和时用 S(R) - S(L-1) 计算即可S(x) 的公式可以封装成一个函数。Fenwick b1(n 2), b2(n 2); void rangeAdd(int l, int r, long long k) { b1.add(l, k); b1.add(r 1, -k); b2.add(l, l * k); b2.add(r 1, -(r 1) * k); } long long getPrefix(int x) { return (x 1LL) * b1.prefixSum(x) - b2.prefixSum(x); } long long rangeSum(int L, int R) { return getPrefix(R) - getPrefix(L - 1); }这个写法里最容易漏的是第二棵树上 add 的数值l * k 和 (r 1) * k 都要乘下标因为 i * d[i] 中的 i 是原始位置不能直接复用第一棵树的增量。还有乘法要记得转 long long尤其当 k 本身很大时(x 1) * prefixSum 极有可能溢出 int。2.4 离散化与逆序对统计树状数组的经典应用之一是统计逆序对。所谓逆序对就是 ij 但 a[i]a[j] 的二元组数量。如果 a 的值域很大比如 1e9不可能直接开那么大的数组所以需要先把 a 离散化把 a 中出现的所有数排序去重然后用排名作为树状数组下标排名从 1 到 m。离散化有两个注意事项一是多去重二是下标一定从 1 开始因为 add(0) 会死循环。有了排名之后从左到右扫描数组。每处理一个元素先查询当前树状数组里有多少个排名小于等于当前排名的元素用已处理的元素总数 i 减去这个数量得到的就是前面有多少个大于当前元素的数。把这些数量累加就是逆序对总数。代码思路如下vectorint nums a; sort(nums.begin(), nums.end()); nums.erase(unique(nums.begin(), nums.end()), nums.end()); Fenwick fw(nums.size()); long long ans 0; for (int i 0; i n; i) { int rk lower_bound(nums.begin(), nums.end(), a[i]) - nums.begin() 1; ans i - fw.prefixSum(rk); fw.add(rk, 1); }这里要注意 ans 一定要用 long long因为最坏情况是 n 个元素完全倒序逆序对数接近 n*(n-1)/21e5 的数据就能到 5e9。另外如果需要处理相等的元素相等的数不能算作逆序对所以这里统计的是“大于当前元素的个数”用 i - prefixSum(rk) 是安全的因为 prefixSum(rk) 包含了所有等于当前排名的元素。2.5 二维树状数组当问题扩展到二维矩阵需要支持单点修改和子矩阵求和树状数组可以很自然地变形成二维结构。核心思想是把 lowbit 跳转嵌套两层外层是行维度的跳转内层是列维度的跳转。修改 (x, y) 位置加 delta 时外层从 x 到 rowLen 加上 lowbit内层从 y 到 colLen 加上 lowbit查询前缀矩形 (x, y) 的和时也按同样的方式嵌套累加。子矩阵求和需要用容斥公式query(x2, y2) - query(x1 - 1, y2) - query(x2, y1 - 1) query(x1 - 1, y1 - 1)。这个公式和二维前缀和完全一致本质上是矩阵区域的重叠加减。代码上可以封装两个函数一个 modify一个 prefix然后区间求和用组合。long long bit[N][N]; void add2D(int x, int y, long long delta) { for (int i x; i n; i i -i) { for (int j y; j m; j j -j) { bit[i][j] delta; } } } long long sum2D(int x, int y) { long long res 0; for (int i x; i 0; i - i -i) { for (int j y; j 0; j - j -j) { res bit[i][j]; } } return res; }二维树状数组的时间复杂度是 O(log n * log m)空间 O(n*m)。它适合 n、m 都在 1000 量级的题如果矩阵特别大但稀疏就要考虑离线处理或者离散化不能硬开二维数组。还有如果遇到矩形区域加、矩形区域和查询二维双差分公式会更复杂实际题目里很少要求你写四棵树这时我会直接考虑二维线段树或者看数据范围是否允许块状结构。3. 同线段树相比什么时候选树状数组3.1 复杂度与常数对比树状数组和线段树都是 O(log n) 级别的数据结构但实际跑起来差异不小。树状数组的代码量非常少空间只要 n1 个 long long线段树即使不开动态点也要开 4n 的空间。树状数组每次操作只做位运算和几个数字的加减访问内存时也是连续的地址对 CPU 缓存非常友好。线段树递归调用本身就有函数栈开销如果写迭代版虽然快一些代码复杂度又会上升。我做过一些简单性能测试在同样规模的单点修改 区间求和题里树状数组通常比符号递归版线段树快 30% 到 50%内存占用只有四分之一左右。对比赛或者 OJ 判题来说这些差距有时候就是能不能 AC 的关键。做一个比较表格的话大概是这样方面树状数组线段树代码量很短十几行较长常需要 4 个函数空间n 1 左右4n 或更多单点修改 区间查询O(log n)O(log n)区间修改 区间查询双树实现懒标记实现任意区间最值不通用支持可处理信息可减性信息如和、异或可合并性信息范围更广常数小较大一句话总结能满足需求且信息可反向推出时优先树状数组能省下大量调试时间。3.2 线段树不可替代的场景树状数组虽然强大但它有个天然前提维护的信息必须支持“减去”因为区间查常常要做两个前缀和的差。像和、异或这类可逆运算可以用树状数组处理但区间最大值、最小值就不行。你想已知前缀最大值不能通过减法得到任意子区间最大值所以树状数组做不了通用区间最值查询。想要区间最值要么用线段树要么用稀疏表但稀疏表又不支持动态修改。另一个线段树明显占优的场景是区间整体修改后还要维护最值比如给区间每个数加 k然后查询 [l, r] 的最大值。这种问题需要懒标记树状数组从未设计懒标记这个机制强行套用会非常别扭。还有可持久化线段树、动态开点线段树以及树链剖分中维护树上路径信息线段树家族比树状数组强大得多。因此我的判断标准很直接能不能把问题化成“可减前缀信息”能就用树状数组不能就老老实实写线段树。3.3 我这几年的选型习惯复盘这些年做题的经验我的心理排序大概是这样的。看到题目先看操作类型如果是单点修改 区间求和直接写树状数组不需要犹豫如果区间修改 区间求和先想差分和双差分树代码长一点点但依然比线段树简单如果是权值统计、逆序对、偏序问题树状数组几乎是默认答案如果题目明确要查询区间最大值、最小值或者需要区间赋值我就会直接切到线段树不会再想着用树状数组硬凑。在比赛环境下编码时间非常宝贵。树状数组加离散化整套代码能控制在 30 到 50 行内而线段树随便都是 80 行起步。所以我经常跟身边的朋友说树状数组不是线段树的替代品而是线段树的第一道筛选器。能用小而美的代码解决问题就不要把复杂度堆到 4n 空间和递归栈上。这不是说线段树不好而是选型要匹配问题。4. 树状数组的进阶用法4.1 权值树状数组求第K大树状数组还可以作为“动态频次桶”来用。我们把数值本身映射成下标树状数组里存的是当前值域上每个数出现的次数。这样 prefixSum(x) 就表示值小于等于 x 的元素有多少个而“求第 K 小”就变成了找到最小的 x 使得 prefixSum(x) K。最简单的实现是在值域上二分查找每次 check 一次前缀和。// 值域 [1, maxV]k 表示第 k 小 int l 1, r maxV; while (l r) { int mid (l r) / 2; if (fw.prefixSum(mid) k) r mid; else l mid 1; } cout l \n;二分法是 O(log^2 n)通常在 n1e5 的题目里完全够用。如果想再压掉一个 log可以用树状数组的二进制倍增从高往低试探位置。这个过程看起来很像在一个森林里从根节点向下走本质上和线段树上二分是同一个思路。我一般只在 q 特别大或者时限非常紧的时候才写倍增版否则二分版更清晰、更不容易错。int kth(int k) { int res 0; for (int step 1 20; step; step 1) { if (res step n fw.tree[res step] k) { res step; k - fw.tree[res step]; } } return res 1; }倍增版本有个关键前提树状数组 tree 数组里的值是“频次和”不是原始值所以代码里比较的是 tree[nxt] k。如果直接用原始数组的某个局部加和会得到错误结果。4.2 离线处理区间内不同元素个数一个非常经典的离线题目是给出 n 个数q 个询问 [l, r]问区间内有多少个不同的值。朴素做法在每个询问里用 set 去重复杂度 O(nq)。离线思路是把所有询问按右端点 r 排序然后从左到右扫描原数组用树状数组维护“每个值最后一次出现的位置”。具体来说扫描到位置 i 时如果当前值 a[i] 曾经出现在某个更早的位置 pre那就把 pre 位置上的贡献减掉然后在当前位置 i 上加 1。这样处理后树状数组里的每个位置只保留一个 1且这个 1 一定属于该值最近一次出现的位置。于是对于右端点等于 i 的询问区间 [l, r] 内不同元素个数就等于 prefixSum(r) - prefixSum(l - 1)。整个过程只需要一轮扫描复杂度 O((nq) log n)。vectorint lastPos(maxVal 1, 0); // 每个右端点挂几个询问 vectorvectorpairint, int queryAt(n 1); for (int i 0; i q; i) { int l, r; cin l r; queryAt[r].push_back({l, i}); } vectorint ans(q); Fenwick fw(n); for (int i 1; i n; i) { if (lastPos[a[i]] ! 0) { fw.add(lastPos[a[i]], -1); } lastPos[a[i]] i; fw.add(i, 1); for (auto [l, idx] : queryAt[i]) { ans[idx] fw.rangeSum(l, i); } }这个技巧在离线数据结构里非常基础你会在很多区间颜色、区间出现次数的题里看到它的影子。关键心法就是“只在当前位置保留最新一次出现”把二维的问题压缩成一维的时间轴。4.3 二维偏序与扫描线二维偏序是树状数组另一个高频考点。典型描述是平面直角坐标系上有 n 个点 (x, y)要求统计每个点左下方有多少个点或者统计满足 xi xj 且 yi yj 的点对数量。通用的做法是把点按 x 排序然后用树状数组维护 y 这个维度上的频次。顺序扫描每一个点先查询 y 当前点 y 的点有多少个再把当前点的 y 插入树状数组。这样每个点被插入时树里已经存在的点一定是 x 排序后靠前的点因此天然满足了 x 维度的偏序条件。实现时有一个容易忽略的细节排序规则里 x 相同怎么办。如果题目要求严格 xi xj那么 x 相等时不能互相产生贡献扫描顺序就要特别注意。通常做法是排序时如果 x 相同按 y 升序排列并且在同一组 x 内先查询再统一插入而不是一个一个边查边插。否则两个 x 相等的点会被错误地统计为满足条件。sort(points.begin(), points.end(), [](auto a, auto b) { if (a.x ! b.x) return a.x b.x; return a.y b.y; }); Fenwick fw(maxY); int cnt 0; for (int i 0; i n; i) { if (i 0 || points[i].x ! points[i - 1].x) { // 这一批之前的点已经全部插入过了 } cnt fw.prefixSum(points[i].y); fw.add(points[i].y, 1); }更稳妥的方案是先统一查询当前 x 相同的整批点然后统一插入避免同 x 点之间的误算。这个技巧在 CDQ 分治前的预处理中也很常见可以说树状数组是把二维偏序“降维”成动态一维前缀和的利器。4.4 树状数组套数据结构当问题变成动态二维数点例如支持单点修改和矩阵查询点数时单棵二维树状数组可能空间不够因为矩阵很大但修改点很少。这个时候可以用树状数组套平衡树或者套线段树外层树状数组负责第一维每棵“外层次点”挂一棵平衡树管理第二维。查询时外层跳 log n 个节点每个节点内再查一次第二维总复杂度 O(log^2 n)。这套做法的优势是支持修改和动态插入缺点是代码量陡增。实际比赛里遇到动态二维数点我更倾向先考虑离线 CDQ 分治或者整体二分这两者都能用若干次一维树状数组解决问题代码更可控。树状数组套线段树更适合在线强制要求、并且第一维和第二维规模都比较适中的场景。我建议把它当作进阶知识了解真到要用的时候再按题写不要一上来就背整套重型结构那样很容易在调试里消耗大量时间。5. 常见错误与排查实录5.1 下标从0开始一错全错树状数组的索引是从 1 开始设计的lowbit(0) 0如果哪个循环里出现了传进去的下标是 0add 和 prefixSum 都会陷入死循环。拿 add 来说如果 idx 等于 0lowbit(0) 还是 0idx lowbit(idx) 永远不前进程序直接卡死。所以每当你发现一个问题“输入数据正确但程序像死循环一样超时”首先就要怀疑是不是下标没偏移。很多时候我们从 0 开始读入数组顺手就把 0 下标传给了树状数组。修复方式很简单在入口处统一偏移比如传 idx 1。我自己的习惯是在数据结构类里加一个注释写上“所有对外接口接收 1-based 下标”然后在主函数里完成转换。这样虽然每次调用多写一个 1但至少不会出现一半对一半错的情况。如果你用调试器看 tree 数组能发现某个位置的值异常大那八成就是 add 时传入过 0 或者负数下标。5.2 初始化用了暴力加卡住大数据树状数组最常见的建树写法是循环 n 次调用 add(i, a[i])这是最简单也最不容易出错的。但当 n 到百万甚至千万级别O(n log n) 的初始化会浪费不少时间卡一卡就超时。这个场景下可以用 O(n) 建树技巧。网上有一版比较经典的 O(n) 建树代码思路是先让 tree[i] 等于 a[i]然后从 i1 到 n 枚举把 tree[i] 累加到它的父节点 tree[i lowbit(i)] 上去。为什么这一步是对的因为每个节点都代表某一段区间和第一次赋值相当于每个节点只包含自己之后通过往父节点累加最终每个父节点会收集到所有子区间的值。for (int i 1; i n; i) tree[i] a[i]; for (int i 1; i n; i) { int j i (i -i); if (j n) tree[j] tree[i]; }实测下来这种初始化在做 1e6 数据的题里会比暴力 add 快很多。唯一的代价是代码语义没有那么直白所以我的建议是两种都记下来小数据用暴力加大数据用 O(n) 建树。5.3 query(r) - query(l-1) 和边界溢出区间查询最典型的手误就是写 query(r) - query(l)或者把 l-1 想当然地传成了 l。当 l1 时query(0) 应该返回 0因为树状数组的循环条件是 idx0所以 query(0) 刚好是 0。这个巧合会掩盖一部分 bug可一旦 l 不是 1结果就明显偏大。强烈建议把区间查询封装成函数统一写prefixSum(r) - prefixSum(l - 1)然后在调用处只传 l 和 r。边界溢出还常出现在差分树里。做区间加 [l, r] 时要 add(r1, -k)如果树的大小是 nr1 等于 n1add 函数里由于 idxn 不成立这次更新会被忽略逻辑上其实没问题。但如果接下来你还要查询 n1 之后的某个前缀和就可能越界。为了避免这种边界困惑最稳妥的做法是树的大小直接开 n2给 r1 留出空间所有 add 循环条件也改为 idx n 1。虽然多了一点空间换来的是更少边界心智负担。5.4 负数和离散化导致的偏移问题权值树状数组要求下标必须是正整数可原始数据里经常出现负数、零或者非常大的数。遇到负数可以先整体加一个 offset把所有值映射到 1 到 maxV 的区间遇到很大的值就离散化。这里最常见的错误是离散化后得到的排名从 0 开始然后直接传给树状数组结果 add(0) 直接死循环。所有离散化的排名最后都要加 1。还要注意相等值的处理。比如用树状数组求逆序对时如果数组里有重复元素那么相等的两个位置不构成逆序对所以查询时要用“小于等于当前值”还是“严格小于当前值”要想清楚。我的习惯是统一用 rank lower_bound(...) - nums.begin() 1然后查询 rank - 1 的数量再加当前值进树。这样可以明确避免把相等值算成逆序对。多了一个 -1 看似小细节但错了整道题都得重算。5.5 卡常经验尽量别用 vector 套 vector 存二维树二维树状数组如果用vectorvectorlong long tree来写每次访问 tree[x][y] 都会先查一次外层 vector再查内层 vector两级指针跳转让缓存命中率变得很低。当 nm1000操作次数又多时这种写法很可能因为常数太大而超时。推荐用一维扁平数组模拟二维开long long tree[(n2)*(m2)]用idx x * (m1) y来定位元素。int n, m; vectorlong long bit((n 2) * (m 2), 0); auto idx [](int x, int y) { return x * (m 2) y; }; void add(int x, int y, long long v) { for (int i x; i n; i i -i) for (int j y; j m; j j -j) bit[idx(i, j)] v; } long long sum(int x, int y) { long long res 0; for (int i x; i 0; i - i -i) for (int j y; j 0; j - j -j) res bit[idx(i, j)]; return res; }因为二维访问模式是按行优先扫描扁平数组的内存连续性明显优于嵌套 vector。我在几次二维树状数组的题目里实测过性能大约能提升 20% 以上代价只是多写一个取下标函数非常划算。6. 复盘后的经验心得6.1 先手推覆盖区间再写模板我后来养成一个习惯拿到任何树状数组题第一件事不是打开模板而是在草稿纸上写几个数字的 lowbit 和覆盖区间。比如 n8c[1] 覆盖 a[1]c[2] 覆盖 a[1..2]c[3] 覆盖 a[3]c[4] 覆盖 a[1..4]。把这些关系画出来之后很多看似诡异的跳转逻辑就变得自然了。为什么修改 i3 时要依次更新 3、4、8因为包含 a[3] 的区间节点恰好是这些。为什么查询 sum(7) 要依次加 c[7]、c[6]、c[4]因为 [1..7] 要被切成 [7,7]、[5,6]、[1,4] 三个块。这个手推过程彻底解决了我早期背模板却不知道在干什么的问题。6.2 一定要提前想清楚查询边界复盘时我发现自己过去写树状数组出错一半以上都是边界问题。要么是 l 忘记减一要么是离散化后排名没有加一要么是差分树 add(r1) 时越界。现在我会在正式编码前在注释里先写清楚每个下标的含义和取值范围。比如“idx 从 1 开始rank 从 1 开始r1 可能等于 n1”。这一点看起来不起眼但它能让我在提交前快速扫出低级错误。最后再分享一个小技巧如果你用树状数组统计逆序对或者第 K 大建议在本地写一个随机暴力程序生成小规模数据对拍一旦对不上十有八九就是下标偏移和相等值处理出了问题按这个方向排查很快就能找到罪魁祸首。