数据结构_线段树 详解+模板

😊 | Powered By HeartFireY | Segment Tree 一、线段树简介

线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。

线段树可以在 O ( log ⁡ N ) O(\log N) O(logN) 的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。

线段树维护的信息，需要满足可加性，即能以可以接受的速度合并信息和修改信息，包括在使用Lazy标记时，标记也要满足可加性

注：可加性表示运算能否合并，例如取模就不满足可加性，对 4 4 4 取模然后对 3 3 3 取模，两个操作就不能合并在一起做。

二、线段树的基本结构 1.什么是线段树

线段树将每个长度不为 1 1 1 的区间划分成左右两个区间递归求解，把整个线段划分为一个树形结构，通过合并左右两区间信息来求得该区间的信息。这种数据结构可以方便的进行大部分的区间操作。

我们举例来说明线段树的基本结构：

我们给出一个数组 A = { 11 ,   22 ,   33 ,   44 ,   55 } A = \{11, \ 22, \ 33, \ 44, \ 55 \} A={11, 22, 33, 44, 55}，我们开始针对这个数组构造线段树，首先将根节点编号设为 1 1 1，用数组 D D D来保存线段树，其中 D i D_i Di​保存线段树上编号为 i i i的结点的值(每个结点所维护的值就是这个节点所表示的区间总和)，如下图所示：

图中 D 1 D_1 D1​ 表示根节点， $ D_1$ 所表示的区间就是 [ 1 , 4 ] [1,4] [1,4]（ a 1 , a 2 , ⋯   , a 5 a_1,a_2, \cdots ,a_5 a1​,a2​,⋯,a5​），其值为 ∑ i = 1 n = 5 A i \sum^{n = 5}_{i = 1}A_i ∑i=1n=5​Ai​，其余结点类推。

通过观察不难发现， D i D_i Di​ 的左儿子节点就是 D 2 × i D_{2\times i} D2×i​， D i D_i Di​ 的右儿子节点就是 D 2 × i + 1 D_{2\times i+1} D2×i+1​。如果 D i D_i Di​ 表示的是区间 [ s , t ] [s,t] [s,t]（即 D i = A s + A s + 1 + ⋯ + A t D_i=A_s+A_{s+1}+ \cdots +A_t Di​=As​+As+1​+⋯+At​) 的话，那么 D i D_i Di​ 的左儿子节点表示的是区间 [ s , s + t 2 ] [ s, \frac{s+t}{2} ] [s,2s+t​]， D i D_i Di​ 的右儿子表示的是区间 [ s + t 2 + 1 , t ] [ \frac{s+t}{2} +1,t ] [2s+t​+1,t]。

2.线段树的建立

首先我们选择堆式储存，即用数组对线段树进行储存（那么 2 p 2p 2p 是 p p p 的左儿子， 2 p + 1 2p+1 2p+1 是 p p p 的右儿子)，若有 n n n 个叶子结点，则 d 数组的范围最大为 2 ⌈ log ⁡ n ⌉ + 1 2^{\left\lceil\log{n}\right\rceil+1} 2⌈logn⌉+1。在实际操作中，我们一般把数组的大小开到 4 n 4n 4n，即4倍数据范围。(同时，建议关闭C++堆栈限制)。

分析：容易知道线段树的深度是 ⌈ log ⁡ n ⌉ \left\lceil\log{n}\right\rceil ⌈logn⌉ 的，则在堆式储存情况下叶子节点（包括无用的叶子节点）数量为 2 ⌈ log ⁡ n ⌉ 2^{\left\lceil\log{n}\right\rceil} 2⌈logn⌉ 个，又由于其为一棵完全二叉树，则其总节点个数 2 ⌈ log ⁡ n ⌉ + 1 − 1 2^{\left\lceil\log{n}\right\rceil+1}-1 2⌈logn⌉+1−1。

在实际使用过程中，我们可以直接将数组的大小开到 4 n 4n 4n，因为 2 ⌈ log ⁡ n ⌉ + 1 − 1 n \frac{2^{\left\lceil\log{n}\right\rceil+1}-1}{n} n2⌈logn⌉+1−1​ 的最大值在 n = 2 x + 1 ( x ∈ N + ) n=2^{x}+1(x\in N_{+}) n=2x+1(x∈N+​) 时取到，此时节点数为 2 ⌈ log ⁡ n ⌉ + 1 − 1 = 2 x + 2 − 1 = 4 n − 5 2^{\left\lceil\log{n}\right\rceil+1}-1=2^{x+2}-1=4n-5 2⌈logn⌉+1−1=2x+2−1=4n−5。

线段树一般采用递归建树，从根节点开始向下递归建左子树右子树。

那么我们讨论递归建树的边界：如果 D i D_i Di​ 表示的区间大小等于 1 1 1 的话（区间大小指的是区间包含的元素的个数，即 A A A的个数。设 D j D_j Dj​ 表示区间 [ l , r ] [l,r] [l,r]，它的区间大小就是 r − l + 1 r-l+1 r−l+1），那么 D i D_i Di​ 所表示的区间 [ l , r ] [l,r] [l,r] 中肯定有 l = r l=r l=r，且 D i = A l = A r D_i=A_l=A_r Di​=Al​=Ar​。这就是线段树的递归边界。

我们通过图片来说明建树的基本思路：

同时，我们通过动态示意图来展示递归执行的过程(以下过程展示的是区间最大值线段树)：

了解了具体的过程，那么我们就可以通过代码进行实现：

这里我们先介绍几个基本运算的表达方式：设当前结点下标为 r t rt rt

求当前结点的左子下标： r t × 2   ⟺   r t < < 1 rt \times 2 \ \Longleftrightarrow \ rt