树状数组
作者:
routine_89
,
2024-02-01 16:14:11
,
所有人可见
,
阅读 58
题目链接
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+50;
int n,m;
int a[N],tr[N];
// tr[x]=a[x-lowbit(x),x] 的和
int lowbit(int x) //返回x最后一个一
{
return x & -x;
}
void add(int x, int c) // 给x位置加上一个数 c,并更新前缀和。
{
for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}
int query(int x) // 求 1 ~ x 的前缀和
{
int res = 0;
for (int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) add(i,a[i]);
while (m -- )
{
int k,x,y;
scanf("%d%d%d",&k,&x,&y);
if(k==2) printf("%d\n",query(y)-query(x-1));
if(k==1) add(x,y);
}
return 0;
}