2018-09-07 11:06:25

## 分析

给定一个数组
7 8 6 5 1 8 18 20 35 //瞎敲的emmm
7 1 -2 -1 3 10 2  15//对应得到差分数组.

### 安利一篇很好的写树状数组的blog

--------------------代码---------------------

/*

Timeuse：214ms
Creator：顾z
Date:2018.09.07
*/
#include<bits/stdc++.h>
#define int long long
#define IL inline
#define RI register int
#define lowbit(x) x&-x
IL void in(int &x){
int f=1;x=0;char s=getchar();
while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
while(s<='9'&&s>='0'){x=x*10+s-'0';s=getchar();}
x*=f;
}
int n,m,last,opt,x,y,z,mian;
int sum1[500002],sum2[500002];
{
for(RI i=pos;i<=n;i+=lowbit(i))
sum1[i]+=x,sum2[i]+=pos*x;
}
IL long long query(int pos)
{
long long res=0;
for(RI i=pos;i;i-=lowbit(i))
res+=(pos+1)*sum1[i]-sum2[i];
return res;
}
main(void)
{
in(n),in(m);
for(RI i=1,opt;i<=m;i++)
{
in(opt);
switch(opt)
{
case 2:in(z),mian+=z;break;
case 3:in(z),mian-=z;break;
case 4:in(x),in(y);printf("%lld\n",query(y)-query(x-1)+(x==1)*mian);break;
case 5:printf("%lld\n",query(1)+mian);
}
}
}


/*

zkw线段树应该会更快一些.
Timeuse：594ms
Creator：顾z
Date:2018.09.03
*/
#include<bits/stdc++.h>
#define int long long
#define IL inline
#define RI register int
#define ls o<<1
#define rs o<<1|1
#define N 1000008
int f=1;x=0;char s=getchar();
while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
while(s<='9'&&s>='0'){x=x*10+s-'0';s=getchar();}
x*=f;
}
int n,f,tr[N],tg[N],mian,c[N];
IL void up(int o){tr[o]=tr[ls]+tr[rs];return;}
IL void build(int o,int l,int r)
{
if(l==r)
{
return;
}
int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
up(o);
return;
}
IL void down(int o,int l,int r)
{
if(tg[o])
{
int mid=(l+r)>>1;
tg[ls]+=tg[o];tg[rs]+=tg[o];
tr[ls]+=tg[o]*(mid-l+1);
tr[rs]+=tg[o]*(r-mid);
tg[o]=0;
}
}
IL int query(int o,int l,int r,int x,int y)
{
if(x<=l&&y>=r)return tr[o];
down(o,l,r);
int res=0;
int mid=(l+r)>>1;
if(x<=mid)res+=query(ls,l,mid,x,y);
if(y>mid)res+=query(rs,mid+1,r,x,y);
return res;
}
IL void change(int o,int l,int r,int x,int y,int del)
{
if(x<=l&&y>=r)
{
tg[o]+=del;
tr[o]+=del*(r-l+1);
return;
}
down(o,l,r);
int mid=(l+r)>>1;
if(x<=mid)change(ls,l,mid,x,y,del);
if(y>mid)change(rs,mid+1,r,x,y,del);
up(o);
return;
}
signed main()
{
build(1,1,n);
for(RI i=1,opt,x,y,z;i<=f;i++)
{
switch(opt)
{
}