segTree
参考：http://www.cnblogs.com/TenosDoIt/p/3453089.html#c
初学者建议先参考上面“一步一步理解线段树”学习理论。
在这里Code分别为区间求和&区间求积的做法。
分别对应OJ luogu的3372和3373
1.区间和
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
struct node{
long long val,lazytag;
}segTree[*+];
];
int n,m,t,x,y,k;
void build(int root,long long arr[],int istart,int iend){//建树
segTree[root].lazytag=;
if(istart==iend){
segTree[root].val=arr[istart];
}else{
;
build(root*,arr,istart,mid);
build(root*+,arr,mid+,iend);
segTree[root].val=segTree[root*].val+segTree[root*+].val;
}
}
void pushDown(int root,int start,int end){//插入懒标记
){
segTree[root*].lazytag+=segTree[root].lazytag;
segTree[root*+].lazytag+=segTree[root].lazytag;
;
segTree[root*].val+=segTree[root].lazytag*(mid-start+);
segTree[root*+].val+=segTree[root].lazytag*(end-mid);
segTree[root].lazytag=;
}
}
long long query(int root,int nstart,int nend,int qstart,int qend){//查询区间
if(qstart>nend||qend<nstart){
;
}if(qstart<=nstart&&qend>=nend){
return segTree[root].val;
}
pushDown(root,nstart,nend);
;
,nstart,mid,qstart,qend)+query(root*+,mid+,nend,qstart,qend);
}
void update(int root,int nstart,int nend,int ustart,int uend,int addval){//赋值
if(ustart>nend||uend<nstart){
return;
}if(ustart<=nstart&&uend>=nend){
segTree[root].lazytag+=addval;
segTree[root].val+=addval*(nend-nstart+);
return;
}
pushDown(root,nstart,nend);
;
update(root*,nstart,mid,ustart,uend,addval);
update(root*+,mid+,nend,ustart,uend,addval);
segTree[root].val=segTree[root*].val+segTree[root*+].val;
}
int main(){
scanf("%lld%lld",&n,&m);
;i<=n;i++){
scanf("%lld",&a[i]);
}
build(,a,,n);
;i<=m;i++){
scanf("%lld",&t);
){
scanf("%lld%lld%lld",&x,&y,&k);
update(,,n,x,y,k);
}){
scanf("%lld%lld",&x,&y);
printf(,,n,x,y));
}
}
}
2.区间积
在这里要点几个点注意：
1：tag2的初始值为1；
2：pushdown里先tag2后tag1（先乘后加）；
3：对tag2进行push需要先把tag1*tag2，tag2*tag2，val*tag2，最后别忘了tag2=1；
4：tag2不需要乘区间，原因是:a*(b+c)=a*b+a*c，乘法分配律；
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
struct node{
long long val,lazytag,lazytag2;
}segTree[*+];
];
long long n,m,t,x,y,k,p;
void build(int root,long long arr[],int istart,int iend){//建树
segTree[root].lazytag=;
segTree[root].lazytag2=;
if(istart==iend){
segTree[root].val=arr[istart];
}else{
;
build(root*,arr,istart,mid);
build(root*+,arr,mid+,iend);
segTree[root].val=segTree[root*].val+segTree[root*+].val;
}
}
void pushDown(int root,int start,int end){//插入懒标记
**){**
segTree[root*].lazytag=(segTree[root*].lazytag*segTree[root].lazytag2)%p;
segTree[root*+].lazytag=(segTree[root*+].lazytag*segTree[root].lazytag2)%p;
segTree[root*].lazytag2=(segTree[root*].lazytag2*segTree[root].lazytag2)%p;
segTree[root*+].lazytag2=(segTree[root*+].lazytag2*segTree[root].lazytag2)%p;
;
segTree[root*].val=(segTree[root*].val*(segTree[root].lazytag2))%p;
segTree[root*+].val=(segTree[root*+].val*(segTree[root].lazytag2))%p;
segTree[root].lazytag2=;
}
){
segTree[root*].lazytag+=segTree[root].lazytag;
segTree[root*+].lazytag+=segTree[root].lazytag;
;
segTree[root*].val+=segTree[root].lazytag*(mid-start+);
segTree[root*+].val+=segTree[root].lazytag*(end-mid);
segTree[root].lazytag=;
}
}
long long query(int root,int nstart,int nend,int qstart,int qend){//查询区间
if(qstart>nend||qend<nstart){
;
}if(qstart<=nstart&&qend>=nend){
return segTree[root].val;
}
pushDown(root,nstart,nend);
;
,nstart,mid,qstart,qend)+query(root*+,mid+,nend,qstart,qend);
}
void update(int root,int nstart,int nend,int ustart,int uend,int addval){//赋值
if(ustart>nend||uend<nstart){
return;
}if(ustart<=nstart&&uend>=nend){
segTree[root].lazytag+=addval;
segTree[root].val+=addval*(nend-nstart+);
return;
}
pushDown(root,nstart,nend);
;
update(root*,nstart,mid,ustart,uend,addval);
update(root*+,mid+,nend,ustart,uend,addval);
segTree[root].val=segTree[root*].val+segTree[root*+].val;
}
**void tupdate(int root,int nstart,int nend,int ustart,int uend,int addval){//赋值(chengfa**
if(ustart>nend||uend<nstart){
return;
}if(ustart<=nstart&&uend>=nend){
segTree[root].lazytag=(segTree[root].lazytag*addval)%p;
segTree[root].lazytag2=(segTree[root].lazytag2*addval)%p;
segTree[root].val=(segTree[root].val*addval)%p;
return;
}
pushDown(root,nstart,nend);
;
tupdate(root*,nstart,mid,ustart,uend,addval);
tupdate(root*+,mid+,nend,ustart,uend,addval);
segTree[root].val=segTree[root*].val+segTree[root*+].val;
}
int main(){
scanf("%lld%lld%lld",&n,&m,&p);
;i<=n;i++){
scanf("%lld",&a[i]);
}
build(,a,,n);
;i<=m;i++){
scanf("%lld",&t);
){
scanf("%lld%lld%lld",&x,&y,&k);
update(,,n,x,y,k);
}){
scanf("%lld%lld",&x,&y);
printf(,,n,x,y)%p);
}){
scanf("%lld%lld%lld",&x,&y,&k);
tupdate(,,n,x,y,k);
}
}
;
}
并且感谢will7101的帮助