15.4 线段树
前置：二叉树与区间边界。本页实现单点赋值和半开区间求和；区间批量更新需要下一层的 lazy propagation 合同。
区间总量与单点值都在变化
前缀和能用 O(1) 回答静态区间和，但一次点更新要影响后面的许多前缀。直接数组更新便宜，区间查询却要扫描。线段树在两者之间取平衡：叶子保存单点值，父节点保存两个孩子区间的和。
一次点更新只改变叶子到根的一条路径；一次区间查询把目标拆成 O(log n) 个互不重叠的树节点区间。
先把查询区间的边界说清楚
“下标 3 到下标 8”可能包含两端，也可能采用右端开区间。接口若不先规定边界，算法再快也会稳定地算错。这里统一使用半开区间。
本实现接收整数可迭代对象并复制输入，更新值也必须为整数，布尔值不在合同内。构建与更新遇到非法值抛 TypeError；非法下标或区间抛 IndexError。长度固定，更新前先检查下标和值。
本页统一使用 [left, right)：包含 left，不包含 right。空区间 [i, i) 的和是 0；整个数组是 [0, n)。这种约定与 Python 切片一致，也让相邻区间 [a, b)、[b, c) 不重叠且没有缝隙。
class SumSegmentTree:
def __init__(self, values):
data = list(values)
for value in data:
self._check_value(value)
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]
@staticmethod
def _check_value(value):
if not isinstance(value, int) or isinstance(value, bool):
raise TypeError("values must be integers")
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)
self._check_value(value)
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)，点更新抛 IndexError。与 Python 切片不同，越界端点不会被自动截断，反向区间也不会被当成空区间。
把汇总树藏进一排格子
_leaf_count 取不小于 n 的最小 2 的幂。叶子从这个下标开始，未使用的叶位置保持加法单位元 0。对任意内部节点 p：
tree[p] = tree[2*p] + tree[2*p+1]根在下标 1，下标 0 留空。总数组长度是 2 * leaf_count，即 Θ(n+1)，包括空数组时的两个槽。这种布局比笼统地写“开 4n 一定安全”更容易说明每个位置的含义。
构建从叶子上方倒序合并，每个节点处理一次，时间 Θ(n+1)。对 n 个值逐个调用 update 建树则为 O(n log(n+1))，两者不应混为一个复杂度。
一次查询只合并覆盖目标的摘要
迭代查询维护尚未处理的半开区间。左边界下标为奇数，表示它是右孩子；左兄弟不在目标内，因此先取它，再把左边界加 1。右边界为奇数时，边界本身是被排除的右孩子，所以把右边界减 1，取其左兄弟。余下区间两端都已对齐兄弟对，才一起除以 2 上移。
例如叶容量为 8，查询 [1,6) 先得到边界 (9,14)，取节点 9；上移到 (5,7) 后取节点 5 和 6。它们分别覆盖 [1,2)、[2,4)、[4,6)，不重叠也不漏元素。
每层至多接纳两个节点，树高 O(log(n+1))，所以非空树的查询和点更新均为 O(log(n+1)) 时间，两个迭代方法额外空间 O(1)；空树的合法查询为 O(1)。这些界把整数加法视为常数操作，大整数仍要计入位数成本。
整数求和满足结合律，并有单位元 0。浮点求和不严格满足结合律，这也是本实现限制整数输入的原因。线段树也能维护最小值、最大值、gcd 或自定义结合操作；若操作不满足结合律，任意分段再合并可能改变答案。若操作不满足交换律，还必须保持左右片段的合并顺序，本页单个 total 的写法不能直接照搬。可分别维护左、右结果：左侧按 combine(left_total, node) 追加，右侧按 combine(node, right_total) 前置，最后合并左右结果。AtCoder Library 的线段树接口将结合律、单位元与操作成本写成了明确前提。
整段数值一起变化时，先记录延迟更新
若要把 [left, right) 内每个值都加上 delta，逐点更新需要 O(k log(n+1))，其中 k=right-left。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 标记，并写出父节点和子标记的更新公式。
最后一条祖先链
线段树没有保存每个查询的答案，只保存可复用的区间摘要。单点变化后，只有一条祖先链失效；查询则从这些摘要中拼出目标区间。