15.4 线段树
算法森林的补给线拉长以后，阿花发现按区间盘点库存已经不能每次都从头累加。
前置：二叉树与区间边界。本页实现单点赋值和半开区间求和；区间批量更新需要下一层的 lazy propagation 合同。
物资总量总在变化
驿站按道路顺序排成一列。长老既会问“第 3 到第 8 站共有多少物资”，又会随时修正某一站的库存。
前缀和能用 O(1) 回答静态区间和，但一次点更新要影响后面的许多前缀。直接数组更新便宜，区间查询却要扫描。线段树在两者之间取平衡：叶子保存单点值，父节点保存两个孩子区间的和。
一次点更新只改变叶子到根的一条路径；一次区间查询把目标拆成 O(log n) 个互不重叠的树节点区间。
先把驿站区间的边界说清楚
“第 3 站到第 8 站”在人话里可能包含两端，也可能只是一句含糊指令。长老若不先规定边界，库存算法再快也会稳定地算错。这里统一使用半开区间。
本页统一使用 [left, right)：包含 left，不包含 right。空区间 [i, i) 的和是 0；整个数组是 [0, n)。这种约定与 Python 切片一致，也让相邻区间 [a, b)、[b, c) 不重叠且没有缝隙。
class SumSegmentTree:
def __init__(self, values):
data = list(values)
self.length = len(data)
self._leaf_count = 1
while self._leaf_count < self.length:
self._leaf_count *= 2
self._tree = [0] * (2 * self._leaf_count)
for index, value in enumerate(data):
self._tree[self._leaf_count + index] = value
for node in range(self._leaf_count - 1, 0, -1):
self._tree[node] = self._tree[2 * node] + self._tree[2 * node + 1]
def _check_index(self, index):
if (
not isinstance(index, int)
or isinstance(index, bool)
or not 0 <= index < self.length
):
raise IndexError(f"index out of range: {index!r}")
def update(self, index, value):
self._check_index(index)
node = self._leaf_count + index
self._tree[node] = value
node //= 2
while node:
self._tree[node] = self._tree[2 * node] + self._tree[2 * node + 1]
node //= 2
def query(self, left, right):
if (
not isinstance(left, int)
or isinstance(left, bool)
or not isinstance(right, int)
or isinstance(right, bool)
or not 0 <= left <= right <= self.length
):
raise IndexError(f"invalid half-open range: [{left!r}, {right!r})")
left += self._leaf_count
right += self._leaf_count
total = 0
while left < right:
if left & 1:
total += self._tree[left]
left += 1
if right & 1:
right -= 1
total += self._tree[right]
left //= 2
right //= 2
return total
if __name__ == "__main__":
tree = SumSegmentTree([1, 3, 5, 7, 9, 11])
assert tree.query(1, 4) == 15
tree.update(2, 6)
assert tree.query(1, 4) == 16
assert tree.query(0, tree.length) == 37
assert tree.query(3, 3) == 0
empty = SumSegmentTree([])
assert empty.query(0, 0) == 0
print("线段树检查通过")原页递归构建空数组时会进入非法区间并无限递归。这份实现让空树保持一个内部单位叶容量，只允许查询 [0, 0)，点更新则按合同失败。
把汇总树藏进一排格子
驿站在地图上是一棵区间树，实现时不必为每个节点制作对象。把叶子集中放在数组后半段，父节点放在前半段，就能用下标找到左右孩子和祖先。
_leaf_count 取不小于 n 的最小 2 的幂。叶子从这个下标开始，未使用的叶位置保持加法单位元 0。对任意内部节点 p：
tree[p] = tree[2*p] + tree[2*p+1]根在下标 1，下标 0 留空。总数组长度是 2 * leaf_count，即 O(n)。这种布局比笼统地写“开 4n 一定安全”更容易说明每个位置的含义。
构建从叶子上方倒序合并，每个节点处理一次，时间 O(n)。逐个调用 update 建树则是 O(n log n)，两者不应混为一个复杂度。
一次巡查只带走覆盖目标的摘要
查询队伍从区间两端向根部靠拢。遇到完整落在目标内的节点，就带走它保存的总量，不再下到每座驿站逐项清点。
迭代查询维护尚未处理的左右边界。左边界是右孩子时，它对应的整段不能再向上合并，立即加入结果并右移；右边界是右孩子的后一位置时，先左移，再加入对应左侧整段。随后两边同时上移到父层。
每层至多接纳两个节点，树高 O(log n)，所以查询时间 O(log n)。点更新也只重算叶子到根的祖先，时间 O(log n)。
求和满足结合律，并有单位元 0。线段树也能维护最小值、最大值、gcd 或自定义结合操作；若操作不满足结合律，任意分段再合并可能改变答案。若操作不满足交换律，还必须保持左右片段的合并顺序，本页单个 total 的写法不能直接照搬。
整段物资一起变化时，先挂一张待办牌
若一整段驿站都增加同样库存，逐站下发会失去线段树的优势。Lazy propagation 先把更新挂在覆盖节点上，等查询或继续下探时再兑现；这张待办牌必须说明怎样组合，不能只写“以后处理”。
若要把 [left, right) 内每个值都加上 delta，逐点更新需要 O(k log n)。Lazy propagation 把“整段都要执行的更新”暂存在覆盖节点上，等查询或继续下探时再推给孩子，从而把区间更新压到 O(log n)。
这需要额外定义：
- 更新如何作用于聚合值，例如区间和要增加
delta * segment_length； - 两次延迟更新怎样组合；
- 何时把标记下推并清除。
区间加、区间赋值和仿射变换的标记组合规则不同。没有先写清代数合同，就不该粘贴一份“通用 lazy 模板”。
与其他区间结构比较
| 需求 | 合适的起点 |
|---|---|
| 静态区间和 | 前缀和 |
| 单点更新 + 前缀/区间和 | Fenwick 树或线段树 |
| 多种结合聚合、区间更新 | 线段树 |
| 静态 RMQ | sparse table 等静态结构 |
Fenwick 树通常代码更短、常数更小，但适用的代数操作与查询形式更受限制。实际选择要结合操作集合、内存与实现复杂度，而不是按“高级程度”排序。
动手检查区间边界
- 与 Python
sum(values[left:right])随机对照查询和更新。 - 把聚合改成最小值，空区间应返回什么单位元？
- 实现返回区间和但支持单点增量，而非单点赋值。
- 证明
_leaf_count < 2n（n > 0），从而推出存储 O(n)。 - 设计区间加的 lazy 标记，并写出父节点和子标记的更新公式。
最后一条祖先链
线段树没有保存每个查询的答案，只保存可复用的区间摘要。单点变化后，只有一条祖先链失效；查询则从这些摘要中拼出目标区间。
回到第 15 章导览可以比较布隆过滤器、并查集、线段树与前面学过的 Trie。算法森林到这里结束，下一卷进入计算机系统。