AcWing 1264. 动态求连续区间和
原题链接
简单
作者:
Bear_King
,
2021-01-18 17:42:15
,
所有人可见
,
阅读 347
树状数组操作
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 100010;
int n,m;
int a[N],tr[N];
int lowbit(int x)
{
return x & -x;
}
void add(int x,int v)
{
for(int i = x; i <= n ;i += lowbit(i)) tr[i] += v;
}
int query(int 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 == 0) printf("%d\n",query(y) - query(x-1));
else add(x,y);
}
return 0;
}