我用线段树做的
by Polariserist @ 2020-08-04 19:20:23
树状数组模板用线段树,您牛逼啊
by 添哥 @ 2020-08-04 19:22:14
线段树过不去,亲自尝试过
by Ame__ @ 2020-08-04 19:22:39
@[Avengers_Endgame](/user/171513) 学一下树状数组吧,不难的
by garbage2 @ 2020-08-04 19:22:59
@[Avengers_Endgame](/user/171513)
线段树空间要开4倍
by Smile_Cindy @ 2020-08-04 19:23:35
楼上正解
by _998344353_ @ 2020-08-04 19:25:01
@[Ame__](/user/245875) 事实上我过了。
by critnos @ 2020-08-04 19:28:29
(清北学堂的题)5005000也过不去
(姜志豪用的线段树,过了。它的代码如下:)
```cpp
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 500500;
const int M = 1050000;
long long tree[M];
int tl[M],tr[M],tmid[M];
int a[N];
int n,m;
void MakeTree(int x,int l,int r)//线段树的x号点表示区间[l,r]
{
tl[x]=l;
tr[x]=r;
if(l==r)
{
tree[x]=a[l];
}
else
{
int mid=(l+r)/2;
tmid[x]=mid;
MakeTree(x*2,l,mid);
MakeTree(x*2+1,mid+1,r);
tree[x]=tree[x*2]+tree[x*2+1];
}
}
void add(int x,int p,long long v)//现在在线段树的x号点,需要把原序列的p位置增加v
{
tree[x]+=v;
if(tl[x]<tr[x])
{
if(p<=tmid[x])
add(x*2,p,v);
else
add(x*2+1,p,v);
}
}
long long find(int x,int l,int r)//现在在线段树的x号点,需要返回[l,r]的和
{
if(tl[x]==l && tr[x]==r)
return tree[x];
if(r<=tmid[x])
return find(x*2,l,r);
else if(l>=tmid[x])
return find(x*2+1,l,r);
return find(x*2,l,tmid[x])+find(x*2+1,tmid[x]+1,r);
}
int main()
{
int i,j;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
MakeTree(1,1,n);
for(i=1;i<=m;i++)
{
int opt;
scanf("%d",&opt);
if(opt==1)
{
int p;
long long now;
scanf("%d%lld",&p,&now);
add(1,p,now);
}
else
{
int a,b;
scanf("%d%d",&a,&b);
long long res=find(1,a,b);
printf("%lld\n",res);
}
}
return 0;
}
```
by Polariserist @ 2020-08-04 19:32:52
树状数组模板用线段树,您牛逼啊
by tobie @ 2020-08-04 19:32:56
别喷了,我就是想学一下单点修改(PS:这道题我用树状数组已经过了)
by Polariserist @ 2020-08-04 19:34:30