@[LiM\_817](/space/show?uid=56724) 干嘛又@我
by applese @ 2017-12-17 21:17:57
@[啦啦啦666](/space/show?uid=48417) @[LiM\_817](/space/show?uid=56724) 显然完全可以用线段树的模板水过本题：
```cpp
#include <cstdio>
#include <cstring>
struct node{ int l,r,lc,rc,c; } a[1000001];
int q[1000001],len=0,n=0,m=0;
void bt(int l,int r)
{
len++;
a[len].l=l;
a[len].r=r;
a[len].lc=-1;
a[len].rc=-1;
a[len].c=0;
int now=len;
if(l<r)
{
int mid=(l+r)/2;
a[len].lc=len+1,bt(l,mid);
a[now].rc=len+1,bt(mid+1,r);
}
}
void change(int now,int x,int t)
{
if(a[now].l==a[now].r)
{
a[now].c+=t;
return ;
}
int mid=(a[now].l+a[now].r)/2;
if(x<=mid)
{
change(a[now].lc,x,t);
}
else
{
change(a[now].rc,x,t);
}
a[now].c=a[a[now].lc].c+a[a[now].rc].c;
}
int findsum(int now,int l,int r)
{
if(a[now].l==l && a[now].r==r)
{
return a[now].c;
}
int mid=(a[now].l+a[now].r)/2;
if(r<=mid)
{
return findsum(a[now].lc,l,r);
}
else if(mid+1<=l)
{
return findsum(a[now].rc,l,r);
}
else
{
return findsum(a[now].lc,l,mid)+findsum(a[now].rc,mid+1,r);
}
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&q[i]);
}
bt(1,n);
for(int i=1;i<=n;i++)
{
change(1,i,q[i]);
}
for(int i=1;i<=m;i++)
{
int t=0,x=0,y=0;
scanf("%d %d %d",&t,&x,&y);
if(t==1)
{
change(1,x,y);
}
else
{
printf("%d\n",findsum(1,x,y));
}
}
return 0;
}
```
by Drinkkk @ 2017-12-17 21:18:54
这™不是线段树吗
by λᴉʍ @ 2017-12-17 21:21:47
树状数组不是有Lowbit吗=\_=???，这个怎么没有。
by Loner_Knowledge @ 2017-12-17 22:56:58
@[Loner\_Knowledge](/space/show?uid=78044) 其实楼主想说的是如何用线段树水过本题。
by Drinkkk @ 2017-12-18 07:56:55
这个线段树。。。好魔性
by Lolierl @ 2017-12-18 18:35:27
@[Lolierl](/space/show?uid=22930) 原谅我花了1分钟都没看明白这个线段树......
by 权御天下 @ 2017-12-19 22:27:41
@钟梓俊，你怎么让我理解这代码？
by 一个低调的人 @ 2017-12-20 19:09:24
才发现这段代码是线段树。。。
by iodwad @ 2017-12-20 19:09:59
您怎么能用线段树水splay好题呢
by newbie314159 @ 2017-12-20 19:15:42