线段树食用方法
1.什么是线段树？
2.线段树操作.
3.lazy.
1.线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。
整个步骤大致可分为 建树—查询—修改。
建树
1 void build(int k,int left,int right){ 2 if(left==right){ 3 ans[k]=num[left]; 4 return ; 5 } 6 int mid=left+(right-left)/2; 7 build(k*2,left,mid); 8 build(k*2+1,mid+1,right); 9 ans[k]=ans[k*2]+ans[k*2+1]; 10 }
查询
1 int qurey(int k,int lt,int rt,int qx,int qy){ 2 if(qy<lt||qx>rt)return 0; 3 else if(lt>=qx&&qy>=rt)return ans[k]; 4 else { 5 int mid=lt+(rt-lt)/2; 6 return qurey(k*2,lt,mid,qx,qy)+qurey(k*2+1,mid+1,rt,qx,qy); 7 } 8
单点修改
1 void modify(int k,int lt,int rt,int po,int val){ 2 if(po<lt||po>rt)return ; 3 else if(lt==po&<==rt){ 4 ans[k]+=val; 5 num[k]+=val; 6 return ; 7 } 8 else { 9 int mid=lt+(rt-lt)/2; 10 modify(k*2,lt,mid,po,val); 11 modify(k*2+1,mid+1,rt,po,val); 12 ans[k]=ans[k*2]+ans[k*2+1]; 13 return ; 14 } 15 }
区间修改
1 void modify(int k,int lt,int rt,int qx,int qy,int val){ 2 if(qy<lt||qx>rt)return ; 3 else if(lt>=qx&&rt<=qy){ 4 add(k,lt,rt,val); 5 //num[k]+=val; 6 return ; 7 } 8 else { 9 int mid=lt+(rt-lt)/2; 10 pushdown(k,lt,rt); 11 modify(k*2,lt,mid,qx,qy,val); 12 modify(k*2+1,mid+1,rt,qx,qy,val); 13 ans[k]=ans[k*2]+ans[k*2+1]; 14 return ; 15 } 16 }
懒标记
void pushdown(int k,int lt,int rt){ if(addval[k]==0)return ; int mid=(lt+rt)>>1; add(k*2,lt,mid,addval[k]); add(k*2+1,mid+1,rt,addval[k]); addval[k]=0; return ; }
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=500000+10; 4 long long num[maxn],ans[maxn]; 5 long long addval[maxn]; 6 void build(int k,int left,int right){ 7 if(left==right){ 8 ans[k]=num[left]; 9 return ; 10 } 11 int mid=left+(right-left)/2; 12 build(k*2,left,mid); 13 build(k*2+1,mid+1,right); 14 ans[k]=ans[k*2]+ans[k*2+1]; 15 } 16 void add(int k,int lt,int rt,int val){ 17 addval[k]+=val; 18 ans[k]+=(rt-lt+1)*val; 19 return ; 20 } 21 void pushdown(int k,int lt,int rt){ 22 if(addval[k]==0)return ; 23 int mid=(lt+rt)>>1; 24 add(k*2,lt,mid,addval[k]); 25 add(k*2+1,mid+1,rt,addval[k]); 26 addval[k]=0; 27 return ; 28 } 29 long long qurey(int k,int lt,int rt,int qx,int qy){ 30 if(qy<lt||qx>rt)return 0; 31 else if(lt>=qx&&qy>=rt)return ans[k]; 32 else { 33 int mid=lt+(rt-lt)/2; 34 pushdown(k,lt,rt); 35 return qurey(k*2,lt,mid,qx,qy)+qurey(k*2+1,mid+1,rt,qx,qy); 36 } 37 } 38 void modify(int k,int lt,int rt,int qx,int qy,int val){ 39 if(qy<lt||qx>rt)return ; 40 else if(lt>=qx&&rt<=qy){ 41 add(k,lt,rt,val); 42 //num[k]+=val; 43 return ; 44 } 45 else { 46 int mid=lt+(rt-lt)/2; 47 pushdown(k,lt,rt); 48 modify(k*2,lt,mid,qx,qy,val); 49 modify(k*2+1,mid+1,rt,qx,qy,val); 50 ans[k]=ans[k*2]+ans[k*2+1]; 51 return ; 52 } 53 } 54 int main() 55 { 56 int n,m; 57 cin>>n>>m; 58 for(int i=1;i<=n;i++) 59 scanf("%lld",&num[i]); 60 build(1,1,n); 61 for(int i=1;i<=m;i++){ 62 int pre,x,y,z; 63 scanf("%d%d%d",&pre,&x,&y); 64 if(pre==1){ 65 int k; 66 scanf("%d",&k); 67 modify(1,1,n,x,y,k); 68 } 69 else { 70 cout<<qurey(1,1,n,x,y)<<endl; 71 } 72 } 73 return 0; 74 } 75 /* 76 7 77 33 64 57 21 19 8 11 78 */
1 // luogu-judger-enable-o2 2 #include<bits/stdc++.h> 3 using namespace std; 4 const long long maxn=500000+10; 5 long long p; 6 long long num[maxn],ans[4*maxn]; 7 long long addval[4*maxn],addmul[4*maxn]; 8 inline int read() { 9 char ch = getchar(); int x = 0, f = 1; 10 while(ch < '0' || ch > '9') { 11 if(ch == '-') f = -1; 12 ch = getchar(); 13 } while('0' <= ch && ch <= '9') { 14 x = x * 10 + ch - '0'; 15 ch = getchar(); 16 } return x * f; 17 } 18 void build(long long k,long long left,long long right){ 19 if(left==right){ 20 ans[k]=num[left]; 21 return ; 22 } 23 long long mid=left+(right-left)/2; 24 build(k*2,left,mid); 25 build(k*2+1,mid+1,right); 26 ans[k]=(ans[k*2]+ans[k*2+1])%p; 27 } 28 void add(long long k,long long lt,long long rt,long long val){ 29 addval[k]=(addval[k]+val)%p; 30 ans[k]=(ans[k]+(rt-lt+1)*val)%p; 31 return ; 32 } 33 void mul(long long k,long long lt,long long rt,long long val){ 34 addmul[k]=(addmul[k]*val)%p; 35 addval[k]=(addval[k]*val)%p; 36 ans[k]=ans[k]*val%p; 37 return ; 38 } 39 void pushdown(long long k,long long lt,long long rt){ 40 // if(addval[k]==0)return ; 41 long long mid=(lt+rt)>>1; 42 mul(k*2,lt,mid,addmul[k]); 43 mul(k*2+1,mid+1,rt,addmul[k]); 44 addmul[k]=1; 45 add(k*2,lt,mid,addval[k]); 46 add(k*2+1,mid+1,rt,addval[k]); 47 addval[k]=0; 48 return ; 49 } 50 long long qurey(long long k,long long lt,long long rt,long long qx,long long qy){ 51 if(qy<lt||qx>rt)return 0; 52 else if(lt>=qx&&qy>=rt)return ans[k]%p; 53 else { 54 long long mid=lt+(rt-lt)/2; 55 pushdown(k,lt,rt); 56 return (qurey(k*2,lt,mid,qx,qy)+qurey(k*2+1,mid+1,rt,qx,qy))%p; 57 } 58 } 59 void modify(long long k,long long lt,long long rt,long long qx,long long qy,long long val){ 60 if(qy<lt||qx>rt)return ; 61 else if(lt>=qx&&rt<=qy){ 62 add(k,lt,rt,val); 63 //num[k]+=val; 64 return ; 65 } 66 else { 67 long long mid=lt+(rt-lt)/2; 68 pushdown(k,lt,rt); 69 modify(k*2,lt,mid,qx,qy,val); 70 modify(k*2+1,mid+1,rt,qx,qy,val); 71 ans[k]=(ans[k*2]+ans[k*2+1])%p; 72 return ; 73 } 74 } 75 void modify1(long long k,long long lt,long long rt,long long qx,long long qy,long long val){ 76 if(qy<lt||qx>rt)return ; 77 else if(lt>=qx&&rt<=qy){ 78 mul(k,lt,rt,val); 79 //num[k]+=val; 80 return ; 81 } 82 else { 83 long long mid=lt+(rt-lt)/2; 84 pushdown(k,lt,rt); 85 modify1(k*2,lt,mid,qx,qy,val); 86 modify1(k*2+1,mid+1,rt,qx,qy,val); 87 ans[k]=(ans[k*2]+ans[k*2+1])%p; 88 return ; 89 } 90 } 91 int main() 92 { 93 long long n,m; 94 //n=read();m=read();p=read(); 95 cin>>n>>m>>p; 96 for(long long i=1;i<=n;i++) 97 cin>>num[i]; 98 for(long long i=1;i<=4*n;i++)addmul[i]=1; 99 build(1,1,n); 100 for(long long i=1;i<=m;i++){ 101 long long pre,x,y; 102 //pre=read(); 103 //x=read();y=read(); 104 //scanf("%d%d%d",&pre,&x,&y); 105 cin>>pre>>x>>y; 106 if(pre==2){ 107 long long k; 108 //k =read(); 109 //scanf("%d",&k); 110 cin>>k; 111 modify(1,1,n,x,y,k); 112 } 113 else if(pre==1){ 114 long long k; 115 //y=read(); 116 //k=read(); 117 // scanf("%d",&k); 118 cin>>k; 119 modify1(1,1,n,x,y,k); 120 } 121 else { 122 cout<<qurey(1,1,n,x,y)%p<<endl; 123 } 124 } 125 return 0; 126 } 127 /* 128 7 129 33 64 57 21 19 8 11 130 */