04 树状数组

01区间修改

区间修改，一般使用差分代替,

以下这个模板属于区间整体加上一个值，然后单点查询， 相比于线段树操作，代码量少太多了

void BIT_opt(int x, int len, int k){
	for(int i = x; i <= len; i += (i & (-i))){
		tr[i] += k;
	}
	return;
}
 
int query(int x){
	int ans = 0;
	for(int i = x; i; i -= (i & (-i))){
		ans += tr[i];
	}
	return ans;
}
 
solve(){
	vi a(n + 1);
	rep(i, 1, n){
		cin >> a[i];
		BIT_opt(i, n, a[i] - a[i - 1]); //初始化的时候就要差分
	}
	
	while(q --){
		int type; cin >> type;
		if(type == 1){
			int x, y, k; cin >> x >> y >> k;
			BIT_opt(x, n, k);
			if(y < n) BIT_opt(y + 1, n, -k);
		}else{
			int x; cin >> x;
			cout << BIT_query(x) << endl;
		}
	}
	return;
}

02权值树状数组

权值树状数组，就是把数字作为桶， 求逆序对就是其中一种使用
它与普通树状数组的区别，往往在于我们处理一个放进去一个，而不是一下子把全部都放进去

03离线扫描 BIT

将查询全都储存下来，按照 r 排序， 然后处理，实际上就是离线排序 + 权值树状数组

04二维偏序/BIT

问题类型

单点查询， 对于每个 $i$ ， 有多少个 $j$ ， 满足 $x_i<x_j$ , $y_i<y_j$

问题区分

对于交换问题，需要区分，任意两个数字交换还是必须相邻数字交换时所需的交换次数

交换规则	交换次数	计算方法
相邻数字交换	逆序对个数	树状数组/归并排序
任意两个数字交换	$n$ - 置换循环节个数	找环
注：对于第二种情况，可以看置换群的笔记

05二维BIT

区间操作，区间查询
下面写的较为笼统，实际操作的时候 + 1 , - 1 的地方记得注意边界

vii tr1(N, vi(N)), tr2(N, vi(N)), tr3(N, vi(N)), tr4(N, vi(N));
 
void BIT_opt(int x, int y, int k){
	for(int i = x; i <= n; i ++ (i & (-i))){
		for(int j = y; j <= n; j += (j & (-j))){
			tr1[i][j] += k;
			tr2[i][j] += x * k;
			tr3[i][j] += y * k;
			tr4[i][j] += x * y * k;
		}
	}
}
 
int BIT_query(int x, int y){
	int ans = 0;
	for(int i = x; i; i -= (i & (-i))){
		for(int j = y; j; j -= (i & (-i))){
			ans += tr1[i][j] * (x + 1) * (y + 1) - tr2[i][j] * (y + 1) - tr3[i][j] * (x + 1) + tr4[i][j];
		}
	}
	return ans;
}
 
void solve(){
	while(q --){
		int type; cin >> type;
		if(type){
			int x1, y1, x2, y2, k; cin >> x1 >> y1 >> x2 >> y2 >> k;
			BIT_opt(x1, y2, k);
			BIT_opt(x2 + 1, y1, - k);
			BIT_opt(x1, y2 + 1, - k);
			BIT_opt(x2 + 1, y2 + 1, k);
		}else{
			int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
			cout << BIT_query(x2, y2) + BIT_query(x1 - 1, y1 - 1) - BIT_query(x1 - 1, y2) - BIT_query(x2, y1 - 1) << endl;
		}
	}
}