树状数组:

求区间和

#include<iostream>
#define int long long //区间求和可能会爆int
using namespace std;
const int N = 100010;
int n,m;
int tr[N];
int lowbit(int x) //返回最后一位1的位置,树状数组操作的基础
{
    return x & -x;
}
void add(int x,int c) //在树状数组索引为x的位置加上c,后更新其父节点
{
    for(int i=x;i<=n;i+=lowbit(i)) tr[i] += c;
}
int ask(int x) //求1~x区间和
{
    int sum = 0;
    for(int i=x;i;i-=lowbit(i)) sum += tr[i];
    return sum;
}
signed main()
{
    scanf("%lld%lld",&n,&m);
    while(m--)
    {
        int k,a,b,c;
        scanf("%lld",&k);
        if(k==0)
        {
            scanf("%lld%lld",&a,&c);
            add(a,c);
        }else
        {
            scanf("%lld%lld",&a,&b);
            printf("%lld\n",ask(b)-ask(a-1)); 
            //求[a,b]就是[1,b]的和减去[1,a-1]的和
        }
    }
    return 0;
}