单点修改，区间查询树状数组，洛谷P3374
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n, m, a[N];
int chaxun(int n){int ans = 0;while(1){ans += a[n];int x = n & -n;n -= x;if(n == 0) break;}return ans;
}
void xiugai(int n, int d){while(1){a[n] += d;int x = n & -n;n += x;if(n >= N) break;}return;
}
int main(){int f, x, y;cin >> n >> m;for(int i = 1; i <= n; i++){cin >> x;xiugai(i,x); }while(m--){cin >> f >> x >> y;if(f == 1) xiugai(x, y);if(f == 2){cout << chaxun(y) - chaxun(x-1) << endl;}}return 0;
}
区间修改，单点查询树状数组，洛谷P3368
把上面那个改成在原数组差分数组上做
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n, m, s[N], a[N];
int chaxun(int n){int ans = 0;while(1){ans += s[n];int x = n & -n;n -= x;if(n == 0) break;}return ans;
}
void xiugai(int n, int d){while(1){s[n] += d;int x = n & -n;n += x;if(n >= N) break;}return;
}
int main(){int f, x, y, k;cin >> n >> m;for(int i = 1; i <= n; i++){cin >> a[i];x = a[i] - a[i-1];xiugai(i,x); }while(m--){cin >> f;if(f == 1){cin >> x >> y >> k;xiugai(x,k);xiugai(y+1,-k);}if(f == 2){cin >> x;cout << chaxun(x) << endl;}}return 0;
}