7.2 线段树与树状数组：区间事务的账房
7.2 线段树与树状数组：区间事务的账房
本节摘要：前缀和查询 O(1) 但改一个数要重建全表；裸数组改 O(1) 但区间查询要逐个加。线段树把数组挂到"每个节点管一段区间"的树上，单点修改与区间查询都 O(log n)；树状数组（BIT）用 lowbit 的下标算术实现同量级的前缀和账本，代码更短但功能面窄。本节实现两者并跟踪一次区间查询的节点分解。
一个矛盾需求：改得快还要查得快
1.1 节的前缀和把区间和查询做到一次减法；可数据是活的——某个元素一改，前缀和从该位置起全数作废。反过来用裸数组，改是 O(1)，查询又是 O(n)。**"频繁单点修改 + 频繁区间查询"**这对矛盾需求，靠线性结构无解，得把区间组织成树：
- 线段树：每个节点管一段区间，叶子是单元素，父管两子之并；节点存该区间的和（或最值等）。改一个点，只有从叶到根的一条链受影响；查一个区间，恰好分解成 O(log n) 个节点，整段整段地取；
- 树状数组：线段树思想精简版，只支持前缀型的查询（区间和可由两个前缀相减得到），用 lowbit 把"我管多长"编进下标里。
线段树：区间一到四的查询分解
# 线段树：建树、单点改、区间查（数组存树，根在下标 1） class SegTree: def __init__(self, data): n = len(data) self.n = n self.t = [0] * (4 * n) # 保险容量 self.visit = [] self._build(1, 0, n - 1, data) def _build(self, node, lo, hi, data): if lo == hi: self.t[node] = data[lo] # 叶子：单元素 return mid = (lo + hi) // 2 self._build(2 * node, lo, mid, data) # 左子管前半 self._build(2 * node + 1, mid + 1, hi, data) # 右子管后半 self.t[node] = self.t[2 * node] + self.t[2 * node + 1] def update(self, node, lo, hi, pos, val): if lo == hi: self.t[node] = val # 到达叶子：改值 return mid = (lo + hi) // 2 if pos <= mid: self.update(2 * node, lo, mid, pos, val) else: self.update(2 * node + 1, mid + 1, hi, pos, val) self.t[node] = self.t[2 * node] + self.t[2 * node + 1] # 回程重算 def query(self, node, lo, hi, ql, qr): if qr < lo or hi < ql: return 0 # 不相交：空手而归 if ql <= lo and hi <= qr: self.visit.append(f"整取[{lo},{hi}]={self.t[node]}") return self.t[node] # 被查询区间完整包含：整取 mid = (lo + hi) // 2 return (self.query(2 * node, lo, mid, ql, qr) + self.query(2 * node + 1, mid + 1, hi, ql, qr)) st = SegTree([2, 1, 5, 3, 4]) print("查询 [1,4] =", st.query(1, 0, 4, 1, 4), "，命中节点：", st.visit) # 输出：查询 [1,4] = 13 ，命中节点：['整取[1,1]=1', '整取[2,2]=5', '整取[3,4]=7'] # 三个整取节点与上图一一对应 st.visit = [] st.update(1, 0, 4, 2, 10) # 下标 2 从 5 改成 10 print("改后查询 [0,2] =", st.query(1, 0, 4, 0, 2)) # 输出：改后查询 [0,2] = 13（2+1+10：只有从叶到根一条链被更新）
单点修改触动的只是"叶子到根"的一条链，长度为树高 log n；区间查询如上图分解成对数个整段。两边都是 O(log n)，矛盾需求就此了结。
树状数组：把"我管多长"写进下标
树状数组（Binary Indexed Tree，Fenwick 树）把同样的思想压进一个一维数组：下标 i 的节点管理长度为 lowbit(i) 的一段，其中 lowbit(i) = i 与它的相反数按位与，取出的正是 i 二进制最低位的 1 所代表的值。
# 树状数组：lowbit 下标算术，前缀和与单点更新都 O(log n) def lowbit(i): return i & (-i) print("下标 1 到 8 的 lowbit：", [lowbit(i) for i in range(1, 9)]) # 输出：下标 1 到 8 的 lowbit： [1, 2, 1, 4, 1, 2, 1, 8] # 1 管自己；2 管 1 到 2；3 管自己；4 管 1 到 4；8 管 1 到 8…… class BIT: def __init__(self, n): self.n = n self.t = [0] * (n + 1) # 下标从 1 开始 def add(self, i, delta): # 单点加：影响沿途所有包含 i 的节点 while i <= self.n: self.t[i] += delta i += lowbit(i) # 跳到下一个覆盖者 def prefix(self, i): # 前缀和：1..i s = 0 while i > 0: s += self.t[i] i -= lowbit(i) # 拆成若干整段之和 return s bit = BIT(5) for idx, v in enumerate([2, 1, 5, 3, 4], start=1): bit.add(idx, v) print("前缀和(4) =", bit.prefix(4), "；区间 [3,5] =", bit.prefix(5) - bit.prefix(2)) # 输出：前缀和(4) = 11 ；区间 [3,5] = 12 # 前缀(4) = 2+1+5+3 = 11；[3,5] = 5+3+4 = 12，两前缀相减而得 bit.add(3, 5) # 第 3 个数加 5 print("更新后再查 [1,3] =", bit.prefix(3)) # 输出：更新后再查 [1,3] = 13（2+1+5+5）
update 沿 lowbit 上跳、query 沿 lowbit 下拆，两条路径的长度都是二进制位数，即 O(log n)。树状数组不存"最大值"这类不可减的信息（前缀相减要求信息可逆），线段树没有这个限制——这是两者的功能分水岭。
| 结构 | 单点改 | 区间查 | 区间最值 | 空间 | 代码量 |
|---|---|---|---|---|---|
| 前缀和数组 | O(n) | O(1) | 不支持 | O(n) | 极短 |
| 裸数组 | O(1) | O(n) | O(n) | O(n) | 极短 |
| 树状数组 | O(log n) | O(log n) | 不便 | O(n) | 短 |
| 线段树 | O(log n) | O(log n) | 支持 | O(n) 系数 4 | 中等 |
⚠️ 常见坑：下标体系打架。树状数组天生 1 起（lowbit(0) = 0 会死循环），线段树数组版根在下标 1（2i 与 2i+1 的父子算术才成立）。从题目或接口拿到 0 起下标，进结构前先加一，出结果后记得还原。
💡 关键直觉：线段树与树状数组都是"分层的部分和"：把"全加一遍"拆成"若干个预制整段之和"，修改时只重算覆盖该位置的少数整段。2 的幂下标让树状数组用一行位运算完成段选择，堪称位运算与下标算术的合璧（下一节位运算的预告）。
走火入魔：需求越界还硬撑
**事故一：静态数据上了树。**数据建好不变、只查不改，前缀和一遍预处理全搞定，上树纯属浪费常数与代码。先问"改不改变"，再选账房。
**事故二：树状数组求区间最值。**前缀相减的套路对 max 无效（max 不可逆）。有"区间最值 + 单点修改"需求，正解是线段树；竞赛里另有单调栈、稀疏表（静态）等兵器，按需取用。
本节要点回顾
- 矛盾需求（频繁改 + 频繁查）靠树形分层化解，线段树与树状数组双双 O(log n)；
- 线段树查询分解：区间被拆成对数个"整取段"（实例 1+5+7=13，节点可复算）；单点修改只动一条根叶链；
- 树状数组用 lowbit 把管辖长度编进下标，add 上跳、prefix 下拆，代码极短但只服务可逆信息；
- 功能分水岭：区间最值、区间推平等高级操作是线段树的领地；
- 下标纪律：树状数组 1 起、线段树根在 1，0 起下标进门先加一。
数值区间有账房管了，字符的"区间匹配"另有一门内功——KMP 与 Rabin-Karp，下一节见。