0%

线段树

发表于 更新于 Valine：
本文字数： 6.7k 阅读时长 ≈ 11 分钟

线段树模板
线段树是处理符合结合律的高效数据结构；
线段树专门处理区间问题的；
线段树的每个节点都表示一个区间，当l==r的时候，意味着区间长度为1，也就是表元素；
线段是是一颗完全二叉树，即每个节点要么是叶子节点要么就有两个孩子节点。

线段树模板题

递归建树：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

ll lc(ll x) {return x<<1;}      //左孩子
ll rc(ll x) {return x<<1|1;}    //右孩子

void push_up(ll p)
{
    tree[p]=tree[lc(p)]+tree[rc(p)];            //这是维护区间和的线段树，维护区间最大最小值的类似；
    //tree[p]=min(tree[lc(p)],tree[rc(p)]); //维护区间最小值
}

void build(ll p,ll l,ll r)              
{
    tag[p]=0;                               //tag标记，先不管，下面讲
    if(l==r){
        tree[p]=a[l];
        return;
    }
    ll mid=(l+r)>>1;
    build(lc(p),l,mid);                     //递归左子树
    build(rc(p),mid+1,r);                   //递归右子树
    push_up(p);                             //回溯时，维护父节点
}

区间修改

单点修改是区间修改的子问题，也就是修改区间长度为1的区间。放在一起谈。
对于区间修改，我们需要引用一个tag标记；
原因：当修改区间的一个元素时，它就需要push_up来更新它的父节点，时间复杂度O(nlogn)，这很低效，当我们引入tag标记时，则可以使区间更新接近O(logn);

tag标记

当某个区间被修改时，就给这个区间打上标记,当用到这个区间的子区间的时候，我们才从父节点往子节点下传更新值.来看一下代码:

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
void fun(ll p,ll l,ll r,ll k)    // p表示该节点，[l,r]表示该节点表示的区间，k表示增量
{
    tag[p]=tag[p]+k;            //记录增量
    tree[p]=tree[p]+(r-l+1)*k;  //更新当前节点的值，因为符合结合律，所以直接可以计算得
}
void push_down(ll p,ll l,ll r)      //下传tag标记
{
    ll mid=(l+r)>>1;                
    fun(lc(p),l,mid,tag[p]);           //下传给左孩子
    fun(rc(p),mid+1,r,tag[p]);          //下传给右孩子
    tag[p]=0;                       //下传完，恢复标记
}

void update(ll nl,ll nr,ll p,ll l,ll r,ll k)        //区间修改，[nl,nr]表示修改的区间，p表示该区间的节点，[l,r]表示该节点表示的区间，k表示增量
{
    if(nl<=l&&r<=nr)            //当需要修改的区间完全覆盖当前区间，我们就给该区间打上tag标记，并且更新一下该节点的值
    {
        tag[p]+=k;
        tree[p]+=(r-l+1)*k;
        return;
    }
    if(tag[p]!=0) push_down(p,l,r);             //没有完全覆盖则需要继续找，如果当前节点有tag标记，说明它的孩子节点没有被更新，我们要先下放tag标记
    ll mid=(l+r)>>1;
    if(nl<=mid)update(nl,nr,lc(p),l,mid,k);     //更新左子树
    if(nr>mid)update(nl,nr,rc(p),mid+1,r,k);    //更新右子树
    push_up(p);                                 //回溯时，维护父节点
}

区间查询

1
2
3
4
5
6
7
8
9
10
ll query(ll nl,ll nr,ll p,ll l,ll r)
{
    ll res=0;
    if(nl<=l&&r<=nr) return tree[p];                    //当查询的区间已经完全包括该区间时，直接return
    if(tag[p]!=0) push_down(p,l,r);                     //如果标记不为0,则说明该区间有修改，需要push_down传递给子节点，且需要在递归子节点前！！！
    ll mid=(l+r)>>1;
    if(nl<=mid)res+=query(nl,nr,lc(p),l,mid);           //递归左孩子
    if(nr>mid) res+=query(nl,nr,rc(p),mid+1,r);         //递归右孩子
    return res;
}

完整代码：

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
#include<cstdio>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAX_N=1e6+5;
ll tree[MAX_N<<2];          //线段树的节点，因为从树顶往下建树，所以需要4N的大小；
ll a[MAX_N];                //存原数组
ll tag[MAX_N<<2];           //标记
ll N,M;
ll lc(ll x) {return x<<1;}      
ll rc(ll x) {return x<<1|1;}    
void push_up(ll p)
{
    tree[p]=tree[lc(p)]+tree[rc(p)];          
}
void fun(ll p,ll l,ll r,ll k)
{
    tag[p]=tag[p]+k;
    tree[p]=tree[p]+(r-l+1)*k;
}
void push_down(ll p,ll l,ll r)
{
    ll mid=(l+r)>>1;
    fun(lc(p),l,mid,tag[p]);
    fun(rc(p),mid+1,r,tag[p]);
    tag[p]=0;
}
void build(ll p,ll l,ll r)              //递归建树
{
    tag[p]=0;
    if(l==r){
        tree[p]=a[l];
        return;
    }
    ll mid=(l+r)>>1;
    build(lc(p),l,mid);
    build(rc(p),mid+1,r);
    push_up(p);
}
ll query(ll nl,ll nr,ll p,ll l,ll r)
{
    ll res=0;
    if(nl<=l&&r<=nr) return tree[p];
    if(tag[p]!=0) push_down(p,l,r);
    ll mid=(l+r)>>1;
    if(nl<=mid)res+=query(nl,nr,lc(p),l,mid);
    if(nr>mid) res+=query(nl,nr,rc(p),mid+1,r);
    return res;
}
void update(ll nl,ll nr,ll p,ll l,ll r,ll k)
{
    if(nl<=l&&r<=nr)
    {
        tag[p]+=k;
        tree[p]+=(r-l+1)*k;
        return;
    }
    if(tag[p]!=0) push_down(p,l,r);
    ll mid=(l+r)>>1;
    if(nl<=mid)update(nl,nr,lc(p),l,mid,k);
    if(nr>mid)update(nl,nr,rc(p),mid+1,r,k);
    push_up(p);
}

int main() {

   scanf("%lld%lld",&N,&M);
   for(int i=1;i<=N;i++) scanf("%lld",&a[i]);
   build(1,1,N);
   while(M--)
   {
       ll b;
       scanf("%lld",&b);
       if(b==1)
       {
           ll x,y,z;
           scanf("%lld%lld%lld",&x,&y,&z);
           update(x,y,1,1,N,z);

       }
       else
       {
           ll x,y;
           scanf("%lld%lld",&x,&y);
           printf("%lld\n",query(x,y,1,1,N));
       }
   }
	return 0;
}

线段树模板2:
如题，已知一个数列，你需要进行下面三种操作：

1.将某区间每一个数乘上x

2.将某区间每一个数加上x

3.求出某区间每一个数的和
传送门
设置两个lazytag，一个存加法，一个存乘法

push_down操作的时候，人为的给这两个lazytag规定先后顺序

乘法优先：
tree[lc(p)]=(tree[lc(p)]mul[p]+add[p](mid-l+1));
tree[rc(p)]=(tree[rc(p)]mul[p]+add[p](r-mid));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void push_down(ll p,ll l,ll r)
{
    ll mid=(l+r)>>1;
    tree[lc(p)]=(tree[lc(p)]*mul[p]+add[p]*(mid-l+1))%PP;   
    tree[rc(p)]=(tree[rc(p)]*mul[p]+add[p]*(r-mid))%PP;

    mul[lc(p)]=(mul[lc(p)]*mul[p])%PP;
    mul[rc(p)]=(mul[rc(p)]*mul[p])%PP;

    add[lc(p)]=(add[lc(p)]*mul[p]+add[p])%PP;
    add[rc(p)]=(add[rc(p)]*mul[p]+add[p])%PP;

    add[p]=0;
    mul[p]=1;
}
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAX_N=1e5+5;
ll N,M,PP;
ll tree[MAX_N<<2];
ll add[MAX_N<<2];
ll mul[MAX_N<<2];
ll a[MAX_N];
ll lc(ll x){return x<<1;}
ll rc(ll x){return x<<1|1;}
void push_up(ll p)
{
    tree[p]=(tree[lc(p)]+tree[rc(p)])%PP;
}
void build(ll p,ll l,ll r)
{
    add[p]=0;
    mul[p]=1;
    if(l==r)
    {
        tree[p]=a[l];
        return;
    }
    ll mid=(l+r)>>1;
    build(lc(p),l,mid);
    build(rc(p),mid+1,r);
    push_up(p);
}
void push_down(ll p,ll l,ll r)
{
    ll mid=(l+r)>>1;
    tree[lc(p)]=(tree[lc(p)]*mul[p]+add[p]*(mid-l+1))%PP;
    tree[rc(p)]=(tree[rc(p)]*mul[p]+add[p]*(r-mid))%PP;

    mul[lc(p)]=(mul[lc(p)]*mul[p])%PP;
    mul[rc(p)]=(mul[rc(p)]*mul[p])%PP;

    add[lc(p)]=(add[lc(p)]*mul[p]+add[p])%PP;
    add[rc(p)]=(add[rc(p)]*mul[p]+add[p])%PP;

    add[p]=0;
    mul[p]=1;
}
void update1(ll nl,ll nr,ll p,ll l,ll r,ll k)
{
    if(nl<=l&&r<=nr)
    {
        tree[p]=(tree[p]*k)%PP;
        add[p]=(add[p]*k)%PP;
        mul[p]=(mul[p]*k)%PP;
        return;
    }
    push_down(p,l,r);
    ll mid=(l+r)>>1;
    if(nl<=mid) update1(nl,nr,lc(p),l,mid,k);
    if(mid<nr) update1(nl,nr,rc(p),mid+1,r,k);
    push_up(p);
}
void update2(ll nl,ll nr,ll p,ll l,ll r,ll k)
{
    if(nl<=l&&r<=nr)
    {
        tree[p]=(tree[p]+k*(r-l+1))%PP;
        add[p]=(add[p]+k)%PP;
        return;
    }
    push_down(p,l,r);
    ll mid=(l+r)>>1;
    if(nl<=mid) update2(nl,nr,lc(p),l,mid,k);
    if(mid<nr) update2(nl,nr,rc(p),mid+1,r,k);
    push_up(p);
}
ll query(ll nl,ll nr,ll p,ll l,ll r)
{
    ll res=0;
    if(nl<=l&&r<=nr)
    {
        return tree[p];
    }
    push_down(p,l,r);
    ll mid=(l+r)>>1;
    if(nl<=mid) res=(res+query(nl,nr,lc(p),l,mid))%PP;
    if(mid<nr) res=(res+query(nl,nr,rc(p),mid+1,r))%PP;
    return res%PP;
}
int main() {
    //scanf("%d%d%d",&N,&M,&P);
    cin>>N>>M>>PP;
    for(ll i=1;i<=N;i++) cin>>a[i];//scanf("%d",&a[i]);
    build(1,1,N);
    while(M--)
    {
        ll op,l,r,k;
        cin>>op>>l>>r;
        //scanf("%d%d%d",&op,&l,&r);
        if(op==1)
        {
            cin>>k;
            //scanf("%d",&k);
            update1(l,r,1,1,N,k);
        }
        else if(op==2)
        {
            cin>>k;
            //scanf("%d",&k);
            update2(l,r,1,1,N,k);
        }
        else
        {
            ll ans=query(l,r,1,1,N);
            ans%=PP;
           // printf("%d\n",ans);
           cout<<ans<<endl;
        }
    }
    return 0;
}
-------------本文结束感谢您的阅读-------------