0%

浅谈线段树

发表于 分类于 Valine：
点阅读全文查看哦~

目录

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;
}

好了，就讲到这里了，试试刷了这道题和这道题

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

欢迎打赏~.