树状数组
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 / 常见坑
0-indexed 与 1-indexed 搞混。
BIT 天生是 1-indexed 的 —— 下标 0 没有
lowbit(循环不再前进), 它正好充当前缀查询的递归终止符。把 0 当成合法下标会让两个方向的 while 同时坏掉。 请开 bit[0..N],所有访问从 1 开始。该用 BIT 时却伸手去拿线段树。
BIT 适合任何可求逆的聚合(求和、XOR、计数)。min / max / gcd 这些不可求逆 —— 没办法「减回去」 —— 所以必须用线段树。该用更轻的工具时,别默认上重武器。
忘了用差分技巧支持区间更新。
朴素 BIT 只支持点更新 + 区间查询。常见错误是为了支持区间更新而把整个 BIT 重建。 正解是在差分数组上建 BIT:
update(l, +δ); update(r+1, −δ), 然后 prefix(i) 就是 i 处的值。每次调用两次范围更新,总共 O(log N)。05 / 去 LeetCode 上练习
简单3
中等9
01Longest Increasing Subsequence— LC 300→02Range Sum Query 2D - Immutable— LC 304→03Range Sum Query - Mutable— LC 307→04Number of Longest Increasing Subsequence— LC 673→05Corporate Flight Bookings— LC 1109→06Matrix Block Sum— LC 1314→07Count Number of Teams— LC 1395→08Count Subarrays With More Ones Than Zeros— LC 2031→09Shifting Letters II— LC 2381→
困难12
01The Skyline Problem— LC 218→02Sliding Window Maximum— LC 239→03Range Sum Query 2D - Mutable— LC 308→04Count of Smaller Numbers After Self— LC 315→05Count of Range Sum— LC 327→06Russian Doll Envelopes— LC 354→07Reverse Pairs— LC 493→08Create Sorted Array through Instructions— LC 1649→09Minimum Number of Removals to Make Mountain Array— LC 1671→10Count Good Triplets in an Array— LC 2179→11Longest Increasing Subsequence II— LC 2407→12Count the Number of K-Big Indices— LC 2519→