拿树状数组的算法已经过了，但是想拿线段树写一写。。。。。。
by Harry_Potter @ 2018-06-07 16:04:15
考虑一下把cincout换成scanfprintf？
by AThousandSuns @ 2018-06-07 16:04:38
@[AThousandSuns](/space/show?uid=72118)
让我试一试，谢谢啊
by Harry_Potter @ 2018-06-07 16:16:58
@[AThousandSuns](/space/show?uid=72118)
呵呵，还是70分
by Harry_Potter @ 2018-06-07 16:23:48
换完后：
```cpp
#include <bits/stdc++.h>
#define lson l,m,rt*2
#define rson m+1,r,rt*2+1
using namespace std;
int n,m,k,z[1000000],y[1000003];
void update(int rt)
{
z[rt]=z[rt*2]+z[rt*2+1];
}
void build(int l,int r,int rt)
{
if (l==r)
{
z[rt]=y[l];
return;
}
int m=(l+r)/2;
build(lson);
build(rson);
update(rt);
}
void modify(int l,int r,int rt,int p,int v)
{
if (l==r)
{
z[rt]+=v;
return;
}
int m=(l+r)/2;
if (p<=m) modify(lson,p,v);
else modify(rson,p,v);
update(rt);
}
int query(int l,int r,int rt,int nowl,int nowr)
{
if (nowl<=l && r<=nowr) return z[rt];
int m=(l+r)/2;
if (nowl<=m)
{
if (m<nowr) return query(lson,nowl,nowr)+query(rson,nowl,nowr);
else return query(lson,nowl,nowr);
}
else return query(rson,nowl,nowr);
}
int main()
{
cin >> n >> m;
for(int a=1;a<=n;a++)
scanf("%d",&y[a]);
build(1,n,1);
for (int a=1;a<=m;a++)
{
int op;
scanf("%d",&op);
if (op == 1)
{
int p,v;
scanf("%d%d",&p,&v);
modify(1,n,1,p,v);
}
else
{
int l,r;
scanf("%d%d",&l,&r);
printf("%d\n",query(1,n,1,l,r));
}
}
return 0;
}
```
by Harry_Potter @ 2018-06-07 16:27:55
@[AThousandSuns](/space/show?uid=72118)
又优化了一下，AC了
感谢感谢！
by Harry_Potter @ 2018-06-07 16:28:55
@[Harry_Potter](/space/show?uid=54832) 把线段树数组再开大一点，到1100000应该差不多。以后最好把数组开到4倍比较稳。（虽然补到2的整数次幂再乘2就够了）
by AThousandSuns @ 2018-06-07 16:29:13
为什么不直接做线段树1呢?感觉比这道题难多了。
by AlgoEmperor @ 2018-06-07 16:58:27
@[Ofnoname](/space/show?uid=73489)
e.................m
by Harry_Potter @ 2018-06-07 18:39:17