Dyd's Blog

He who has a strong enough why can bear almost any how.

线段树

Posted on Edited on In
Symbols count in article: 7.6k Reading time ≈ 7 mins.

有点久远了，有点丑

线段树

思想

对于一个区间 $[x,y]$ , 我们将其分为两个区间 : $[x,mid]$ 和 $[mid+1,y]$ , 在对这两个区间进行同样操作 , 直到无法继续 , 如图 :
例子
不难发现 , 线段树除去最后一层后 , 一定是一颗满二叉树 , 深度为 $O(\log{}{N})$ 。 所以我们用父子二倍的节点编号法:

  1. $root=1$

  2. $x$ 的左节点编号为 $x * 2$ ， 右节点编号为 $x * 2+1$

一个 $N$ 个叶节点线段数最多有 $4N$ 个节点 , 所以数组要开 $4$ 倍 。

基本实现

  • $sum$ ：当前区间的总和
  • $add$ ：懒标记，表示给以当前节点为根的子树中的每一个节点都加上 $add$ 。不难发现，为维护 $add$ ，我们用一个 $push_down()$ 来下传 $add$ 。
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<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n,m,a[N];
struct ST{
	ll sum,add;
	int l,r;
}tr[N*4];
void push_down(int u){
	if(tr[u].add){
		tr[u<<1].add+=tr[u].add;
		tr[u<<1].sum+=(ll)(tr[u<<1].r-tr[u<<1].l+1)*tr[u].add;
		tr[u<<1|1].add+=tr[u].add;
		tr[u<<1|1].sum+=(ll)(tr[u<<1|1].r-tr[u<<1|1].l+1)*tr[u].add;
		tr[u].add=0;
	}
	return ;
}
void push_up(int u){
	tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
	return ;
}
void build(int u,int l,int r){
	if(l==r){
		tr[u].l=l,tr[u].r=r;
		tr[u].sum=a[r];
		tr[u].add=0;
	}
	else{
		tr[u].l=l,tr[u].r=r;
		int mid=l+r>>1;
		build(u<<1,l,mid),build(u<<1|1,mid+1,r);
		push_up(u);
	}
	return ;
}
void modify(int u,int l,int r,int d){
	if(tr[u].l>=l&&tr[u].r<=r){
		tr[u].sum+=(ll)(tr[u].r-tr[u].l+1)*d;
		tr[u].add+=d;
	}
	else{
		push_down(u);
		int mid=tr[u].l+tr[u].r>>1;
		if(l<=mid) modify(u<<1,l,r,d);
		if(r>mid) modify(u<<1|1,l,r,d);
		push_up(u);
	}
	return ;
}
ll ask(int u,int l,int r){
	if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum;
	push_down(u);
	int mid=tr[u].l+tr[u].r>>1;
	ll as=0;
	if(l<=mid) as+=ask(u<<1,l,r);
	if(r>mid) as+=ask(u<<1|1,l,r);
	return as;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	build(1,1,n);
	while(m--){
    	char op[2];
    	int l,r,d;
        scanf("%s",op);
        if(op[0]=='C'){
            scanf("%d%d%d",&l,&r,&d);
            modify(1,l,r,d);
        }
        else{
            scanf("%d%d",&l,&r);
            printf("%lld\n",ask(1,l,r));
        } 
    }
	return 0;
}

应用1——扫描线

P5490 【模板】扫描线 

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+5;
ll n;
vector<ll>ys;
struct Segment{
	ll k;
	ll x,yl,yr;
	bool operator<(const Segment &t) const{
		return x<t.x;
	}
	void init(ll _x,ll _yl,ll _yr,ll _k){
		x=_x;
		yl=_yl;
		yr=_yr;
		k=_k;
	}
}seg[N*2];
struct LineTree{
	ll l,r;
	ll cnt;
	ll len;
	void init(ll _l,ll _r,ll _cnt,ll _len){
		l=_l;
		r=_r;
		cnt=_cnt;
		len=_len;
	}
}tr[N*8];
ll find(ll y){
	//lower_bound()函数用于在指定区域内查找不小于目标值的第一个元素。
	return lower_bound(ys.begin(),ys.end(),y)-ys.begin();
}
void push_up(ll u){
	if(tr[u].cnt) tr[u].len=ys[tr[u].r+1]-ys[tr[u].l];
	else if(tr[u].l!=tr[u].r)
		tr[u].len=tr[u<<1].len+tr[u<<1|1].len;
	else tr[u].len=0;
	return ;
}
void build(ll u,ll l,ll r){
	tr[u].init(l,r,0,0);
	if(l!=r){
		ll mid=l+r>>1;
		build(u<<1,l,mid),build(u<<1|1,mid+1,r);
	}
	return ;
}
void modify(ll u,ll l,ll r,ll k){
	if(tr[u].l>=l&&tr[u].r<=r){
		tr[u].cnt+=k;
		push_up(u);
	}
	else{
		ll mid=tr[u].l+tr[u].r>>1;
		if(l<=mid) modify(u<<1,l,r,k);
        if(r>mid) modify(u<<1|1,l,r,k);
        push_up(u);
	}
	return ;
}
int main(){
	scanf("%lld",&n);
	ys.clear();
	for(ll i=0,j=0;i<n;++i){
		ll xr,xl,yr,yl;
		scanf("%lld%lld%lld%lld",&xl,&yl,&xr,&yr);
		seg[j++].init(xl,yl,yr,1);
		seg[j++].init(xr,yl,yr,-1);
		ys.push_back(yl),ys.push_back(yr);
	}
	sort(ys.begin(),ys.end());
	//unique函数功能是去除相邻的重复元素
	//它并不真正把重复的元素删除,而是将无重复的元素复制到序列的前段,
	//从而覆盖相邻的重复元素.unique返回的迭代器指向超出无重复的元素范围末端的下一个位置.
	//erase:删除
	ys.erase(unique(ys.begin(),ys.end()),ys.end());
	build(1,0,ys.size()-2);
	sort(seg,seg+n*2);
	ll res=0;
	for(ll i=0;i<n*2;++i){
		if(i>0) res+=tr[1].len*(seg[i].x-seg[i-1].x);
		modify(1,find(seg[i].yl),find(seg[i].yr)-1,seg[i].k);
	}
	printf("%lld\n",res);
	return 0;
}

代码

以下是一个维护最值的线段树的修改操作

1
2
3
4
5
6
7
8
9
10
   //单点修改,将[x,x]的值改为z
void Modify(int p,int x,int z){
	if(l[p]==r[p]) dmax[p]=z,return ;
	int mid=(l[p]+r[p])>>1;
	if(x<=mid) Modify(p<<1,x,z);
	if(y>mid) Modify(p<<|1,x,z);
	//从下往上跟新信息,也叫push_up 
	dmax[p]=max(dmax[p<<1],dmax[p<<1|1]);
} 
   //调用入口: st.Modify(1,x,z);

以下是一个维护区间和的线段树，支持区间增加，区间乘法

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
//洛谷P3373 
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,a[N],mod;
struct ST{		//SegmentTree
	long long dat[N*4];		//维护区间和
	int l[N*4],r[N*4];		//区间 
	long long add[N*4],mul[N*4];			//懒惰标记(lazytag) 
	//建立区间ll-rr,编号为p 
	void Build(int p,int ll,int rr){
		//初始化lazytag 
		add[p]=0;
		mul[p]=1; 
		l[p]=ll;r[p]=rr;			//以p为编号的节点维护的区间为ll到rr
		//ll==rr的话,这个区间就只有一个数,直接让区间维护的值等于a[ll]
		if(ll==rr)
			dat[p]=a[ll];
		//否则维护的值等于左儿子加右儿子
		else{			
			int mid=(ll+rr)>>1;
			Build(p<<1,ll,mid);
			Build(p<<1|1,mid+1,rr);
			dat[p]=dat[p<<1]+dat[p<<1|1];		//当然,具体的维护视题目而定
		}
		dat[p]%=mod; 
		return ;
	}
	//懒惰标记,规定乘法优先
	void Spread(int p){
		//如果懒标记不为0,就将其下传,修改左右儿子维护的值 
		if(add[p]!=0||mul[p]!=1){
			//根据我们规定的优先度,儿子的值=
			//此刻儿子的值*爸爸的乘法lazytag+
			//儿子的区间长度*爸爸的加法lazytag
			dat[p<<1]=(dat[p<<1]*mul[p]+add[p]*(r[p<<1]-l[p<<1]+1))%mod;
			dat[p<<1|1]=(dat[p<<1|1]*mul[p]+add[p]*(r[p<<1|1]-l[p<<1|1]+1))%mod;
			//为该节点的左右儿子打上标记,
			mul[p<<1]=(mul[p<<1]*mul[p])%mod;
			mul[p<<1|1]=(mul[p<<1|1]*mul[p])%mod; 
			//由于乘法优先,加法打标记时要先乘一下 
			add[p<<1]=(add[p<<1]*mul[p]+add[p])%mod;
			add[p<<1|1]=(add[p<<1|1]*mul[p]+add[p])%mod;
			//下传之后将父节点的懒标记清0
			mul[p]=1;
			add[p]=0; 
		}
		return ;
	} 
	//区间修改,将区间[x,y]都加上z 
	void Change_add(int p,int x,int y,int z){
		if(x<=l[p]&&y>=r[p]){		//被覆盖的话,就对其进行修改
			dat[p]+=(long long)z*(r[p]-l[p]+1);
			dat[p]%=mod;
			add[p]=(add[p]+z)%mod;		//打上懒标记
			return ;
		}
		//如果没有被覆盖,就继续向下找,但儿子所维护的区间可能因为
		//懒标记的存在而没有修改,因此将懒标记下放
		Spread(p);
		int mid=(l[p]+r[p])>>1;
		if(x<=mid) Change_add(p<<1,x,y,z);//如果要修改的区间覆盖了左儿子
		if(y>mid) Change_add(p<<1|1,x,y,z);//右儿子同理
		//维护值
		dat[p]=(dat[p<<1]+dat[p<<1|1])%mod;
		return ; 
	}
	//区间修改,将区间[x,y]都乘上z
	void Change_mul(int p,int x,int y,int z){
		if(x<=l[p]&&y>=r[p]){
			dat[p]=(dat[p]*z)%mod;
			mul[p]=(mul[p]*z)%mod;
			//乘法优先,故加法标记也要乘
			add[p]=(add[p]*z)%mod;
			return ; 
		}
		//否则同加法,向下找
		Spread(p);
		int mid=(l[p]+r[p])>>1;
		if(x<=mid) Change_mul(p<<1,x,y,z);
		if(y>mid) Change_mul(p<<1|1,x,y,z);
		dat[p]=(dat[p<<1]+dat[p<<1|1])%mod;
		return ;
	} 
	//区间查询,查询[x,y]的和 
	long long Ask(int p,int x,int y){
		if(x<=l[p]&&y>=r[p]) return dat[p];//如果被覆盖，就返回维护的值
		//下传懒标记，并查询左右儿子
		Spread(p);
		int mid=(l[p]+r[p])>>1;
		long long ans=0;
		if(x<=mid) ans=(ans+Ask(p<<1,x,y))%mod;
		if(y>mid) ans=(ans+Ask(p<<1|1,x,y));
		return ans%mod;
	} 
}st;
int main(){
	scanf("%d%d%d",&n,&m,&mod);
	for(int i=1;i<=n;++i)
		scanf("%d",&a[i]);
	st.Build(1,1,n); 
	while(m--){
		int q,x,y,z;
		scanf("%d",&q);
		if(q==1){
			scanf("%d%d%d",&x,&y,&z);
			st.Change_mul(1,x,y,z);
		}
		else if(q==2){
			scanf("%d%d%d",&x,&y,&z);
			st.Change_add(1,x,y,z);
		} 
		else{
			scanf("%d%d",&x,&y);
			printf("%lld\n",st.Ask(1,x,y));
		}
	}
	return 0;
}
//注：打线段树的时候一定要注意两端取等 
//如51行两端取等，61、62行单边取等