05差分树状数组

神奇的树状数组啊

vi tr(N);
 
//初始化数组
void init(int len){
	fill(tr.begin(), tr.ebgin() + len + 1, 0);
}
 
//去只是需要更新的区间的操作
void add1(int l, int r, int k){
	add2(l, k);
	if(r < n) add2(r + 1, -k);
}
 
//真正的操作，实际上应该写在 add1 前面，此处是按照思路顺序写的
void add2(int l, int k){
	for(int i = l; i <= n; i += (i & (-i)){ //也可以平时的树状数组一样写出去
		tr[i] += k;
	}
}
 
//这里一般需要改编， 这里的实例属于普通前缀和一下，如果需要计算某一段区间，那就计算两个前缀和
int sum(int l){
	int ans = 0;
	for(int i = l; i; i -= (i & (-i))){
		ans += tr[i];
	}
	return ans;
}