schtonn

schtonn

0%

线段树

Posted on Edited on Valine:

前置知识

数组，结构体，二叉树

引入

有时候我们会遇到一些大规模的区间查找和区间修改问题，比如让你维护一个 \(10^5\) 长度的数列，要求操作有区间求和、区间加（区间每个数加上一个值），让你在一秒内完成 \(10^5\) 次操作。

暴力是肯定不行的，数据范围太大，操作太多，会超时。

所以我们就有一种专门解决大范围区间修改查询的数据结构：线段树。

线段树

线段树本质上是把整个数列拆分了，用一个一个区间来表示。

比如有 \(n\) 个节点，根节点代表整个数列的区间 \([1,n]\)，根节点的两个子节点代表根区间二分成两部分，也就是 \([1,\operatorname{mid}]\) 和 \([\operatorname{mid}+1,n]\)。 而子节点也是一棵线段树。 一直往下延伸，叶子结点就代表着单一位置 \([a,a]\)。 下图是一个 \(n=7\) 的示例：

segment-1
segment-1

每一个节点都存储着它所代表的区间的信息，比如这个区间的元素和。

查找

解释

如查找 \([l,r]\)，则执行以下步骤： 1. 首先在根节点查找 \([l,r]\) 2. 判断当前所在区间是否在当前查找的区间内部，若在内部则直接返回当前区间数据。 3. 若当前区间的右子节点区间的左边界在当前查找的区间的左边界的右侧，说明当前查找区间完全在右子节点一侧，则返回在右子节点查找 \([l,r]\) 的结果。 4. 否则，若当前区间的左子节点区间的右边界在当前查找区间的右边界的左侧，说明当前查找区间完全在左子节点一侧，则返回在左子节点查找 \([l,r]\) 的结果。 5. 否则，说明当前查找区间横跨左右子节点，那么返回：在左子节点查找当前查找区间的左边界-左子节点区间的右边界与在右子节点查找右子节点的左边界-当前查找区间的右边界结果的和。

简单来说就是不断向下递归寻找，直到当前的区间能包住全部或者一部分要求区间。

举例

设若查找区间 \([3,6]\)，首先从根节点开始： - 当前区间 \([1,7]\) 不在 \([3,6]\) 内部，经过判断 \([3,6]\) 横跨左右子节点，分别在左右子节点查找查找：\([3,3]\) 和 \([4,6]\)。 - 于是在 \([1,3]\) 内查找 \([3,3]\)，经过两次下放到右子树最终返回。 - 接着在 \([4,7]\) 内查找 \([4,6]\)，\(4,6\) 横跨左右子树，继续查找：\([4-5]\) 和 \([6-6]\)。 - 进入 \([4,5]\)，在区间内部，直接返回。由 \([6,7]\) 进入 \([6,6]\) 后返回，查找完毕。

修改

我们会发现，修改时如果像查找一样做，那么有一些细小的叶子修改就改不到，如刚才举例的 \([4,5]\)，如果只修改 \([4,5]\) 区间，那么单独查询 \([4,4]\) 和 \([5,5]\) 的时候就会出错。要是每一个修改都下放到叶子节点，那这个算法就和暴力一样了。所以我们需要一些巧妙地解决办法。

lazy

我们在树的节点上加一个标记：\(\texttt{lazy}\)。

所谓 \(\texttt{lazy}\)，就是要懒，就是要在事情迫不得已要做的时候把它做了，所以我们每次那些细小的叶子修改就不做他，直接记录在 \(\texttt{lazy}\) 标记上，等到要查询的时候，再从标记上下放到子结点上，查询到哪里就下放到哪里。

在刚才的例子里，修改 \([4,5]\) 时就把一个同样值的 \(\texttt{lazy}\) 也放在了 \([4,5]\) 点里，递归查找 \([4,4]\) 时就会把 \(\texttt{lazy}\) 下放，这时才修改了 \([4,4]\)。

注意

修改后的结点，需要同时把所有祖先结点全部更新。

优势

暴力算法的复杂度是 \(O(nm)\) 的，而线段树的复杂度是 \(O(n\log m)\) 的，因为每次树深入一层，区间长度都会减半。

代码(luogu P3372)

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include "iostream"
using namespace std;
#define N 1000010
#define lson id<<1 //此处偷了懒，因为完全二叉树的性质可以推出，左子树编号是根节点的一倍，右子树是根节点一倍加一，
#define rson id<<1|1 //使用位运算提高速度。
int a[N],n,m,op,x,y,k;
struct node {
	int l,r,sum,lazy;
}t[2*N];
void update(int id){//更新函数（向上更新修改的）
	t[id].sum=t[lson].sum+t[lson].lazy*(t[lson].r-t[lson].l+1)+
		t[rson].sum+t[rson].lazy*(t[rson].r-t[rson].l+1);
}
void pushdown(int id){//下推函数（下推lazy的）
	if(t[id].lazy){
		t[lson].lazy+=t[id].lazy;
		t[rson].lazy+=t[id].lazy;
		t[id].sum+=t[id].lazy*(t[id].r-t[id].l+1);
		t[id].lazy=0;
	}
}
void buildtree(int id,int l,int r){//建树
	t[id].l=l;
	t[id].r=r;
	t[id].lazy=0;
	if(l==r){
		t[id].sum=a[l];
		return;
	}
	int mid=(l+r)>>1;
	buildtree(lson,l,mid);
	buildtree(rson,mid+1,r);
	update(id);
}
void change(int id,int l,int r,int c){//修改
	if(t[id].l>=l&&t[id].r<=r){
		t[id].lazy+=c;
		return;
	}
	pushdown(id);
	if(t[lson].r>=r)change(lson,l,r,c);
	else if(t[rson].l<=l)change(rson,l,r,c);
	else{
		change(lson,l,t[lson].r,c);
		change(rson,t[rson].l,r,c);
	}
	update(id);
}
int query(int id,int l,int r){//求和
	if(t[id].l>=l&&t[id].r<=r){
		return t[id].sum+t[id].lazy*(t[id].r-t[id].l+1);
	}
	pushdown(id);
	if(t[lson].r>=r)return query(lson,l,r);
	else if(t[rson].l<=l)return query(rson,l,r);
	else{
		return query(lson,l,t[lson].r)+query(rson,t[rson].l,r);
	}
	update(id);
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	buildtree(1,1,n);
	for(int i=1;i<=m;i++){
		cin>>op;
		if(op==1){
			cin>>x>>y>>k;
			change(1,x,y,k);
		}
		else{
			cin>>x>>y;
			cout<<query(1,x,y)<<endl;
		}
	}
	return 0;
}