Open xjzsq opened 6 years ago
又写了一次线段树...暂时不想重写一篇博客,就发条评论吧... 写了大概40min(期间一边研究珂学一边敲...),看速度还可以吧... 然后查错查了好久...最后发现竟然是(r-l+1)写成了(l+r-1),并不知道自己当时在干什么(估计是看到珂朵莉手抖了一下...)
//深夜线段树?有点zuo...
#include<bits/stdc++.h>
using namespace std;
const int maxn=100001;
long long a[maxn],k;
int n,m,x,y;
struct segtreenode
{
long long sumv[maxn<<2],add[maxn<<2];
inline void pushup(int o)
{
sumv[o]=sumv[o<<1]+sumv[o<<1|1];
}
void build(int o,int l,int r)
{
if(l==r){sumv[o]=a[l];return;}
int mid=(l+r)>>1;
build(o<<1,l,mid);
build(o<<1|1,mid+1,r);
pushup(o);//forget pushup
}
inline void pushdown(int o,int l,int r)
{
if(!add[o])return;
int mid=(l+r)>>1;
sumv[o<<1]+=add[o]*(mid-l+1);add[o<<1]+=add[o];
sumv[o<<1|1]+=add[o]*(r-mid);add[o<<1|1]+=add[o];
add[o]=0;//forget clear the lazy tag
//pushup(o);//pushup by mistake
}
inline void addsum(int o,int l,int r,int s,int t,long long p)
{
if(l>=s&&r<=t){sumv[o]+=p*(r-l+1);add[o]+=p;return;}
int mid=(l+r)>>1;
pushdown(o,l,r);//forget pushdown
if(mid>=s)addsum(o<<1,l,mid,s,t,p);
if(mid<t)addsum(o<<1|1,mid+1,r,s,t,p);
pushup(o);
}
long long querysum(int o,int l,int r,int s,int t)
{
if(l>=s&&r<=t)return sumv[o];
long long ans=0;
int mid=(l+r)>>1;
if(add[o])pushdown(o,l,r);//forget to judge if the lazy tag is 0
if(mid>=s)ans+=querysum(o<<1,l,mid,s,t);
if(mid<t)ans+=querysum(o<<1|1,mid+1,r,s,t);
return ans;
}
}segtree;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
segtree.build(1,1,n);
while(m--)
{
scanf("%d",&x);
if(x==1)
{
scanf("%d%d%lld",&x,&y,&k);
segtree.addsum(1,1,n,x,y,k);
}
else
{
scanf("%d%d",&x,&y);
printf("%lld\n",segtree.querysum(1,1,n,x,y));
}
}
return 0;
}
就这样吧,去写作业了...
http://www.xjdesyxx.top/2018/02/09/segtree/