AcWing 243. 一个简单的整数问题2

线段树不是一个算法，而是一个对区间进行修改、维护的工具。

AcWing 243. 一个简单的整数问题2

题目大意:

给定一个长度为$N$的数列$A$，以及$M$条指令，每条指令可能是以下两种之一：

1. C l r d，表示把$A[l],A[l+1], \ldots,A[r]$都加上$d$。
2. Q l r，表示询问数列中第$l \sim r$个数的和。

对于每个询问，输出一个整数表示答案。

思路:

带懒标记的线段树区间和板子题

Code:

int n,m;
int w[N];
struct node{
	int l,r;
	int sum,add;
}tr[N * 4];

void pushup(int u){
	tr[u].sum = tr[u << 1].sum + tr[u << 1|1].sum;
}

void pushdown(int u){
	//&引用
	auto &root = tr[u],&left = tr[u << 1],&right = tr[u << 1|1];
	if (root.add){
		left.add += root.add,left.sum += (left.r - left.l + 1) * root.add;
		right.add += root.add,right.sum += (right.r - right.l + 1) * root.add;
		root.add = 0;
	}
}

void build(int u,int l,int r){
	if (l == r)	tr[u] = {l,r,w[r],0};
	else{
		tr[u] = {l,r};
		int mid = l + r >> 1;
		build(u << 1,l,mid),build(u << 1|1,mid + 1,r);
		pushup(u);
	}
}

void modify(int u,int l,int r,int d) {
	if (tr[u].l >= l && tr[u].r <= r) {
		tr[u].sum += (tr[u].r - tr[u].l + 1) * d;
		tr[u].add += d;
	}else {  //分裂
		pushdown(u);
		int mid = tr[u].l + tr[u].r >> 1;
		if (l <= mid)	modify(u << 1,l,r,d);
		if (r > mid)	modify(u << 1|1,l,r,d);
		pushup(u);
	}
}

int query(int u,int l,int r) {
	if (tr[u].l >= l && tr[u].r <= r)	return tr[u].sum;
	
	pushdown(u);
	int mid = tr[u].l + tr[u].r >> 1;
	int sum = 0;
	if (l <= mid)	sum = query(u << 1,l,r);
	if (r > mid)	sum += query(u << 1|1,l,r);
	return sum;
}

void solve()
{
	cin >> n >> m;
	for (int i = 1;i <= n;i ++)	cin >> w[i];
	build(1,1,n);
	char ch;
	int l,r,d;
	while(m --) {
		cin >> ch >> l >> r;
		if (ch == 'C') {
			cin >> d;
			modify(1,l,r,d);
		} else {
			cout << query(1,l,r) << '\n';
		}
	}
}