数据结构：树状数组

树状数组可以修改点查询区间和，其修改和查询都是平衡树级别的

其实它本身就是一颗差不多的树

具体原理这里不再叙述，因为已经忘了。。

下面直接给出相应的函数：

修改点：

void update(int x,int y)
{
    while(x<=n)
    {
        c[x]+=y;
        x+=lowbit(x);
    }
}

查询区间和：

int sum(int x)
{
    int ans=0;
    while(x>0)
    {
        ans+=c[x];
        x-=lowbit(x);
    }
    return ans;
}

在使用树状数组的时候，一定要注意题目给出的数据范围，千万不要忘记开long long

下面给出完整实现，这篇博文确实太水了。。

 1 //aininot260 修改点，查询区间和
 2 #include<iostream>
 3 using namespace std;
 4 const int maxn=100005;
 5 const int maxm=10005;
 6 int n,m;
 7 int a[maxn];
 8 int c[maxn];
 9 int lowbit(int x)
10 {
11     return x&(-x);
12 }
13 void update(int x,int y)
14 {
15     while(x<=n)
16     {
17         c[x]+=y;
18         x+=lowbit(x);
19     }
20 }
21 int sum(int x)
22 {
23     int ans=0;
24     while(x>0)
25     {
26         ans+=c[x];
27         x-=lowbit(x);
28     }
29     return ans;
30 }
31 int main()
32 {
33     cin>>n;
34     for(int i=1;i<=n;i++) cin>>a[i];
35     for(int i=1;i<=n;i++) update(i,a[i]);
36     cin>>m;
37     for(int i=1;i<=m;i++)
38     {
39         int x,y,z;
40         cin>>x>>y>>z;
41         if(x==1) update(y,z);
42         if(x==2) cout<<sum(z)-sum(y-1)<<endl;
43     }
44     return 0;
45 }