树状数组
01 / 一句话本质
一个 1-indexed 数组,每格保存「以本格为右端、长度为 2 的某次幂」的区间和 ——这个长度就是下标的最低位 1。 点更新沿着隐式的树向上走(加上最低位),前缀和沿着向下走(减去最低位)。 都是 O(log N),十行代码,完全不必分配一棵树。
题目前缀和 + 单点修改输入[3,2,-1,6,5,4,-3,3]修改arr[5] += 10查询[2,7]
长度为 8 的 1 索引数组。树状数组 bit[i] 存储以 i 结尾、长度为 lowbit(i) 的区间和。
步
0 / 22
阶段
构造
实时
—
0 / 22
02 / 模式骨架
# 1-indexed,长度 Ndef lowbit(i): return i & -i# 点更新:arr[i] += deltadef update(i, delta):while i ≤ N:bit[i] += deltai += lowbit(i)# arr[1..i] 的前缀和def prefix(i):s ← 0while i > 0:s += bit[i]; i −= lowbit(i)return s# 区间和 [l..r] = prefix(r) − prefix(l − 1)
03 / 什么时候用这个模式
"区间和 + 点更新"
经典用例。和线段树解决同一类问题,但树状数组更短、常数更小、内存只占一半。只要聚合是「求和」或其他容易求逆的运算,优先用树状数组。
"逆序对 / 比当前小的数 / 坐标离散化"
扫一遍数组,把取值做离散化压到小范围里,维护一个频率树状数组。 每个新元素加入前做一次「之前已经看到的范围里有多少」的前缀计数。 LC 315、493、327 都是同一套配方。
"区间更新 + 点查询"
在差分数组上做 BIT。
update(l, +δ)、 update(r+1, −δ),然后 prefix(i) 就是当前位置的值。 单点查询的场景下可以替代带懒标记的线段树。"二维 BIT 求子矩形和"
两层 while 循环嵌套(每层一个维度)就得到 O(log² N) 的「可变网格上子矩形求和」。LC 308。
04 / 常见坑
i.
0-indexed 与 1-indexed 搞混。
BIT 天生是 1-indexed 的 —— 下标 0 没有
lowbit(循环不再前进), 它正好充当前缀查询的递归终止符。把 0 当成合法下标会让两个方向的 while 同时坏掉。 请开 bit[0..N],所有访问从 1 开始。ii.
该用 BIT 时却伸手去拿线段树。
BIT 适合任何可求逆的聚合(求和、XOR、计数)。min / max / gcd 这些不可求逆 —— 没办法「减回去」 —— 所以必须用线段树。该用更轻的工具时,别默认上重武器。
iii.
忘了用差分技巧支持区间更新。
朴素 BIT 只支持点更新 + 区间查询。常见错误是为了支持区间更新而把整个 BIT 重建。 正解是在差分数组上建 BIT:
update(l, +δ); update(r+1, −δ), 然后 prefix(i) 就是 i 处的值。每次调用两次范围更新,总共 O(log N)。05 / 去 LeetCode 上练习
四道题,按难度排序。这里有意不放解答。