专题进阶 · 树与范围查询推荐总顺序 · 第 54 / 148 课

用可合并的区间摘要组织查询,解释相交、包含与懒标记的区别。

先学会这些,再进入本课 二叉树 前缀和 树状数组
还有 3 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 树与范围查询

线段树Segment Tree

把区间递归分解,支持可合并信息的区间查询和更新。

建议 50 分钟 · 含手算、代码与三层练习

本课要建立的能力

用可合并的区间摘要组织查询,解释相交、包含与懒标记的区别。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

既要单点修改,又要查询任意区间的和、最大值或其他可合并信息,树状数组的前缀相减并非总适用。

02一步步得到方法

区间被反复二分

根表示整个区间,孩子表示左右两半,叶子表示单元素。每个内部节点保存两个孩子摘要的合并结果。求和用加法,最小值用 min;合并需要结合律,空区间需要单位元。

本课采用迭代布局:把叶子数补到不小于 n 的二次幂 size,叶子放在 [size,2size),父节点下标是 i//2。多出的叶子存 0,保证不改变和。

查询只取完整覆盖块

把 [l,r) 平移到叶子层。若 l 是右孩子,它的左兄弟不在范围内,所以先取 l 再 l++;若 r 是右边界对应的右孩子位置,先 --r 再取该左侧尾块。随后两端同时上移。

两边向上靠拢时,所取块互不重叠,覆盖范围逐层缩小。单点赋值则修改叶子后一路重算父节点。区间更新若想快,需要懒标记表示尚未下传的统一操作,不能仅改根摘要就当完成所有子节点。

先选聚合运算,再定义单位元

线段树每个节点保存一段区间的聚合结果。聚合应满足结合律,空段需要单位元:和是0,最小值是正无穷,最大值是负无穷。不同查询不能随意复用同一个初始值。

迭代半开区间查询分别收集左右两侧块,范围逐层缩小。若聚合不满足交换律,还必须保留左右累积次序;本课的求和掩盖了这个更一般的顺序要求。

03把一个小例子完全算清楚

[1,2,3,4] 查询 [1,4),再把下标 2 改为 10。

步骤计算与状态为什么这样做
叶子位置 4..7 存 1,2,3,4父节点 2=3,3=7
查询取叶子 5 的 2,再取节点 3 的 7结果 9
更新叶子 6=10,节点 3=14,根=17只重算祖先
再次查询2+14=16不访问无关节点

窄屏可左右滑动表格,阅读完整计算与理由。

线段树保存的是可以快速合并的区间摘要,而非每种查询的完整答案。

04为什么这个方法成立

  1. 建树自底向上,使每个节点等于其叶子区间之和。
  2. 单点赋值只影响祖先区间,重算祖先恢复不变量。
  3. 查询挑选不重叠且恰好覆盖目标范围的节点,合并得到正确答案。

05把推导翻译成代码

Python · 可独立运行的教学实现

class SegmentTree:
    def __init__(self, a):
        self.n, self.size = len(a), 1
        while self.size < self.n:
            self.size *= 2
        self.tree = [0]*(2*self.size)
        self.tree[self.size:self.size+self.n] = a
        for i in range(self.size-1,0,-1):
            self.tree[i] = self.tree[2*i] + self.tree[2*i+1]
    def assign(self, index, value):
        assert 0 <= index < self.n
        i = self.size + index
        self.tree[i] = value
        while i > 1:
            i //= 2
            self.tree[i] = self.tree[2*i] + self.tree[2*i+1]
    def query(self, left, right):
        assert 0 <= left <= right <= self.n
        left += self.size; right += self.size
        result = 0
        while left < right:
            if left % 2:
                result += self.tree[left]; left += 1
            if right % 2:
                right -= 1; result += self.tree[right]
            left //= 2; right //= 2
        return result

逐个理解关键决定

right -= 1
右端不包含,必须先退一格再取尾块。
self.tree[2*i] + self.tree[2*i+1]
父摘要只由两个孩子合并,因此更新传播每层 O(1)。

06时间、空间与实现范围

建树 O(n),存储 O(n),单点赋值和区间查询 O(log n)。

区间加的懒标记版本还需记录区间长度,并正确组合旧标记与新操作;本课代码没有该扩展。

07改变条件,检查哪里会出错

任意合并运算都可交换左右顺序

字符串连接、矩阵乘法等不交换;泛化查询需分别维护左右累计值再按顺序合并。

实现点更新却宣称范围修改也 O(log n)

范围更新通常需要额外的懒标记及合成规则,不能只改一个叶子就完成。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

区间最小值的空叶填多少?

需要一点提示

不能影响 min。

查看解析与答案

填正无穷,合并改为 min。

练习 2 · 边界与辨析

空查询 [2,2) 返回什么?

需要一点提示

没有任何覆盖块。

查看解析与答案

求和返回 0,其他运算返回相应单位元。

练习 3 · 变式与迁移

给整段加 5,根的和应增加多少?

需要一点提示

每个元素都变化。

查看解析与答案

增加 5×区间长度;懒标记保存 +5,之后访问孩子时再传播,不能只让根加 5。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Princeton · 查找结构

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。