题目大意:
P3372(线段树模板)
已知一个数列,你需要进行下面两种操作:
1、将某区间每一个数加上 k。
2、求出某区间每一个数的和。
思路:
记录线段树模板
(1)懒标记 add[ ],数组一定要开的大一点
前缀和 sum[ ],数组一定要开的大一点,还要开long long
(2)build 建树函数:树 k ,边界 l ~ r
(3)Add 加数函数:树 k ,边界 l ~ r ,区间加 p
(4)pushdown 标记下传函数:树 k ,边界 l ~ r ,中间 mid
(5)modify 区间加数函数:树 k ,边界 l ~ r ,询问区间 x ~ y ,区间加数 v
(6)quety 区间查询函数:树 k ,边界 l ~ r ,询问区间 x ~ y
AC Code:
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,x,y,v,opr;
int a[N],add[N*4];
long long sum[N*4];
long long ans;
inline int read()
{
int ans=0;
char last=' ',ch=getchar();
while(ch<'0'||ch>'9') last=ch,ch=getchar();
while(ch>='0'&&ch<='9') ans=ans*10+ch-'0',ch=getchar();
if(last=='-') ans=-ans;
return ans;
}
void build(int k,int l,int r)
{
if(l==r)
{
sum[k]=a[l]; return ;
}
int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
sum[k]=sum[k<<1]+sum[k<<1|1];
}
void Add(int k,int l,int r,int p)
{
add[k]+=p;
sum[k]+=(long long)(r-l+1)*p;
}
void pushdown(int k,int l,int r,int mid)
{
if(add[k]==0) return ;
Add(k<<1,l,mid,add[k]);
Add(k<<1|1,mid+1,r,add[k]);
add[k]=0;
}
void modify(int k,int l,int r,int x,int y,int v)
{
if(x<=l&&r<=y) return Add(k,l,r,v);
int mid=(l+r)>>1;
pushdown(k,l,r,mid);
if(x<=mid) modify(k<<1,l,mid,x,y,v);
if(mid<y) modify(k<<1|1,mid+1,r,x,y,v);
sum[k]=sum[k<<1]+sum[k<<1|1];
}
long long query(int k,int l,int r,int x,int y)
{
if(x<=l&&r<=y) return sum[k];
int mid=(l+r)>>1;
long long res=0;
pushdown(k,l,r,mid);
if(x<=mid) res+=query(k<<1,l,mid,x,y);
if(mid<y) res+=query(k<<1|1,mid+1,r,x,y);
return res;
}
int main()
{
n=read();m=read();
for(int i=1;i<=n;i++) a[i]=read();
build(1,1,n);
for(int i=1;i<=m;i++)
{
opr=read();x=read();y=read();
if(opr==1)
{
v=read();
modify(1,1,n,x,y,v);
}
if(opr==2)
cout<<query(1,1,n,x,y)<<endl;
}
return 0;
}
Comments | NOTHING