题目描述

给定长度为N的数列A，然后输入M行操作指令。
第一类指令形如“C l r d”，表示把数列中第l~r个数都加d。
第二类指令形如“Q X”，表示询问数列中第x个数的值。
对于每个询问，输出一个整数表示答案。

1≤N,M≤10^5,
|d|≤10000,
|A[i]|≤1000000000

输入描述

第一行包含两个整数N和M。
第二行包含N个整数A[i]。
接下来M行表示M条指令，每条指令的格式如题目描述所示。

输出描述

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

输入样例

10 5
1 2 3 4 5 6 7 8 9 10
Q 4
Q 1
Q 2
C 1 6 3
Q 2

输出样例

4
1
2
5

#include <bits/stdc++.h>
#define MAXN 100001
using namespace std;
using ll = long long;

int n,m;
ll tree[MAXN];
ll data[MAXN];

ll lowbit(int x) {
    return x & -x;
}

void add(int x,int data) {
    for (int i = x; i <= n; i += lowbit(i))
        tree[i] += data;
}

ll query(int x) {
    ll ret = data[x];
    for (int i = x; i; i -= lowbit(i)) 
        ret += tree[i];

    return ret;
}

int main() {
    ios::sync_with_stdio(false);

    cin >> n >> m;

    for (int i = 1; i <= n; ++i)
        cin >> data[i];

    char op;
    int a,b,c;
    for (int i = 1; i <= m; ++i) {
        cin >> op;
        if(op == 'Q') {
            cin >> a;

            cout << query(a) << endl;;
        } else {
            cin >> a >> b >> c;

            add(a, c);
            add(b + 1, -c);
        }
    }

    return 0;
}