@[red_farmer](https://www.luogu.com.cn/user/564329) 不需要用差分数组的
~~验证码3pjc祭~~
下面是我的AC代码
```
#include<iostream>
#include<cstring>
using namespace std;
int n,m,a[500010],c[500010];
int f,x,y;
inline int lowbit(int x)
{
x=x&(-x);
return x;
}
int updata(int k,int x)
{
for(int i=k;i<=n;i+=lowbit(i))
{
c[i]+=x;
}
}
int getsum(int k)
{
int sum=0;
for(int i=k;i>0;i-=lowbit(i))
{
sum+=c[i];
}
return sum;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
updata(i,a[i]);
}
while(m--)
{
cin>>f>>x>>y;
if(f==2)
{
cout<<getsum(y)-getsum(x-1)<<endl;
}
else
{
updata(x,y);
}
}
return 0;
}
```
by huwanpeng @ 2021-10-10 13:49:34
@[huwanpeng](/user/525152) 用差分不是可以降复杂度吗？
by red_farmer @ 2021-10-10 13:51:49
@[red_farmer](/user/564329) 复杂度还是 $\mathcal O(n\log n)$，但可能提高效率
by ADay @ 2021-10-10 14:01:33
@[ADay](/user/312393) 大佬可以帮我看看是错在哪儿吗？qwq
by red_farmer @ 2021-10-10 14:17:39
@[red_farmer](/user/564329)
```cpp
for(int i=n;i>=1;i--) t[i]-=t[lowbit(i)];
```
改为
```cpp
for(int i=n;i>=1;i--) t[i]-=t[i-lowbit(i)];
```
就过了
by ADay @ 2021-10-10 14:38:22
@[ADay](/user/312393) 谢谢大佬，我无地自容了，浪费了您宝贵的时间
by red_farmer @ 2021-10-10 15:36:44
@[ADay](/user/312393) 抱歉
by red_farmer @ 2021-10-10 15:37:12
@[red_farmer](/user/564329) 我不是大佬啊我很菜的
by ADay @ 2021-10-10 16:42:00