题目描述

给定一个长度为n（n<=100000），初始值都为0的序列，x(x<=10000)次的修改某些位置上的数字，每次加上一个数，然后提出y (y<=10000)个问题，求每段区间的和。时间限制1秒。

思路

题目为单点修改加统计和，很容易想到用树状数组，套模板就可以了

#include 
#include 
#include 
using namespace std;
#define maxn 1000001
int c[maxn];
inline int read()
{
    int x=0, p=1; char ch=getchar();
    while (ch < '0' || ch > '9'){if (ch == '-') p=-1; ch=getchar();}
    while (ch >= '0' && ch<='9'){x=(x << 1)+(x << 3)+ch-'0'; ch=getchar();}
    return x*p;
}
int n,m;
int main()
{
    n=read(); m=read();
    for (int k = 1; k <= m; k++)
    {
        char ch;
        cin >> ch;
        int x=read(), y=read();
        if (ch == 'x')
        {
            for (int i = x; i <= n; i += i&(-i))
                c[i] += y;
        }
        else
        {
            int l = 0, r = 0;
            for (int i = y; i > 0; i -= i&(-i))
                r += c[i];
            for (int i = x-1; i > 0; i -= i&(-i))
                l += c[i];
            printf("%d\n", r-l);
        }
    }
}