摘要生成中...
AI 摘要
Hunyuan-lite

线段树简述

线段树是用来维护 区间信息 的数据结构。线段树的每个节点代表一个区间。

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

线段树的模板

模板题：求给定区间的区间和（多次询问）

线段树中，区间的范围给定之后，树的结点就固定了。

使用链表表示线段树

预先定义：

1
2
3
4
5
6
class Node{
	int val,add;
	Node left,right;
}
Node root = new Node(); // 预先定义好树根
int N = 1000000000;     // 题目中可能出现的范围

线段树的构建模板写法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void buildTree(Node node, int start, int end) {
    // 到达叶子节点
    if (start == end) {
        node.val = arr[start];
        return ;
    }
    if(node.left==null)node.left=new Node();
    if(node.right==null)node.right=new Node();
    int mid = (start + end) >> 1;
    buildTree(node.left, start, mid);
    buildTree(node.right, mid + 1, end);
    // 向上更新
    pushUp(node);
}
// 向上更新
private void pushUp(Node node) {
    node.val = node.left.val + node.right.val;
}

线段树动态开点模板写法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
// 动态开点
public class SegmentTreeDynamic {
	// 结点表示
    class Node {
        Node left, right; // 左右指针
        int val; // 结点的值，意思为此节点锁表示区间的区间和
        int add; // 懒惰标记，意思是此节点的子结点的每个元素的值都要加上 add
    }
    private int N = (int) 1e9; // 区间范围，一般由题目给出
    private Node root = new Node(); // 根结点

	// 区间更新
	// 将[start,end]当前结点的所有元素加上 val
    public void update(Node node, int start, int end, int l, int r, int val) {
        // 当前结点已经满足更新范围
        if (l <= start && end <= r) {
            node.val += (end - start + 1) * val;
            node.add += val;
            // 子节点就不再递归，实现了「懒惰」
            return ;
        }
        int mid = (start + end) >> 1;
        pushDown(node, mid - start + 1, end - mid); // 清空当前结点懒惰标记
        // 表明查询区间和左子区间有交集
        if (l <= mid) update(node.left, start, mid, l, r, val);
        // 表明查询区间和右子区间有交集
        if (mid + 1 <= r) update(node.right, mid + 1, end, l, r, val);
        pushUp(node); // 更新当前结点的区间值
    }
    public int query(Node node, int start, int end, int l, int r) {
        if (l <= start && end <= r) return node.val;
        int mid = (start + end) >> 1;
        int ans = 0;
        pushDown(node, mid - start + 1, end - mid);
        // 表明查询区间和左子区间有交集
        if (l <= mid) ans += query(node.left, start, mid, l, r); 
        // 表明查询区间和右子区间有交集
        if (mid + 1 <= r) ans += query(node.right, mid + 1, end, l, r);
        return ans;
    }
    private void pushUp(Node node) {
        node.val = node.left.val + node.right.val;
    }

	// 结点下推
    private void pushDown(Node node, int leftNum, int rightNum) {
	    // 子节点建立检查
        if (node.left == null) node.left = new Node();
        if (node.right == null) node.right = new Node();
        if (node.add == 0) return ; // 没有懒惰标记，无需处理

		// 处理懒惰标记
        node.left.val += node.add * leftNum;
        node.right.val += node.add * rightNum;
        node.left.add += node.add;  // 累积懒惰标记
        node.right.add += node.add;
        node.add = 0;               // 清空懒惰标记，表示处理完毕
    }
}

从上面的代码可以看出，不管是 update，还是 query，在进行下层递归时都是使用 [start, mid] 和 [mid + 1, end]。它表示数的当前结点表示的区间范围。

递归时，不管是 update，还是 query，[l,r] 表示查询区间，参数传递时是不变的。不要自行分割区间，如：

1
2
3
4
5
6
// 错误写法
if (l <= mid) update(node.left, start, mid, l, mid, val);
if (mid + 1 <= r) update(node.right, mid + 1, end, mid+1, r, val);
// 更正写法（按照自行分割的思路）
if (l <= mid) update(node.left,start,mid,l,r>=mid?mid:r,val);
if (mid + 1 <= r) update(node.right,mid+1,end,l<=mid+1?mid+1:l,r,val);

上面的做法是错误的，因为你可能会把查询的区间扩大了，也就是说，上面的代码没有考虑到 r<mid 或 l>mid+1 的情况。

递归时的终止条件中，我们并没有检查 start <= end，即不考虑 start > end 的情况，那么 update，还是 query 在递归过程中传入的参数会出现 start > end 吗？答案是不会的。推导 [1] 如下：

  • 因为本层传入 start > end 只有在上一层有 start==end 并计算 mid=(start+end)/2; 时，对右子区间递归时才可能出现。
  • 然而如果上一层传入的参数 start==end，那么必有 l <= start && end <= r，它只会在第一个条件判断语句（边界条件）中跳出递归，不会进行后续的 mid 计算，更无下一层的递归。
  • 因此不会出现传过来的参数 start > end。

对于终止条件的风格，还有以下这种，两者是等价的：

1
2
3
4
5
6
7
8
9
10
11
12
13
public void update(Node node, int start,int end,int l,int r,int val){
	if(r<start || l> end)return; // 查询区间与当前区间无交集
	if(l<= start && end <= r){
		node.val += val * ( end-start+1);
		node.add += val;
		return ;
	}
	int mid = (start+end)/2;
	pushDown(node,mid-start+1,end-mid);
	update(node.left,start,mid,l,r,val);   // 移除了前面的判断条件
	update(node.right,mid+1,end,l,r,val);  // 移除了前面的判断条件
	pushUp(node);
}

在不同的题目中，val 和 add 可以扮演不同的角色，比如区间和或者区间最值。这时候就需要根据题目要求修改 val 和 add 的计算代码。

使用数组表示线段树

image.png

堆式存储

我们知道，（二叉）堆的逻辑结构是树形的，但其存储结构是数组。树根编号为 1。假设某结点的编号为 p，则其左孩子的编号为 2p，右孩子编号为 2p+1。

image.png

代码写法：父结点编号 p，左子节点编号 p<<1，右子节点编号 p<<1|1。注意，不建议使用移位运算配合加号使用，因为加号优先级更高，因此需要引入额外的括号。

优先级的记忆口诀：单算移关与，异或逻条赋

括号级别最高，逗号级别最低，单目 > 算术 > 位移 > 关系 > 逻辑 > 三目 > 赋值。

就是把原先在链式结构中 Node 的属性值变为数组即可。注意取的数组大小至少为 4N，如果题目中所需的 N 过大可能会导致内存超限。

关于使用堆式存储时数组大小设置成 4N 的原因

关于线段树的空间：如果采用堆式存储，若有 n 个叶子结点，则 d 数组的范围最大为 2⌈log⁡n⌉+12^{\left\lceil\log{n}\right\rceil+1}。

分析：容易知道线段树的深度是 ⌈log⁡n⌉\left\lceil\log{n}\right\rceil 的，则在堆式储存情况下叶子节点（包括无用的叶子节点）数量为 2⌈log⁡n⌉2^{\left\lceil\log{n}\right\rceil} 个，又由于其为一棵完全二叉树，则其总节点个数 2⌈log⁡n⌉+1−12^{\left\lceil\log{n}\right\rceil+1}-1。当然如果你懒得计算的话可以直接把数组长度设为 4n，因为 2⌈log⁡n⌉+1−1n\frac{2^{\left\lceil\log{n}\right\rceil+1}-1}{n} 的最大值在 n=2x+1(x∈N+)n=2^{x}+1(x\in N_{+}) 时取到，此时节点数为 2⌈log⁡n⌉+1−1=2x+2−1=4n−52^{\left\lceil\log{n}\right\rceil+1}-1=2^{x+2}-1=4n-5。

而堆式存储存在无用的叶子节点，可以考虑使用内存池管理线段树节点，每当需要新建节点时从池中获取。自底向上考虑，必有每两个底层节点合并为一个上层节点，因此可以类似哈夫曼树地证明，如果有 n 个叶子节点，这样的线段树总共有 2n-1 个节点。其空间效率优于堆式存储，并且是可能的最优情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
int N;
int[] vals ,adds; // 大小为 4 N

public void build(int nodeId,int start,int end){
	if(start==end){
		vals[nodeId]=nums[start];
		return;
	}
	int mid= (start+end)/2;
	build(nodeId<<1,start,mid);
	build(nodeId<<1|1,mid+1,end);
	pushUp(nodeId);
}

public void update(int nodeId, int start,int end,int l,int r,int val){
	if(l<= start && end <= r){
		vals[nodeId] += val * ( end-start+1);
		adds[nodeId] += val;
		return ;
	}
	int mid = (start+end)/2;

	pushDown(nodeId,mid-start+1,end-mid);
	if(l<=mid)update(nodeId<<1,start,mid,l,r,val);
	if(mid+1<=r)update(nodeId<<1|1,mid+1,end,l,r,val);
	pushUp(nodeId);
}

public void pushUp(int nodeId){
	vals[nodeId] = vals[nodeId<<1]+ vals[nodeId<<1|1];
}

public void pushDown(int nodeId,int leftNum,int rightNum){
	if(adds[nodeId]==0)return;
	vals[nodeId<<1]+=adds[nodeId]*leftNum;
	vals[nodeId<<1|1]+=adds[nodeId]*rightNum;
	adds[nodeId<<1]+=adds[nodeId];
	adds[nodeId<<1|1]+=adds[nodeId];
	adds[nodeId]=0;
}

public int query(int nodeId,int start , int end,int l,int r){
	if(l<=start&&end<=r){ 
		return vals[nodeId];
	}
	int mid = (start+end)/2;
	int ans=0;
	pushDown(nodeId,mid-start+1,end-mid);
	if(l<=mid)ans+=query(nodeId<<1,start,mid,l,r);
	if(mid+1<=r)ans+=query(nodeId<<1|1,mid+1,end,l,r);
	return ans;
}

相关题目：🟨 307. 区域和检索 - 数组可修改 - 力扣（LeetCode）

什么情况下用动态开点线段树？

如果只是需要一次构建并求出结果，就使用一次归并的思路解决（写 build 函数即可）。

如果是多次更新与查询混合交替（在 LeetCode 中这种题目一般是叫你补充完整一个类），那就使用动态开点和懒惰标记模板，写一个完整的线段树。

根据题目实际情况，两个模板按需默写。比如在这些题目中：

本文参考

  1. 尝试将上面的话抽象为命题并用形式语言证明？一点点参考：站内文章你真的弄懂假言判断（条件命题）了吗？。 ↩︎