给定长度为 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]|≤109
输入样例：
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. 树状数组是单点修改，区间查询，而此题是单点查询，区间修改；所以想到了利用差分，来将此题的操作转换为树状数组的操作；
2. 求a[x]相当于差分数组tr[1]+tr[2]…+tr[x]（sum区间查询）；区间加d，a[L~R]+=d，相当于差分数组的L这个位置加上d，r+1的位置减d（两次单点修改add）；

#include <bits/stdc++.h>using namespace std;
typedef long long LL;
const int N = 100010;
int n, m;
int a[N];
LL tr[N];//差分数组int lowbit(int x) {return x & -x;
}void add(int x, int c) {for (int i = x; i <= n; i += lowbit(i)) {tr[i] += c;}
}//差分数组求和，sum[x]就是想要查的a[x]值（a[x]=b[1]+b[2]+...+b[x]）
LL sum(int x) {LL res = 0;for (int i = x; i; i -= lowbit(i)) {res += tr[i];}return res;
}int main() {cin >> n >> m;for (int i = 1; i <= n; ++i) {cin >> a[i];}//建树状数组，差分for (int i = 1; i <= n; ++i) {add(i, a[i] - a[i - 1]);}while (m--) {char op;int l, r, d;cin >> op >> l;//查询if (op == 'Q') {//查询a[l]，相当于[1,l]的前缀和cout << sum(l) << endl;} else {cin >> r >> d;//给区间[l,r]都加上d，相当于下面两个操作//①、l这个位置加上dadd(l, d);//②、r+1的位置减dadd(r + 1, -d);}}return 0;
}