线段树区间聚合

区间查询数据结构 · HTML

数学 / 逻辑形态

给定结合运算 merge 与单位元 identity；维护 set(i,x) 和 query(l,r) 的半开区间聚合。

识别信号

• 查询与更新在线交错
• 摘要可由左右区间合并
• 需要 min/max/gcd 或多字段摘要
• 点变化后只想更新对数节点
• 可能扩展 lazy propagation

容易误判的相似信号

核心不变量

每个内部节点始终等于左右孩子相邻区间的 merge 结果。

状态、转移与处理顺序

Python 骨架

class SegmentTree:
    def __init__(self, a, merge=min, identity=float('inf')):
        self.merge, self.id = merge, identity
        self.n = 1
        while self.n < len(a): self.n *= 2
        self.t = [identity] * (2 * self.n)
        self.t[self.n:self.n+len(a)] = a
        for i in range(self.n-1, 0, -1):
            self.t[i] = merge(self.t[2*i], self.t[2*i+1])
    def set(self, i, value):
        i += self.n; self.t[i] = value
        while i > 1:
            i //= 2
            self.t[i] = self.merge(self.t[2*i], self.t[2*i+1])
    def query(self, l, r):
        l += self.n; r += self.n
        left = right = self.id
        while l < r:
            if l & 1: left = self.merge(left, self.t[l]); l += 1
            if r & 1: r -= 1; right = self.merge(self.t[r], right)
            l //= 2; r //= 2
        return self.merge(left, right)

正确性思路

1. 自底向上建树使初始摘要正确。
2. 点更新只影响叶到根的祖先，重算后恢复不变量。
3. 查询选出的节点互不重叠且恰覆盖区间。
4. 左右累积器保留顺序，所以非交换 merge 也正确。

复杂度

边界条件

• 空查询返回 identity
• merge 必须结合但不必交换
• 全负 max 的 identity 不能取 0
• 非交换 merge 要保留顺序
• 非二次幂空叶填 identity

错误模式

选择与排除规则

• 动态点更新加可结合摘要：segment tree。
• 可逆前缀和：优先 Fenwick。
• 静态幂等查询：Sparse Table。
• 区间更新时先定义 lazy tag 的组合不变量。

相关模板

原创微型例子

Recall prompts

• merge 至少满足什么性质？
• 为何需要左右两个累积器？
• 点更新影响哪些节点？

我的补充