白告山风

不定期更新摄影，acm题解等等有趣的东西~

0%

线段树专题

发表于 更新于 分类于 ，
本文字数： 12k 阅读时长 ≈ 11 分钟

首先我们先来介绍线段树的基本组成部分，有原数组arr[N]，线段树数组segtree[N]，线段树每个元素包括当前节点的权重（原数组在某一区间的区间和等等）。

模板：单点修改+区间查询

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
//线段树的单点修改，区间求和
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+8;
struct Segtreemode{
    int val;
}segtree[N<<2];//这里4*n是保证 可以将完全平衡二叉树化的原数组完美存入。
int arr[N];
void pushup(int rt){//合并操作，其中rt<<1和rt<<1|1分别是根节点为rt的左右子树节点
    segtree[rt]=segtree[rt<<1].val+segtree[rt<<1|1].val;
}
void build(int l,int r,int rt){//构建线段树 l是当前的原数组左区间下标，r是当前原数组右区间下标 rt是当前线段树的节点下标
    if(l==r){//如果到了叶节点，直接赋值
        segtree[rt].val=arr[l];
        return ;
    }
    else{
        int mid=(l+r)/2;
        build(l,mid,rt<<1);//构建当前左子树
        build(mid+1,r,rt<<1|1);//构建当前右子树
        pushup(rt);//合并左右子树的值
    }
}
void update(int id,int val,int l,int r,int rt){//单点修改 将原数组下标为id的位置增加val，当然访问的原数组区间是[l,r]，在线段树里的节点是rt
    if(l==r&&r==id){
        segtree[rt].val+=val;
      //segtree[rt].val=val;//如果是将下标为id的值修改为val
    }
    else{
        int mid=(l+r)/2;
        if(id<=mid)build(id,val,l,mid,rt<<1);//经典二分查找的步骤
        else{
            build(id,val,mid+1,r,rt<<1|1);
        }
        pushup(rt);//保证子树更新后，上面的根节点也会跟着更新
    }
    
}
int query(int L,int R,int l,int r,int rt){//区间查询，需要查询的是区间[L,R],当前区间是[l,r],对应线段树节点是rt
	int remain=0;
    if(l>=L&&r<=R){//如果当前区间正好被需要查询的区间包含。
        return segtree[rt].val;
    }
    else if(r<L||l>R){//如果完全不相交
        return 0;
    }
    else{//区间存在交叉
        int mid=(l+r)/2;
        return query(L,R,l,mid,rt<<1)+query(L,R,mid+1,r,rt<<1|1);
    }
}

​ 大致来看，你会发现树状数组和线段树的优化原理很相似，都是通过将原数组按规律割分成若干子区间，从而减少对某个点修改甚至对某个区间修改时的对预处理数组的修改次数，但是线段树和树状数组有个本质上的区别，树状数组的底层原理只能支持它代表整体区间，对于如果想来表示区间中的一个最大值，则会在修改的过程的中，如果不借助其他辅助数组就会不确定这个特征值是否会改变，而线段树，就不会有这个问题，所以这就是在处理查询区间最大值时，线段树是第一选择。

​ 然而线段树的精髓真的体现却是在区间修改+区间查询。其中需要用到lazy标记，充分体现了节能主义，，其绝不干除了影响查询结果之外其他多余的事，但是对于那些相对于查询多余的修改，虽然没做，但是会做上标记，如果查询到了它的头上，我才进行修改。

例题2：洛谷P3373线段树1区间修改+区间查询

由题易知我们需要进行将一个区间全部加上一个值，或者求一个区间和的操作，我们先仔细看看这道题的数据范围
$$
1\leq{n,m}\leq10^5
$$
其中n是原数组个数，m是操作次数，我们不妨取一个极限，n和m均为10^5,若我们进行10^5 -1次从（1+random（1100））到（10^5-random（1100））每个数字增加一个random（1~100）；

最后查询一个[L,R]的区间和，如果我们每次区间修改操作都老老实实地直到每个子树都修改完才进行下次操作，我们易算出此时的极限操作单点操作次数一定有一个n*m，10^10毫无疑问超时了，我们手动在草稿纸上模拟的时候容易发现，在很多时候没必要细化修改到子树，我们在包含这些子树的根节点上标记一下，等区间查询查到它的头上的时候再把标记下放下去即可。

源码：线段树+lazy操作
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
//线段树 区间更新+区间查询 （懒标记） 
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5; 
int n,m;//n是数组长度，m是操作次数
long long a[N];//原数组
struct SegTreeNode{
	long long val;
	long long lazy;//懒标记的精髓在于，不把工作做全了（会在没完整的任务前一个根节点做标记），但是不影响大整体 ，只有下次再做统计工作，没完成的部分会影响结果的时候，以及查询具体完全情况的时候 我才完成之前没有完成的工作 
}SegTree[N<<2];//线段树
void PushUp(int rt){//合并左右子树 
	SegTree[rt].val=SegTree[rt<<1].val+SegTree[rt<<1|1].val;
}
void PushDown(int rt,int l,int r){//将懒标记下推至左右子树 
	long long mid=(l+r)/2,remain=SegTree[rt].lazy;
	SegTree[rt<<1].lazy+=remain;//左子树继承lazy标签，重点在于操作符是+=！！
	SegTree[rt<<1].val+=(mid-l+1)*remain;//更新左子树val值
	SegTree[rt<<1|1].lazy+=remain;//右子树继承lazy标签
	SegTree[rt<<1|1].val+=(r-mid)*remain;//更新右子树val值
	SegTree[rt].lazy=0;//归零根节点lazy标签
}
void build(int l,int r,int rt){//建线段树 
	SegTree[rt].lazy=0;
	if(l==r){
		SegTree[rt].val=a[l];
		return;
	} 
	else{
		long long mid=(l+r)/2;
		build(l,mid,rt<<1);
		build(mid+1,r,rt<<1|1);
		PushUp(rt);
	}
} 
void update(int L,int R,int C,int l,int r,int rt){//[L,R]区间每个点加上C，当前区间[l,r],rt; 
	if(l>=L&&r<=R){
		SegTree[rt].val+=(r-l+1)*C;
		SegTree[rt].lazy+=C;
		return ;
	}
	else if(r<L||l>R){
		return ;
	}
	else{
		if(SegTree[rt].lazy!=0){
			PushDown(rt,l,r);//！！注意在存在交叉区间的更新过程中，遇到lazy标签必须要向下推，因为如果不向下推，而绕过它去它的子树标记新的lazy，则在之后的pushup过程中，前一个lazy标签伴随的“SegTree[rt].val+=(r-l+1)*C;”会被子树合并时覆盖而消除，从而引起错误。
		}
		long long mid=(l+r)/2;
		update(L,R,C,l,mid,rt<<1);
		update(L,R,C,mid+1,r,rt<<1|1);
		PushUp(rt);
	}
}
long long  Query(int L,int R,int l,int r,int rt){//我们要询问的是从L到R,当前区间是[l,r]; 
	if(l>=L&&r<=R ){//如果当前区间被需要查询的区间包含 
		return SegTree[rt].val;
	}
	else if(r<L||l>R){
		return 0;
	}
	else{//存在交叉区间 
		long long mid=(l+r)/2;
		
		if(SegTree[rt].lazy!=0){
			PushDown(rt,l,r);
		}
	/*	long long ans=0;
		if(L<=mid)ans+=Query(L,R,l,mid,rt<<1);//需要查询的区间与当前区间的左子树有重合 
		if(mid<R) ans+=Query(L,R,mid+1,r,rt<<1|1); 
		return ans;*/
		return Query(L,R,l,mid,rt<<1)+Query(L,R,mid+1,r,rt<<1|1);
	}
	
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	build(1,n,1);
	while(m--){
		int id=0;
		scanf("%d",&id);
		if(id==1){
			long long x1,y1,k;
			scanf("%lld%lld%lld",&x1,&y1,&k);
			update(x1,y1,k,1,n,1);
		}
		else {
			int x1,y1;
			scanf("%d%d",&x1,&y1);
			printf("%lld\n",Query(x1,y1,1,n,1));
		}
	}
	return 0;
}

例题3：线段树+区间合并

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
Problem Description
Given n integers.
You have two operations:
U A B: replace the Ath number by B. (index counting from 0)
Q A B: output the length of the longest consecutive increasing subsequence (LCIS) in [a, b].

Input
T in the first line, indicating the case number.
Each case starts with two integers n , m(0<n,m<=10^5).
The next line has n integers(0<=val<=10^5).
The next m lines each has an operation:
U A B(0<=A,n , 0<=B=10^5)
OR
Q A B(0<=A<=B< n).

Output
For each Q, output the answer.

输入样例
1
10 10
7 7 3 3 5 9 9 8 1 8 
Q 6 6
U 3 4
Q 0 1
Q 0 5
Q 4 7
Q 3 5
Q 0 2
Q 4 6
U 6 10
Q 0 9
 
输出样例
1
1
4
2
3
1
2
5

LCIS:最长上升相邻子序列

源码：
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+8;
int a[N];
struct Segtreemode{
	int max1;
	int lmax;
	int rmax;
	
}segtree[N<<2];
void pushup(int l,int r,int rt){
	int mid=(l+r)/2;
	if(a[mid]>=a[mid+1]){//区间不能合并 
		segtree[rt].max1=max(segtree[rt<<1].max1,segtree[rt<<1|1].max1);
		segtree[rt].lmax=segtree[rt<<1].lmax;
		segtree[rt].rmax=segtree[rt<<1|1].rmax;
	}
	else{//可以合并 
		segtree[rt].max1=max(segtree[rt<<1].max1,max(segtree[rt<<1|1].max1,segtree[rt<<1].rmax+segtree[rt<<1|1].lmax));
		segtree[rt].lmax=segtree[rt<<1].lmax==(mid-l+1)?segtree[rt<<1].lmax+segtree[rt<<1|1].lmax:segtree[rt<<1].lmax;
		segtree[rt].rmax=segtree[rt<<1|1].rmax==(r-mid)?segtree[rt<<1|1].rmax+segtree[rt<<1].rmax:segtree[rt<<1|1].rmax;
	}
}
void build(int l,int r,int rt){
	if(l==r){
		segtree[rt].max1=segtree[rt].lmax=segtree[rt].rmax=1;
		return ;
	}
	else {
		int mid=(l+r)/2;
		build(l,mid,rt<<1);
		build(mid+1,r,rt<<1|1);
		pushup(l,r,rt);
	}
}
void update(int id,int k,int l,int r,int rt){
	if(l==r&&r==id){
		a[id]=k;
		return ;
	}
	else if(r<id||id<l){
		return ;
	}
	else{
		int mid=(l+r)/2;
		update(id,k,l,mid,rt<<1);
		update(id,k,mid+1,r,rt<<1|1);
		pushup(l,r,rt);
	}
}
int query(int l1,int r1,int l,int r,int rt){
	if(l>=l1&&r<=r1){
		return segtree[rt].max1;
	}
	else if(r<l1||l>r1){
		return 0;
	}
	else{//当当前区间和所需求的区间有重合的时候 
		int mid=(l+r)/2;
		
		int ans=0;
		int ans1=query(l1,r1,l,mid,rt<<1);
		int ans2=query(l1,r1,mid+1,r,rt<<1|1);
			ans=max(ans1,ans2);
		//if(l1<=mid)ans=max(ans,query(l1,r1,l,mid,rt<<1));
		//if(r1>mid)ans=max(ans,query(l1,r1,mid+1,r,rt<<1|1));
		
			if(a[mid]<a[mid+1]){
				ans=max(ans,min(mid-l1+1,segtree[rt<<1].rmax)+min(r1-mid,segtree[rt<<1|1].lmax));//重点！！！ 
			}
		return ans;
		
	}
}
int main(){
	int t=0;
	scanf("%d",&t);
	while(t--){
		int n,m;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
		}
			build(1,n,1);
			
		while(m--){
			char idx;
			int x1,y1;
		
			scanf(" %c%d%d",&idx,&x1,&y1);
			if(idx=='Q'){
				printf("%d\n",query(x1+1,y1+1,1,n,1));
			} 
			else{
				update(x1+1,y1,1,n,1);
			}
		}
	}
	return 0;
}

例题4：洛谷P3373线段树综合

这道题稍微有点麻烦，就是处理乘法和加法的前后顺序上。

源码：
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+8;
long long n,m,p;
long long a[N];
struct Segtreemode{
	long long val;
	long long mul;
	long long add;
}segtree[N<<2];
void pushup(int rt){
	segtree[rt].val=(segtree[rt<<1].val+segtree[rt<<1|1].val)%p; 
}
void pushdown(int l,int r,int rt){//优先乘法，之后加法  当前区间[l,r]，线段树下标rt 
	int mid=(l+r)/2;
	segtree[rt<<1].val=(segtree[rt<<1].val*segtree[rt].mul+(mid-l+1)*segtree[rt].add)%p;
	segtree[rt<<1].mul=(segtree[rt].mul*segtree[rt<<1].mul)%p;
	segtree[rt<<1].add=(segtree[rt].add+segtree[rt].mul*segtree[rt<<1].add)%p;//注意乘法优先原则，如果在乘法之前存在加法，要把加法提出来 
	segtree[rt<<1|1].val=(segtree[rt<<1|1].val*segtree[rt].mul+(r-mid)*segtree[rt].add)%p;
	segtree[rt<<1|1].mul=(segtree[rt].mul*segtree[rt<<1|1].mul)%p;
	segtree[rt<<1|1].add=(segtree[rt].add+segtree[rt].mul*segtree[rt<<1|1].add)%p;//同理 
	segtree[rt].mul=1;
	segtree[rt].add=0; 
}
void build(int l,int r,int rt){// 当前区间[l,r]，线段树下标rt
	segtree[rt].mul=1;
	segtree[rt].add=0;
	if(l==r){
		segtree[rt].val=a[l]%p;
		return ;
	}
	else{
		int mid=(l+r)/2;
		build(l,mid,rt<<1);
		build(mid+1,r,rt<<1|1);
		pushup(rt);
	}
}
void update_mul(int l1,int r1,long long c,int l,int r,int rt){//需要操作的空间[l1,r1];
	 if(l>=l1&&r<=r1){
	 	segtree[rt].val =(segtree[rt].val*c)%p;
	 	segtree[rt].mul=(segtree[rt].mul*c)%p;
	 	segtree[rt].add=(segtree[rt].add*c)%p;
	 	return ;
	 }
	 else if(l>r1||r<l1)return ;
	 int mid=(l+r)/2;
	 pushdown(l,r,rt);
	 update_mul(l1,r1,c,l,mid,rt<<1);
	 update_mul(l1,r1,c,mid+1,r,rt<<1|1);
	 pushup(rt);
}
void update_add(int l1,int r1,long long c,int l,int r,int rt){
	if(l>=l1&&r<=r1){
		segtree[rt].val=(c*(r-l+1)+segtree[rt].val)%p;
		segtree[rt].add=(segtree[rt].add+c)%p;//关键 
		return ;
	} 
	else if(l>r1||r<l1)return ;
	int mid=(l+r)/2;
	pushdown(l,r,rt);
	update_add(l1,r1,c,l,mid,rt<<1);
	update_add(l1,r1,c,mid+1,r,rt<<1|1);
	pushup(rt);
}
long long query(int l1,int r1,int l,int r,int rt){
	if(l>=l1&&r<=r1){
	 	return segtree[rt].val;
	 }
	 else if(l>r1||r<l1)return 0;
	 int mid=(l+r)/2;
	 pushdown(l,r,rt);
	 return (query(l1,r1,l,mid,rt<<1)+query(l1,r1,mid+1,r,rt<<1|1))%p;
}
int main(){
	/*freopen("C:\\Users\\yhl\\Downloads\\P3373_2.in","r",stdin);
	freopen("C:\\Users\\yhl\\Desktop\\p3373_2.out","w",stdout);*/ 
	scanf("%d%d%lld",&n,&m,&p);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	build(1,n,1);
	while(m--){
		int id=0;
		scanf("%d",&id);
		if(id==1){
			long long x,y,k;
			scanf("%d%d%lld",&x,&y,&k);
			update_mul(x,y,k,1,n,1);
		}
		else if(id==2){
			long long x,y,k;
			scanf("%d%d%lld",&x,&y,&k);
			update_add(x,y,k,1,n,1);
		}
		else{
			int x,y;
			scanf("%d%d",&x,&y);
			printf("%lld\n",query(x,y,1,n,1));
		}
	}
	return 0;
}

总结：

​ 对于区间修改和查询等操作下，线段树是一选，如果题目对内存卡的特别死，我们再考虑它的下位树状数组。