题目描述

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

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

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

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

输入格式
第一行包含两个整数N和M。

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

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

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

每个答案占一行。

数据范围
1≤N,M≤105,
|d|≤10000,
|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
输出样例：
4
1
2
5

算法1

相比树状数组，线段树更简单明了 区域处理 区域求和
不必搞差分前缀等处理。
不过用树状数组 更能锻炼思维了.
线段树代码

C++ 代码

/*数据范围
1≤N, M≤105,
| d | ≤10000,
| 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
输出样例：
4
1
2
5

*/

#include <iostream>
#include <string>

using namespace std;



const int N = 1000007;
int arr[N];
int n; int q;


struct Node {
    int l;
    int r;
    long long sum, lazy;

    //该节点范围下所有节点增加x
    void update(long long x) {
        sum += (r - l + 1)*x;
        lazy += x;
    }
}tree[N*4];


void pushup(int x) {
    tree[x].sum = tree[x * 2].sum + tree[x * 2 + 1].sum;
}

void pushdown(int x)
{
    long long lazyval = tree[x].lazy;
    if (lazyval) {
        tree[x*2].update(lazyval);
        tree[x * 2 + 1].update(lazyval);
        tree[x].lazy = 0;
    }
}



void build(int x, int l, int r) {
    tree[x].sum = 0; tree[x].lazy = 0;
    tree[x].l = l; tree[x].r = r;
    if (l == r) {
        tree[x].sum = arr[l];
    }
    else {
        int mid = (l + r) / 2;
        build(x * 2, l, mid);
        build(x * 2+1, mid+1,r );
        pushup(x);
    }
}


void update(int x, int l, int r, int val)
{
    int L = tree[x].l; int R = tree[x].r;

    if (l <= L && r >= R) {
        tree[x].update(val);
    }
    else {
        pushdown(x);
        int mid = (L + R) / 2;
        if (l <= mid) update(x * 2, l, r, val);
        if (r > mid) update(x * 2 + 1, l, r, val);
        pushup(x);
    }
}

long long query(int x, int l, int r)
{
    int L = tree[x].l; int R = tree[x].r;
    if (l <= L && r >= R) {
        return tree[x].sum;
    }
    else {
        pushdown(x);
        int mid = (L + R) / 2;
        long long ans = 0;
        if (l <= mid) ans += query(x * 2, l, r);
        if (r > mid) ans += query(x * 2 + 1, l, r);

        return ans;
    }

    return 0;
}




int main()
{
    //cin >> n >> q;
    scanf("%d%d",&n,&q);

    for (int i = 1; i <= n; i++) {
        //cin >> arr[i];
        scanf("%d",&arr[i]);
    }
    build(1, 1, n);

    for (int i = 1; i <= q; i++) {
        //接收每次询问
        char type[2]; int l, r, val;
        scanf("%s%d",type,&l);

        if (type[0] == 'C') {
            //cin >> l >> r >> val;
            scanf("%d%d",&r,&val);
            update(1, l, r, val);
        }
        else {
            //cin >> l;
            //cout << query(1, l, l) << endl;
            printf("%lld\n", query(1, l, l));
        }
    }

    return 0;
}