【模板】cdq分治代替树状数组（单点修改，区间查询）

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
const int N = (int)1e6 + 5;

int n, m;
struct Q{
	int type, id;
	long long val;
	friend bool operator < (Q x, Q y){
	    return x.id == y.id ? x.type < y.type : x.id < y.id;
	}
}q[N], tmp[N];
int qsize;
long long ans[N];
int asize;

void cdq(int l, int r){//左闭右开
	if(r - l <= 1) return ;//长度为1的区间内部就不会有贡献了
	int mid = l + ((r - l) >> 1);
	cdq(l, mid); cdq(mid, r);
	long long sum = 0;
	int i = l, j = mid, tsize = 0;
        //合并并计算左区间对右区间贡献
	while(i < mid && j < r){
		if(q[i] < q[j]){
			if(q[i].type == 1) sum += q[i].val;
			tmp[++tsize] = q[i++];  
		}
		else {
			if(q[j].type == 2) ans[q[j].val] -= sum;
			else if(q[j].type == 3) ans[q[j].val] += sum;
			tmp[++tsize] = q[j++];
		}
	}
	while(i < mid) tmp[++tsize] = q[i++];
	while(j < r){
		if(q[j].type == 2) ans[q[j].val] -= sum;
		else if(q[j].type == 3) ans[q[j].val] += sum;
		tmp[++tsize] = q[j++];
	}
	for(int i = 1; i <= tsize; ++i) q[l + i - 1] = tmp[i];
}

/*
这部分的思路总结

判断是否到边界
下方左右分治
计算左边对右边的贡献
把左右类似归并排序重排

*/

int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i){
		++qsize;
		q[qsize].id = i, q[qsize].type = 1;
		scanf("%lld", &q[qsize].val);
	}
	for(int i = 1; i <= m; ++i){
		scanf("%d", &q[++qsize].type);
		if(q[qsize].type == 1){
			scanf("%d%lld", &q[qsize].id, &q[qsize].val);
		}
		else {
			int l, r; scanf("%d%d", &l, &r);
			++asize;
			q[qsize].id = l - 1, q[qsize].val = asize;
			q[++qsize].id = r, q[qsize].type = 3, q[qsize].val = asize;
		}
	}
	cdq(1, qsize + 1);
	for(int i = 1; i <= asize; ++i) printf("%lld
", ans[i]); 
	return 0;    
}