【模板】线段树

【模板】线段树

一.最基础的线段树：支持区间加减修改，区间查询。

　　其实两个差分树状数组也可以搞定这个事情，不过还是线段树这样更加直观一点。

　　建议初步接触线段树的同学先看主程序再看函数，然后有需要可以手动模拟一下，有助于理解每个函数的作用~

#include<bits/stdc++.h>
using namespace std;
struct SegTree
{int l,r;long long sum,Lazy;
}Tree[400040];
int n,m,x,y,z,opt;
long long a[100010];void push_up(int k)
{Tree[k].sum=Tree[k<<1].sum+Tree[k<<1|1].sum;
}
void Build(int k,int l,int r)
{Tree[k].l=l;Tree[k].r=r;if(l==r){Tree[k].sum=a[l];return;}int mid=l+r>>1;Build(k<<1,l,mid);Build(k<<1|1,mid+1,r);push_up(k);
}
void push_down(int k)
{if(Tree[k].Lazy){Tree[k<<1].sum+=Tree[k].Lazy*(Tree[k<<1].r-Tree[k<<1].l+1);Tree[k<<1].Lazy+=Tree[k].Lazy;Tree[k<<1|1].sum+=Tree[k].Lazy*(Tree[k<<1|1].r-Tree[k<<1|1].l+1);Tree[k<<1|1].Lazy+=Tree[k].Lazy;Tree[k].Lazy=0;}
}
void update(int k,int L,int R,long long val)
{    push_down(k);if(L<=Tree[k].l && Tree[k].r<=R){Tree[k].sum+=val*(Tree[k].r-Tree[k].l+1);Tree[k].Lazy+=val;return;}int mid=Tree[k].l+Tree[k].r>>1;if(L<=mid) update(k<<1,L,R,val);if(R>mid) update(k<<1|1,L,R,val);push_up(k);
}
long long Query(int k,int L,int R)
{if(L<=Tree[k].l && Tree[k].r<=R){return Tree[k].sum;}push_down(k);long long res=0;int mid=Tree[k].l+Tree[k].r>>1;if(L<=mid) res+=Query(k<<1,L,R);if(R>mid) res+=Query(k<<1|1,L,R);return res;
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%lld",&a[i]);}Build(1,1,n);for(int i=1;i<=m;i++){scanf("%d",&opt);if(opt==1){scanf("%d%d%lld",&x,&y,&z);update(1,x,y,z);}else if(opt==2){scanf("%d%d",&x,&y);printf("%lldn",Query(1,x,y));}}return 0;
}

二.区间乘法和加减修改，区间查询。

　　来自洛谷【模板】线段树2……

　　在这种情况下要注意优先处理加标记，按先乘后加运算……

#include<bits/stdc++.h>
using namespace std;
struct SegTree
{int l,r;long long sum,Add,Mul;
}Tree[1000040];
int n,m,p,x,y,z,opt,a[100010];
void push_up(int k)
{Tree[k].sum=(Tree[k<<1].sum+Tree[k<<1|1].sum)%p;
}
void Build(int k,int l,int r)
{Tree[k].Add=0;Tree[k].Mul=1;Tree[k].l=l;Tree[k].r=r;if(l==r){Tree[k].sum=a[l]%p;return;}int mid=l+r>>1;Build(k<<1,l,mid);Build(k<<1|1,mid+1,r);push_up(k);
}
void push_down(int k)
{Tree[k<<1].Add=(Tree[k].Add+Tree[k<<1].Add*Tree[k].Mul)%p;Tree[k<<1|1].Add=(Tree[k].Add+Tree[k<<1|1].Add*Tree[k].Mul)%p;Tree[k<<1].Mul=(Tree[k<<1].Mul*Tree[k].Mul)%p;Tree[k<<1|1].Mul=(Tree[k<<1|1].Mul*Tree[k].Mul)%p;Tree[k<<1].sum=(Tree[k<<1].sum*Tree[k].Mul+Tree[k].Add*(Tree[k<<1].r-Tree[k<<1].l+1))%p;Tree[k<<1|1].sum=(Tree[k<<1|1].sum*Tree[k].Mul+Tree[k].Add*(Tree[k<<1|1].r-Tree[k<<1|1].l+1))%p;Tree[k].Add=0;Tree[k].Mul=1;
}
void update_Add(int k,int L,int R,long long val)
{    push_down(k);if(L<=Tree[k].l && Tree[k].r<=R){Tree[k].Add=(Tree[k].Add+val)%p;Tree[k].sum=(Tree[k].sum+Tree[k].Add*(Tree[k].r-Tree[k].l+1))%p;return;}int mid=Tree[k].l+Tree[k].r>>1;if(L<=mid) update_Add(k<<1,L,R,val);if(R>mid) update_Add(k<<1|1,L,R,val);push_up(k);
}
void update_Mul(int k,int L,int R,long long val)
{    push_down(k);if(L<=Tree[k].l && Tree[k].r<=R){Tree[k].Mul=(Tree[k].Mul*val)%p;Tree[k].Add=(Tree[k].Add*val)%p;Tree[k].sum=(Tree[k].sum*Tree[k].Mul)%p;return;}int mid=Tree[k].l+Tree[k].r>>1;if(L<=mid) update_Mul(k<<1,L,R,val);if(R>mid) update_Mul(k<<1|1,L,R,val);push_up(k);
}
long long Query(int k,int L,int R)
{if(L<=Tree[k].l && Tree[k].r<=R){return Tree[k].sum%p;}push_down(k);long long res=0;int mid=Tree[k].l+Tree[k].r>>1;if(L<=mid) res+=Query(k<<1,L,R);if(R>mid) res+=Query(k<<1|1,L,R);return res%p;
}
int main()
{scanf("%d%d%d",&n,&m,&p);for(int i=1;i<=n;i++){scanf("%lld",&a[i]);}Build(1,1,n);for(int i=1;i<=m;i++){scanf("%d",&opt);if(opt==1){scanf("%d%d%lld",&x,&y,&z);update_Mul(1,x,y,z);}else if(opt==2){scanf("%d%d%lld",&x,&y,&z);update_Add(1,x,y,z);}else if(opt==3){scanf("%d%d",&x,&y);printf("%lldn",Query(1,x,y));}}return 0;
}

三.区间修改权值，统计区间内不同元素个数。

　　这类题，如果允许线段树做的话一般会带着状态压缩一起。

　　题目来自一次模拟赛。

　　题意：有两种操作 C 和 P。

　　　　　对于C操作，给一个区间[l,r]，将其中所有数换成一个给定的k。

　　　　　对于P操作，给一个区间[l,r]，统计其中不同数个数。

·　　　　  初始序列全为1。

　　　　　k不超过30。

　　题解：线段树状压位运算维护就行。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 struct SegTree
 4 {
 5     int l,r;
 6     int val,col;
 7 }Tree[400040];
 8 int n,T,m,x,y,z;
 9 char s[10];
10 void pushup(int k)
11 {
12     Tree[k].val=Tree[k<<1].val|Tree[k<<1|1].val;
13 }
14 void Build(int k,int l,int r)
15 {
16     Tree[k].l=l;
17     Tree[k].r=r;
18     Tree[k].col=0;
19     if(l==r)
20     {
21         Tree[k].val=1;
22         return;
23     }
24     int mid=l+r>>1;
25     Build(k<<1,l,mid);
26     Build(k<<1|1,mid+1,r);
27     pushup(k);
28 }
29 void pushdown(int k)
30 {
31     if(Tree[k].col)
32     {
33         Tree[k<<1].col=Tree[k].col;
34         Tree[k<<1|1].col=Tree[k].col;
35         Tree[k<<1].val=Tree[k].col;
36         Tree[k<<1|1].val=Tree[k].col;
37         Tree[k].col=0;
38     }
39 }
40 void update(int k,int L,int R,int w)
41 {
42     int l=Tree[k].l,r=Tree[k].r;
43     if(L<=l && r<=R)
44     {
45         Tree[k].col=1<<(w-1);
46         Tree[k].val=1<<(w-1);
47         return;
48     }
49     pushdown(k);
50     int mid=l+r>>1;
51     if(L<=mid) update(k<<1,L,R,w);
52     if(R>mid) update(k<<1|1,L,R,w);
53     pushup(k);
54 }
55 long long Query(int k,int L,int R)
56 {
57     int l=Tree[k].l,r=Tree[k].r;
58     if(L<=l && r<=R)
59     {
60         return Tree[k].val;
61     }
62     long long res=0;
63     pushdown(k);
64     int mid=l+r>>1;
65     if(L<=mid) res|=Query(k<<1,L,R);
66     if(R>mid) res|=Query(k<<1|1,L,R);
67     return res;
68 }
69 int main()
70 {
71     scanf("%d%d%d",&n,&T,&m);
72     Build(1,1,n);
73     for(int i=1;i<=m;i++)
74     {
75         scanf("%s",s);
76         if(s[0]=='C')
77         {
78             scanf("%d%d%d",&x,&y,&z);
79             if(x>y) swap(x,y);
80             update(1,x,y,z);
81         }
82         else
83         {
84             scanf("%d%d",&x,&y);
85             if(x>y) swap(x,y); 
86             long long ans=Query(1,x,y);
87             int cnt=0;
88             for(int j=1;j<=30;j++)
89             {
90                 if(ans&(1<<(j-1)))
91                 {
92                     cnt++;
93                 }
94             }
95             cout<<cnt<<endl;
96         }
97     }
98     return 0;
99 }

转载于:.html