0%

浅谈线段树

目录

1.线段树是什么?有什么用?

2.线段树的思想

3.浅谈懒标记

4.线段树的应用

5.线段树的进阶

线段树是什么?有什么用?

关于线段树,它长这样:

如图,图片中每个节点都是区间,区间可以有权值,可以进行区间操作,如:
区间和
区间最大子段和
区间最大/最小值
区间修改
每次操作可以达到logn的时间。

线段树的思想

看了线段树,有没有感觉熟悉?没错,这就是分块的思想。

线段树的实现

1.建树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void build(int l,int r,int rt)
{
if(l==r)
{
sum[rt]=a[l];//这里是要维护的变量,赋值,因为l==r,所以这是叶子节点,可以直接赋值,你要维护几个变量,你就赋值几个变量
return;
}
int mid=(l+r)>>1;//中位值
build(l,mid,rt<<1);//建左儿子rt<<1=rt*2
build(mid+1,r,rt<<1|1);//建右儿子rt<<1|1=rt*2+1
sum[rt]=sum[rt<<1]+sum[rt<<1|1];//这里也是维护的变量,sum[rt]=sum[rt的左儿子]+sum[rt的右儿子]
/*
同理,这里还可以维护其他的变量,如:区间最大值[rt]=max(左区间最大值,右区间最大值);
最小值一样
*/
}

2.区间修改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void update(int l,int r,int rt,int i,int j,int k)//将[i,j]内的数加上k
{
if(l==r)//到叶子节点,修改
{
sum[rt]+=k;
return ;
}
int mid=(l+r)>>1;
if(i<=mid)//i<=mid,这样就代表[l,mid]内的区间有要修改的
update(l,mid,rt<<1,i,j,k);
if(mid<j)//mid<j,这要就代表[mid+1,r]内的区间有要修改的
update(mid+1,r,rt<<1|1,i,j,k);
sum[rt]=sum[rt<<1]+sum[rt<<1|1]//更新;
}

3.区间求和

1
2
3
4
5
6
7
8
9
10
11
12
int query(int l,int r,int rt,int i,int j)//查询[i,j]区间求和
{
if(l>=i&&r<=j)//如果这是在要求和的区间
{
return sum[rt];//返回区间和
}
int mid=(l+r)>>1;
int ans=0;//答案
if(i<=mid)ans+=query(l,mid,rt<<1,i,j);//在左边
if(mid<j)ans+=query(mid+1,r,rt<<1|1,i,j);//在右边
return ans;
}

4.完整代码

题目

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>
#define ll long long
using namespace std;
const ll n=1e5+10;
ll nn,m,a[n];
ll sum[n<<2],ma[n<<2];
void build(ll l,ll r,ll rt)
{
if(l==r)
{
sum[rt]=a[l];
ma[rt]=sum[rt];
return;
}
ll mid=(l+r)>>1;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
ma[rt]=max(ma[rt<<1],ma[rt<<1|1]);
}
int read(){
int s=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=s*10+ch-'0';
ch=getchar();
}
return s*f;
}
void update(ll l,ll r,ll rt,ll i,ll j)
{
if(ma[rt]<=1)return;
if(l==r)
{
sum[rt]=sqrt(sum[rt]);
ma[rt]=sum[rt];
return;
}
ll mid=(l+r)>>1;
if(mid>=i)update(l,mid,rt<<1,i,j);
if(mid<j)update(mid+1,r,rt<<1|1,i,j);
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
ma[rt]=max(ma[rt<<1],ma[rt<<1|1]);
}
ll query(ll l,ll r,ll rt,ll i,ll j)
{
if(l>=i&&r<=j)
return sum[rt];
ll mid=(l+r)>>1;
ll ans=0;
if(i<=mid)ans+=query(l,mid,rt<<1,i,j);
if(mid<j)ans+=query(mid+1,r,rt<<1|1,i,j);
return ans;
}
int main(){
nn=read();
for(ll i=1;i<=nn;i++)
cin>>a[i];
build(1,nn,1);
m=read();
for(ll i=1;i<=m;i++)
{
ll c,x,y;
cin>>c>>x>>y;
if(x>y)
swap(x,y);
if(c==0)
{
update(1,nn,1,x,y);
}
else
cout<<query(1,nn,1,x,y)<<endl;
}
return 0;
}

浅谈懒标记

看了这个代码,思考,怎么优化?
当然用懒标记了。
懒标记的思想:
区间修改时,不到单点,到区间,只修改当前值,接下来把标记传下去,左右儿子加上,下次遍历到时再重复操作,把标记传下去。

核心操作:

1
2
3
4
5
6
7
8
9
10
void pushdown(LL l,LL r,LL rt){
if(lazy[rt]){
LL mid=(l+r)>>1;
lazy[rt<<1]+=lazy[rt];//传到左儿子,右儿子
lazy[rt<<1|1]+=lazy[rt];
sum[rt<<1]+=(mid-l+1)*lazy[rt];//mid-l+1=区间有几个数,(mid-l+1)*lazy为加上区间内所有需要加的数
sum[rt<<1|1]+=(r-mid)*lazy[rt];//同上
lazy[rt]=0;//传下去了,就不需要了
}
}

代码

题目

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
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
#define LL long long

const int M=100005;
LL n,m,a[4*M],sum[4*M],lazy[4*M];
void pushdown(LL l,LL r,LL rt){
if(lazy[rt]){
LL mid=(l+r)>>1;
lazy[rt<<1]+=lazy[rt];
lazy[rt<<1|1]+=lazy[rt];
sum[rt<<1]+=(mid-l+1)*lazy[rt];
sum[rt<<1|1]+=(r-mid)*lazy[rt];
lazy[rt]=0;
}

}
void build(LL l,LL r,LL rt){ //建立
if(l==r){
sum[rt]=a[l];
return;
}
LL mid=(l+r)>>1;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void add(LL l,LL r,LL rt,LL x,LL y,LL k){ //修改
if(x<=l&&y>=r){
sum[rt]+=k*(r-l+1);
lazy[rt]+=k;

return;
}
LL mid=(l+r)>>1;
pushdown(l,r,rt);
if(x<=mid)add(l,mid,rt<<1,x,y,k);
if(y>mid)add(mid+1,r,rt<<1|1,x,y,k);

sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
LL query(LL l,LL r,LL rt,LL x,LL y){ //查询
if(l>=x&&r<=y){
return sum[rt];
}
pushdown(l,r,rt);
LL mid=(l+r)>>1;
LL s=0;
if(mid>=x) s=s+query(l,mid,rt<<1,x,y);
if(mid<y)s=s+query(mid+1,r,rt<<1|1,x,y);
return s;

}
int main(){
LL x,y,k,c;
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
build(1,n,1);
for(int i=1;i<=m;i++){
cin>>c;
if(c==1){
cin>>x>>y>>k;
add(1,n,1,x,y,k);
}
else{
cin>>x>>y;
cout<<query(1,n,1,x,y)<<endl;
}
}
return 0;
}

线段树的应用

题目

分析:

经典的线段树题目,套模板就行了,只要注意一下懒标记就行了,简单的区间修改区间求和。

代码(不加注释,前面讲了,代码仅供参考)

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
#include<bits/stdc++.h>
#define inf 2147283647
using namespace std;
const int maxn=300005;
int n,m,lazy[maxn<<2],sum[maxn<<2];
void pushup(int rt)
{
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void pushdown(int rt,int l)
{
if(lazy[rt])
{
lazy[rt<<1]^=1;
lazy[rt<<1|1]^=1;
sum[rt<<1]=(l-(l>>1))-sum[rt<<1];
sum[rt<<1|1]=(l>>1)-sum[rt<<1|1];
lazy[rt]=0;
}
}
void update(int l,int r,int rt,int i,int j)
{
pushdown(rt,r-l+1);
if(i<=l&&r<=j)
{
lazy[rt]^=1;
sum[rt]=r-l+1-sum[rt];
return;
}
int mid=l+r>>1;
if(i<=mid)
update(l,mid,rt<<1,i,j);
if(mid<j)
update(mid+1,r,rt<<1|1,i,j);
pushup(rt);
}

int query(int l,int r,int rt,int i,int j)
{
pushdown(rt,r-l+1);
if(l>=i&&r<=j)
{
return sum[rt];
}
int mid=(l+r)>>1;
int ans=0;
if(i<=mid)ans+=query(l,mid,rt<<1,i,j);
if(mid<j)ans+=query(mid+1,r,rt<<1|1,i,j);
return ans;
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int c,a,b;
cin>>c>>a>>b;
if(c==0)
update(1,n,1,a,b);
else
cout<<query(1,n,1,a,b)<<endl;
}
return 0;
}

题目

分析 :

简单的单点修改+区间查询,懒操作不需要,修改时要特判一下

代码:

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
#include<bits/stdc++.h>
#define inf 2147283647
using namespace std;
const int maxn=200005;
int n,m,ma[maxn<<2],a[maxn];
void build(int l,int r,int rt)
{
if (l==r)
{
ma[rt]=a[l];
return;
}
int mid=(l+r)>>1;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
ma[rt]=max(ma[rt<<1],ma[rt<<1|1]);
}
void update(int l,int r,int rt,int i,int j)
{
if(l==r)
{
if(ma[rt]<=j)//特判
ma[rt]=j;
return;
}
int mid=(l+r)>>1;
if(i<=mid)//单点修改,运用二分思想
update(l,mid,rt<<1,i,j);
else
update(mid+1,r,rt<<1|1,i,j);
ma[rt]=max(ma[rt<<1],ma[rt<<1|1]);
}
int query(int l,int r,int rt,int i,int j)
{
if(i<=l&&r<=j)
return ma[rt];
int mid=(l+r)>>1,mx=-2147283647;
if(i<=mid)mx=query(l,mid,rt<<1,i,j);
if(j>mid)
mx=max(mx,query(mid+1,r,rt<<1|1,i,j));
return mx;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
build(1,n,1);
for(int i=1;i<=m;i++)
{
char a;
cin>>a;
int x,y;
cin>>x>>y;
if(a=='Q')
cout<<query(1,n,1,x,y)<<endl;
else
update(1,n,1,x,y);
}
return 0;
}

例题

题目1

分析:维护两个值,最大数和区间和,如果区间最大数≤1,就不需要修改了,因为sqrt(1)=1。

题目2

分析:维护最小值就行了

题目3

分析:预处理出D,然后区间修改+求和,维护区间和和最大值,如果最大值≤2就不需要修改了,因为D(2)=2,D(1)=1。

题目4

分析:区间求和+区间取模+单点修改,维护区间和和最大值,如果最大值<要取模的值,就不修改了。

线段树的进阶

线段树还可以求区间最大子段和= =,但比较难,可以选择性学习。
分析:
我们要维护四个变量
s:区间内的最大子段和
l:紧靠左端点的最大子段和
r:紧靠右端点的最大子段和
sum:区间和(好像不要维护??)
现在有一个问题,如何维护?
s有三种情况:
1.s是左儿子的s
2.s是右儿子的s
3.s是左儿子的r+右儿子的l。
l有两种情况:
1.l=左儿子的l
2.l=左儿子的s+右儿子的ls
r有两种情况:
1.r=右儿子的r
2.r=右儿子的s+左儿子的rs
看了上面,得出pushup:

1
2
3
4
5
6
7
8
void pushup(int rt)
{
tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
tree[rt].l=max(tree[rt<<1].l,tree[rt<<1].sum+tree[rt<<1|1].l);
tree[rt].r=max(tree[rt<<1|1].r,tree[rt<<1|1].sum+tree[rt<<1].r);
tree[rt].s=max(max(tree[rt<<1].s,tree[rt<<1|1].s),tree[rt<<1].r+tree[rt<<1|1].l;
return;
}

接下来,右有一个难点,怎么查询
[l,r]的区间最大子段和有以下几种情况
1.独立的存在于左儿子或右儿子中
2.左儿子的r+右儿子的l
然而如果[l,r]在线段树中是一个节点(单独维护过),直接return s就

代码:

题目

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
#include<bits/stdc++.h>
#define inf 2147283647
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
using namespace std;
const int maxn=50005;
struct node{
int sum,l,r,s;
}tree[maxn<<2];
int a[maxn];
void pushup(int rt)
{
tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
tree[rt].l=max(tree[rt<<1].l,tree[rt<<1].sum+tree[rt<<1|1].l);
tree[rt].r=max(tree[rt<<1|1].r,tree[rt<<1|1].sum+tree[rt<<1].r);
tree[rt].s=max(max(tree[rt<<1].s,tree[rt<<1|1].s),tree[rt<<1].r+tree[rt<<1|1].l);
return;
}
void build(int l,int r,int rt)
{
if(l==r)
{
tree[rt].l=tree[rt].r=tree[rt].s=tree[rt].sum=a[l];
return ;
}
int mid=(l+r)>>1;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
pushup(rt);
}
node query(int l,int r,int rt,int i,int j)
{
if(i<=l&&j>=r)//完全包含
return tree[rt];
int mid=(l+r)>>1;
node l1,l2,ans;
ans.s=0;
if(j<=mid)ans=query(lson,i,j);//全在左儿子
if(i>mid)//全在右儿子
ans=query(rson,i,j);
if(i<=mid&&j>mid){
l1=query(lson,i,j);//左儿子
l2=query(rson,i,j);//右儿子
ans.sum=l1.sum+l2.sum;
ans.l=max(l1.l,l1.sum+l2.l);//取最大,同上所述的情况
ans.r=max(l2.r,l2.sum+l1.r);
ans.s=max(max(l1.s,l2.s),l1.r+l2.l);
}
return ans;
}
int main(){
int n,m;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
build(1,n,1);
cin>>m;
for(int i=1;i<=m;i++)
{
int l,r;
cin>>l>>r;
cout<<query(1,n,1,l,r).s<<endl;
}
return 0;
}

好了,就讲到这里了,试试刷了这道题这道题

写个文章不容易,求给个评论= =

欢迎打赏~.