第 39 章 树状数组¶
树状数组是区间数据结构里性价比最高的一个：几十行代码，常数极小， 支持单点改 + 区间查、区间改 + 单点查、区间改 + 区间查三种形态。
本章最重要的一条判断，请先记住：
在 Python 里，树状数组的常数比线段树小 5–10 倍。 能用树状数组解决的问题，绝对不要写线段树。
它的代价写在最后一节：信息必须可减。求和、异或可以，最值不行——那是 线段树 的地盘。选型决策表（哪种情况该用哪种结构）在 数据结构目录页。
1 从前缀和说起¶
静态区间和用前缀和就够了，\(O(n)\) 预处理、\(O(1)\) 查询：
from itertools import accumulate
pre = [0] + list(accumulate(a)) # C 层循环
s = pre[r + 1] - pre[l] # a[l..r] 的和
但前缀和不支持修改：改一个 \(a_i\)，后面所有 pre 都要重算，是 \(O(n)\)。
| 需求 | 工具 | 单次复杂度 |
|---|---|---|
| 静态区间和 | 前缀和 | \(O(1)\) |
| 静态区间加、最后统一查 | 差分数组 | \(O(1)\) |
| 静态区间最值 | ST 表 | \(O(1)\)（预处理 \(O(n\log n)\)） |
| 动态：单点改 + 区间和 | 树状数组 | \(O(\log n)\) |
| 动态：区间改 + 区间和 | 双树状数组 | \(O(\log n)\) |
| 动态：区间改 + 区间最值 / 复杂信息 | 线段树 | \(O(\log n)\) |
| 动态：奇奇怪怪的操作 | 分块 | \(O(\sqrt n)\) |
选型顺序永远是：前缀和 → 树状数组 → 分块 → 线段树。 越往后常数越大，代码越长，出错概率越高。
2 树状数组：lowbit 树¶
lowbit¶
「lowbit」即最低位，是整型二进制表示中最后一个 1 的位置。 获得 lowbit 的方法是
x & -x。因为负数存的是补码，而补码是反码加 1。x末尾的 0 变成 1，lowbit 上的 1 变成 0，然后加 1，末尾的 0 进位后在 lowbit 上填 1， 而 lowbit 之前的位置x和-x恰好相反。
Python 特别提醒：Python 的整数是无限位宽的补码，
x & -x同样成立， 而且不会有 C++ 里int/long long位宽不同的问题。见 运算符与位运算。
结构¶
树状数组 t[i] 管辖区间 \((i - \text{lowbit}(i),\ i]\)，长度恰好是 \(\text{lowbit}(i)\)。
一个形象的说法：没必要真的把树建出来，直接在原序列上做。 两条移动路线：
| 路线 | 走法 | 用途 |
|---|---|---|
| 向前（减 lowbit） | i -= i & -i |
查询前缀和 |
| 向后（加 lowbit） | i += i & -i |
更新祖先 |
每条路线最多走 \(\lfloor \log n \rfloor + 1\) 步。精确结论是：
树状数组：区间操作最多访问 \(2(\lfloor \log n \rfloor + 1)\) 个节点。 线段树：区间操作最多访问 \(4\lceil \log n \rceil\) 个节点。
同样是 \(O(\log n)\)，树状数组的节点访问数只有线段树的一半， 而且每个节点只做一次加法（线段树要做 push down、区间判断、递归调用）。 这就是「常数小 5–10 倍」的来源。
3 模板：三种形态¶
形态一：单点修改 + 区间和查询¶
最基础的形态。
class BIT:
"""树状数组：单点加、前缀和查询。下标 1..n。
单次操作 O(log n)，常数极小（每步只有一次加法和一次 lowbit）。
兼容 Python 3.9。
"""
__slots__ = ("n", "t") # 固定属性表：省掉实例字典，取属性更快
def __init__(self, n):
self.n = n
self.t = [0] * (n + 1) # 下标从 1 用起；t[0] 空置，lowbit 公式才成立
def add(self, i, v):
"""a[i] += v，O(log n)。"""
t, n = self.t, self.n # 提成局部变量，循环里省去每次的属性查找
while i <= n: # 超过 n 就没有祖先要更新了
t[i] += v
i += i & -i # 向后：跳到下一个把 i 包含在内的更大区间
return
def pre(self, i):
"""返回 a[1] + ... + a[i]，O(log n)。"""
t = self.t
s = 0
while i > 0: # 走到 0 表示前缀已被完整切分完毕
s += t[i] # t[i] 覆盖 (i-lowbit(i), i]，各段互不重叠
i -= i & -i # 向前：剥掉最低位的 1，跳到左邻那一段
return s
def query(self, l, r):
"""返回 a[l] + ... + a[r]，O(log n)。"""
return self.pre(r) - self.pre(l - 1) # 靠相减取区间，故信息必须可减（见 39.6）
def build(self, a):
"""从数组 a（1-indexed，a[0] 忽略）O(n) 建树。
比逐个 add 的 O(n log n) 快，n 大时值得用。
"""
t = self.t
n = self.n
for i in range(1, n + 1):
t[i] += a[i] # 顺序遍历，走到 i 时 t[i] 已收齐全部子段
j = i + (i & -i) # i 的父亲：唯一一个把 t[i] 整段包住的节点
if j <= n:
t[j] += t[i] # 整段一次性并给父亲，每个节点只被访问一次
\(O(n)\) 建树：先把
t[i] = a[i]，再把每个t[i]累加到父亲t[i + lowbit(i)]。 一趟循环就完成，比 \(n\) 次add快 \(\log n\) 倍。
形态二：区间修改 + 单点查询（差分）¶
在差分数组上建树状数组：\(d_i = a_i - a_{i-1}\)，则 \(a_i = \sum_{j \le i} d_j\)。
class BITDiff(BIT):
"""区间加 + 单点查询。在差分数组上做树状数组。"""
def range_add(self, l, r, v):
"""a[l..r] 全部 += v，O(log n)。"""
self.add(l, v) # 差分数组从 l 起整体抬高 v
self.add(r + 1, -v) # r+1 处抵消，抬高只保留在 [l, r]
# r = n 时这里访问 n+1，数组必须开到 n+1
def point(self, i):
"""返回 a[i]，O(log n)。"""
return self.pre(i) # 差分的前缀和就是原值，无需再减
开数组要开到 \(n+1\)，否则
add(r + 1, -v)在 \(r = n\) 时会越界（或被静默丢弃导致 WA）。
形态三：区间修改 + 区间和查询（双树状数组）¶
现在有个尴尬的地方：树状数组可以支持区间查询或者区间修改，但两者不能兼得。 需要一点小技巧，树状数组也可以同时支持两种操作……相当于使用了两个树状数组。
推导：设 \(d\) 是差分数组，则
所以维护两个树状数组：\(B_1\) 存 \(d_j\)，\(B_2\) 存 \((j-1) d_j\)。
class BITRange:
"""区间加 + 区间和查询。双树状数组，O(log n)。
这是 Python 里做「区间改 + 区间查」的**首选**：
常数远小于线段树，代码只有 30 行。
"""
__slots__ = ("n", "t1", "t2")
def __init__(self, n):
self.n = n + 1 # 多留一格给 r+1
self.t1 = [0] * (self.n + 1) # 第一棵树：存差分 d[j]
self.t2 = [0] * (self.n + 1) # 第二棵树：存加权差分 (j-1) * d[j]
def _add(self, t, i, v):
n = self.n
while i <= n:
t[i] += v
i += i & -i # 与形态一同一条向后路线，只是换棵树走
def range_add(self, l, r, v):
"""a[l..r] 全部 += v，O(log n)。"""
self._add(self.t1, l, v) # d[l] += v
self._add(self.t1, r + 1, -v) # d[r+1] -= v，把影响截断在 r
self._add(self.t2, l, v * (l - 1)) # 权重取 j-1，与下面 _pre 的推导式配套
self._add(self.t2, r + 1, -v * r) # 此处 j = r+1，故权重是 (r+1)-1 = r
def _pre(self, i):
t1, t2 = self.t1, self.t2
s1 = s2 = 0
j = i
while j > 0: # 两棵树共用同一条向前路线，循环次数减半
s1 += t1[j] # s1 累加出 sum(d[1..i])
s2 += t2[j] # s2 累加出 sum((j-1) * d[j])
j -= j & -j
return s1 * i - s2 # 即 i * sum(d) - sum((j-1)*d)，见上面推导
def query(self, l, r):
"""返回 a[l] + ... + a[r]，O(log n)。"""
return self._pre(r) - self._pre(l - 1)
性能技巧：
_pre里把两个树状数组放在同一个while循环里走， 而不是调两次pre。循环次数减半，这在 \(n = 5\times10^5\) 时是几秒的差别。
三种形态对照¶
| 形态 | 修改 | 查询 | 底层存什么 |
|---|---|---|---|
| 形态一 | 单点 | 区间和 | 原数组 |
| 形态二 | 区间 | 单点 | 差分数组 |
| 形态三 | 区间 | 区间和 | 差分 + 加权差分（两棵树） |
4 树状数组上的二分（倍增）¶
树状数组还能 \(O(\log n)\) 回答「第 \(k\) 小」「前缀和首次超过 \(x\) 的位置」。
不要写「二分答案 + 每次查前缀和」——那是 \(O(\log^2 n)\)。 正确做法是在树状数组上从高位往低位倍增试探：
def kth(bit, k):
"""在计数型树状数组上找第 k 小（k 从 1 开始），O(log n)。
bit.t[i] 存的是「值为 (i-lowbit(i), i] 的元素个数」。
"""
n = bit.n
t = bit.t
pos = 0 # 循环不变量：前缀 [1, pos] 的计数恒 < 原始 k
log = n.bit_length()
for j in range(log, -1, -1): # 从高位到低位，逐位拼出答案的二进制
nxt = pos + (1 << j) # pos 是 2^(j+1) 的倍数，故 lowbit(nxt) 恰为 1<<j
if nxt <= n and t[nxt] < k: # t[nxt] 正好是 (pos, nxt] 这一整段的计数
pos = nxt # 整段跨过去，前缀计数仍不足 k
k -= t[pos] # 扣掉跨过的部分，k 变成剩余排名
return pos + 1 # 退出时 pos 是最后一个前缀计数 < k 的位置
用途：动态第 \(k\) 小、有序集合的前驱后继（集合与多重集合）、 约瑟夫问题的 \(O(n\log n)\) 解法（链表）。
\(O(\log n)\) 而不是 \(O(\log^2 n)\)，在 Python 里是「能过」和「TLE」的区别。 \(n = 10^5\) 时前者是 \(1.7\times10^6\) 次迭代，后者是 \(2.9\times10^7\) 次。
5 可减性：树状数组能做什么、不能做什么¶
树状数组靠「前缀和相减」得到区间信息，所以要求运算满足可减性（存在逆元）：
| 信息 | 可减？ | 树状数组 |
|---|---|---|
| 求和 | ✅ | ✅ |
| 异或和 | ✅（自身是逆元） | ✅ |
| 乘积（模素数） | ✅（逆元存在） | ✅ |
| 最大值 / 最小值 | ❌ | ❌ 只能维护前缀最值，不支持任意区间 |
| 最大公约数 | ❌ | ❌ |
| 区间赋值 | ❌ | ❌ |
这就是线段树不可替代的地方。
6 本章速查¶
| 要点 | 结论 |
|---|---|
| 选型第一原则 | 能用树状数组就绝不写线段树 |
| 树状数组常数 | 比线段树小 5–10 倍 |
| lowbit | x & -x |
向前 i -= i & -i |
查前缀和 |
向后 i += i & -i |
更新祖先 |
| \(O(n)\) 建树 | t[i] += a[i] 后累加到 t[i + lowbit(i)] |
| 区间改 + 单点查 | 维护差分 |
| 区间改 + 区间和 | 双树状数组（\(d_j\) 和 \((j-1)d_j\)） |
| 求第 \(k\) 小 | 倍增，\(O(\log n)\)，不是二分套查询的 \(O(\log^2 n)\) |
| 限制 | 信息必须可减（求和 ✅，最值 ❌） |
| 卡不过去时 | 先问能不能离线；再问是不是为了常数放弃了复杂度 |
| 数据规模 → Python 现实性 |
|---|
| \(n, q \le 10^5\) |
| \(n, q \le 5\times10^5\) |