进阶 · 算法 · 前置：前缀和、二进制 · 约 18 分钟
树状数组：把前缀拆成不重叠的块
条带位置表示覆盖范围，长度表示项数，不表示和值。查询向左剥离，修改沿覆盖关系向上走。
prefix(7)：已累加 0
0/3 · 接下来取 T[7]，覆盖 7…7；然后 i 从 7 减去 lowbit=1。
滑块支持方向键及 Home / End；切换模式或输入会重置演示，不会累计修改。窄屏保持最小图宽，可横向滚动。减动画模式关闭自动播放，可逐步查看所有状态。
当前节点明细
- T[7]：覆盖 [7,7]，和值 2；下一步
- T[6]：覆盖 [5,6]，和值 2；尚未处理
- T[4]：覆盖 [1,4]，和值 6；尚未处理
同一步，对照代码
let sum = 0;
for (let i = 7; i > 0; i -= i & -i) {
sum += bit[i];
}
// 已累加 0 个块：0T[i] = sum(A[i-lowbit(i)+1…i])。当前路径：7 → 6 → 4。此演示输入限 8 个固定整数；适用条件与复杂度见下方。
看完图，带走这些结论
树状数组用 T[i] 保存一基闭区间 [i−lowbit(i)+1,i] 的和，其中 lowbit(i)=i&−i 是最低位的1代表的值。查询前 k 项时反复取 T[i] 并令 i−=lowbit(i)，把前缀拆成互不重叠的块；给 A[p] 加 Δ 时，沿 i+=lowbit(i) 更新所有包含 p 的块。
适用条件与边界
本课采用一基元素下标，查询 prefix(k) 包含1到k，prefix(0)=0。交互固定八项小整数，每轮从原数组开始，不累积上一轮修改；支持负值、负增量和零增量。条长表示覆盖项数，不表示和。通用实现需要检查下标、整数位宽与总和上界；普通求和树状数组不能直接处理任意区间最小值。
始终保持的规律
T[i]始终等于A[i−lowbit(i)+1..i]之和。查询已取块与剩余前缀互不重叠，恰好覆盖目标前缀。
逐步例子
- A=[3,−2,4,1,5,−3,2,6]。T[7]覆盖[7,7]，T[6]覆盖[5,6]，T[4]覆盖[1,4]；这三块恰好铺满前7项。
- 查询7：7(111₂)减lowbit(7)=1到6(110₂)，再减2到4(100₂)，再减4到0。得到T[7]+T[6]+T[4]=2+2+6=10。每次删除最低位的1，所以必然结束。
- 查询循环的不变量：已取的块互不相交，它们与尚未处理的[1,i]一起构成原来的[1,k]。取当前块[i−lowbit(i)+1,i]后，剩余前缀正好止于i−lowbit(i)。
- 给A[3]加3：包含位置3的块恰是T[3]、T[4]、T[8]，分别覆盖[3,3]、[1,4]、[1,8]。沿3→4→8→16，16超过n=8后停止；不改T[2]或T[6]。
- 为什么更新能跳过其他块？令s=lowbit(i)，i+s将最低位1及连续进位清零、把更高位变为1，得到包含当前块的下一个祖先块。固定p的覆盖块按这条链从p一直扩展；介于相邻祖先之间的其他块，其左端在p右侧，不包含p。
- 一基闭区间[l,r]的和是prefix(r)−prefix(l−1)。与前课零基左闭右开[l,r)对应的仍是前r项减前l项，转换下标后再套公式，不能混用。
动态操作与数值边界
一次前缀查询删除一个二进制1，一次单点增量沿更高祖先跳转，且lowbit(i+lowbit(i))>lowbit(i)，都为O(log n)时间；树数组空间O(n)。用n次单点增量建树需O(n log n)，存在O(n)建树法但本课不展开。画面为了直接展示覆盖定义逐块求和建模，最坏O(n log n)，绘图成本不计入查询本身。CSES Dynamic Range Sum Queries的n≤200000、值≤10⁹，区间和可达2×10¹⁴，C++需long long；JavaScript Number在此范围的整数加减精确，但位运算只按32位执行，不适合不加限制地推广到巨大下标。
常见误区
- 从下标0开始更新：lowbit(0)=0会使循环无法前进，本课更新下标必须≥1。
- 把点赋值当增量：把A[p]改为u，应先计算Δ=u−A[p]，更新T后同步保存A[p]=u。
- 查询与更新方向颠倒：查询减lowbit剥去末块，更新加lowbit找覆盖祖先。
- 以为负数不能用：区间和依靠加减，可有负数；但用树状数组查找第k个元素等额外技巧常要求非负频数。
- 把区间最小值照搬为两个前缀相减：min没有这样的逆运算，普通求和模板不适用。
- 把多个演示步骤当多次独立修改：一次更新只给每个覆盖节点加一次Δ；重新选择输入会回到原数组。
自测与答案
prefix(0)是多少？给第8项减2会改哪些节点？将第3项从4赋值为1，应该传入哪个Δ？
prefix(0)=0，不访问T[0]。n=8时只改T[8]，下一步16越界停止。赋值4→1的增量是−3，而不是1。
把差分存进树状数组：区间加数后，立即读取某一项
如果修改与查询交错出现，就不能每次都重新扫描整条差分数组。可以保留原数组 A，另外用一棵初始全零的树状数组保存额外增量的差分 D。下面采用一基下标，树覆盖 1…n+1；最后一格只用作取消事件的哨兵，不是新的数组元素。这是静态延伸例子，上方动画仍演示原数组的单点增加与前缀求和。
给闭区间 [a,b] 加 v，只需 add(a,v)、add(b+1,−v)。读取第 k 项时返回 A[k]+prefixD(k)。因为一个更新对 D 的前缀贡献在 k<a 时为 0，在 a≤k≤b 时为 v，在 k>b 时为 v−v=0；多个更新按加法叠加，所以查询得到到目前为止所有覆盖 k 的增量。原数组一直不变，不要又把它改一遍，否则会重复计入。
沿用 A=[3,−2,4,1,5,−3,2,6]。先给 [2,4] 加 3：在 D 的第 2 格记 +3、第 5 格记 −3。于是第 4 项为 1+3=4，第 5 项仍是 5。再给 [4,8] 减 2：第 4 格记 −2、第 9 格记 +2；第 4 项变为 1+3−2=2，第 8 项变为 6−2=4。最终数组为 [3,1,7,2,3,−5,0,4]。每次读取都只查询树状数组前缀，不必还原全数组。
关键是区分树里保存什么：普通树状数组保存 A 的分块和，prefix(k) 是前 k 项之和；这里保存的是 D 的分块和，prefixD(k) 只是第 k 项的累计增量，不是 A[1…k] 的区间和。若改用零基左闭右开 [l,r)，两次事件对应一基 add(l+1,v)、add(r+1,−v)，读取原下标 i 时是 A[i]+prefixD(i+1)。不要混用两个下标约定。
建立全零的增量树并读入原数组为 O(n) 时间、O(n) 空间；每次区间加做两次点更新，单点读取做一次前缀查询，均为 O(log n)。n=1、a=b、b=n、重复覆盖、零增量都遵循同一规则；哨兵 n+1 不参与合法位置 1…n 的读取。这里只解决区间加与单点读，不能直接用两个 prefixD 相减来回答原数组的区间和，也不是区间赋值模板。
CSES Range Update Queries 是这一操作组合的常青练习，题页没有给出发布日期；原题初值与增量均为正数，上例负数是本站的教学扩展。原题 n、q≤200000，初值与每次增量≤10⁹，保守值上界为 (q+1)×10⁹≤200001000000000，已超过 32 位有符号整数。C++ 的原值、事件、树节点与查询累加都应使用 long long；JavaScript Number 在这些整数界限内可精确加减，但更大范围须重新分析，不把安全性推广到任意输入。