树状数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
const int maxn=550000;
int c[maxn],n,m,tmp1,odd,x,y;
int lowbit(int x)
{
return x&(-x);
}
void change(int x,int z)
{
while(x<=n)
c[x]+=z,x+=lowbit(x);
}
int xfind(int x)
{
int ans=0;
while(x>0)ans+=c[x],x-=lowbit(x);
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
scanf("%d",&tmp1),change(i,tmp1);
for(int i=1;i<=m;++i)
{
scanf("%d%d%d",&odd,&x,&y);
if(odd==1)change(x,y);
else printf("%d\n",xfind(y)-xfind(x-1));
}
return 0;
}
显示 Gitment 评论