线段树讲解二

Veröffentlicht am | in

概述

《线段树讲解一》讲解了单点更新区间查询的线段树，现在给出一种更普适的线段树，支持区间更新区间查询。

不同做法

使用单点更新

如果我们用单点更新来模拟区间更新，容易知道，每更新一个点虽然很快，但是更新整个区间确实十分费时间的一件事。更一般的，每次更新的复杂度是$O(nlogn)$，无法达到快速应答的需求。

懒操作

懒操作是线段树的核心操作，这是线段树之所以是log级算法的原因。我们可以注意到，对于线段树上的一个节点，如果我们更新的区间已经完全覆盖了这个区间，那么我们就没必要把这个节点的子节点都更新了，如果我们询问到这个节点的时候，我们再将堆积在这里的信息往下传。
这样操作的复杂度很明显是$O(logn)$的。

如同上图中，我们试图更新$[3,7]$的区间，注意到$[4,7]$是整个节点，所以我们只需将信息保存在$[4,7]$的节点上，当我们需要知道$[4,7]$节点以下信息的时候，再将信息往下传即可。

基本操作

结构和单点更新类似，只是多了一个懒操作的标记，我们用区间增加某个值，区间询问最大值的线段树来举例子。

结构

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
int N;
struct SegmentTree{
	#define lchild l,m,v<<1
	#define rchild m+1,r,v<<1|1
	struct Node{
		int maxVal,lazy;
	}Tree[MAX_N*4];
	void build(){
		for(int i=0;i<MAX_N*4;i++)
			Tree[i].maxVal=Tree[i].lazy=0;
	}
	void pushDown(int v){
		Tree[v<<1].maxVal+=Tree[v].lazy;
		Tree[v<<1|1].maxVal+=Tree[v].lazy;
		Tree[v<<1].lazy+=Tree[v].lazy;
		Tree[v<<1|1].lazy+=Tree[v].lazy;
		Tree[v].lazy=0;
	}
	void pushUp(int v){
		Tree[v].maxVal=max(Tree[v<<1].maxVal,Tree[v<<1|1].maxVal);
	}
	void update(int a,int b,int x,int l=1,int r=N,int v=1){
		if(a<=l&&r<=b){
			Tree[v].lazy+=x;
			Tree[v].maxVal+=x;
			return;
		}
		if(Tree[v].lazy)pushDown(v);
		int m=(l+r)>>1;
		if(a<=m)update(a,b,x,lchild);
		if(b>m)update(a,b,x,rchild);
		pushUp(v);
	}
	int query(int a,int b,int l=1,int r=N,int v=1){
		if(a<=l&&r<=b)
			return Tree[v].maxVal;
		int m=(l+r)>>1;
		int res=0;
		pushDown(v);
		if(a<=m)res=max(res,query(a,b,lchild));
		if(b>m)res=max(res,query(a,b,rchild));
		return res;
	}
}seg;