AcWing：242. 一个简单的整数问题（树状数组）

给定长度为N的数列A，然后输入M行操作指令。

第一类指令形如“C l r d”，表示把数列中第l~r个数都加d。

第二类指令形如“Q X”，表示询问数列中第x个数的值。

对于每个询问，输出一个整数表示答案。

输入格式

第一行包含两个整数N和M。

第二行包含N个整数A[i]。

接下来M行表示M条指令，每条指令的格式如题目描述所示。

输出格式

对于每个询问，输出一个整数表示答案。

每个答案占一行。

数据范围

1≤N,M≤1051≤N,M≤105,
|d|≤10000|d|≤10000,
|A[i]|≤1000000000|A[i]|≤1000000000

输入样例：

10 5

1 2 3 4 5 6 7 8 9 10

Q 4

Q 1

Q 2

C 1 6 3

Q 2

输出样例：

题解：利用树状数组来记录每次改变的值，如果修改[l, r]之间的值，增加val，则令[l, n]加上val，[r + 1, n]减去val，然后查询值得时候，就是用树状数组得查询，然后加上原来数组里面得值就是答案。

#include <iostream>

#include <cstdio>

using namespace std;

typedef long long ll;

const int maxn = 1e5+;

ll arr[maxn];

ll tree[maxn];

int n, m;

int lowbit(int x) {

    return x & (-x);

}

void add(int x, ll val) {

    while(x <= n) {

        tree[x] += val;

        x += lowbit(x);

    }

}

ll ask(int x) {

    ll res = ;

    while(x >= ) {

        res += tree[x];

        x -= lowbit(x);

    }

    return res;

}

int main() {

    scanf("%d %d", &n, &m);

    for(int i = ; i <= n; i++) {

        scanf("%lld", &arr[i]);

    }

    while(m--) {

        char str[];

        int l, r;

        ll val;

        scanf("%s", str);

        if(str[] == 'Q') {

            scanf("%d", &l);

            printf("%lld\n", ask(l) + arr[l]);

        } else {

            scanf("%d%d%lld", &l, &r, &val);

            add(l, val);    //在[l, n]的区间内增加val

            add(r + , -val);    //在[r + 1, n]的区间内减少val

        }

    }

    return ;

}

巴特西