树状数组

单点修改，区间查询

#include 
using namespace std;
const int N = 5e5 + 10;
int n, m, tree[N];
int lowbit(int k){
	return k & -k;
}
void update(int x, int k){
	while (x <= n){
		tree[x] += k;
		x += lowbit(x);
	}
}
int query(int x){
	int t = 0;
	while (x != 0){
		t += tree[x];
		x -= lowbit(x);
	}
	return t;
}
void solve(){
	cin >> n >> m;
	for (int i = 1; i <= n; i++){
		int a;
		scanf("%d", &a);
		update(i, a);
	}
	for (int i = 1; i <= m; i++){
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		if (a == 1) update(b, c);
		else cout << query(c) - query(b - 1) << "\n";
	}
}
int main(){
	solve();
	return 0;
}

应用：
模板题：https://www.luogu.com.cn/problem/P3374
逆序对题解：

区间修改，单点查询（差分）

#include 
using namespace std;
const int N = 5e5 + 10;
int n, m, tree[N], num[N];
int lowbit(int k){
	return k & -k;
}
void update(int x, int k){
	while (x <= n){
		tree[x] += k;
		x += lowbit(x);
	}
}
int query(int x){
	int t = 0;
	while (x != 0){
		t += tree[x];
		x -= lowbit(x);
	}
	return t;
}
void solve(){
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		scanf("%d", &num[i]);
	for (int i = 1; i <= m; i++){
		int op, l, r, x;
		scanf("%d", &op);
		if (op == 1){
			scanf("%d%d%d", &l, &r, &x);
			update(l, x);
			update(r + 1, -x);
		}
		else {
			scanf("%d", &x);
			cout << num[x] + query(x) << "\n";
		}
	}
}
int main(){
	solve();
	return 0;
}

模板题：https://www.luogu.com.cn/problem/P3368