AcWing 243. 一个简单的整数问题2（pushdown模板题，区间加数，区间求和）

思想：访问到树中结点时不再下降，查询时再更新。

const int N = 1e5 + 5;
int t;
int w[N];
struct node
{
	int l, r;
	ll sum, add;
}tr[4*N];
void pushup(int u)
{
	tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void pushdown(int u)
{
	node &root = tr[u], &le = tr[u << 1], &re = tr[u << 1 | 1];
	if (root.add)
	{
		le.add += root.add, le.sum += (ll)(le.r - le.l + 1)*root.add;
		re.add += root.add, re.sum += (ll)(re.r - re.l + 1)*root.add;
		root.add = 0;
	}
}
void build(int u, int l, int r)
{
	if (l == r)tr[u] = { l,r,w[l],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 += (ll)(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);
	}
}
ll 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;
	ll sum = 0;
	if (l <= mid)sum += query(u << 1, l, r);
	if (r > mid)sum += query(u << 1 | 1, l, r);
	return sum;
}
int main()
{
   // freopen("in.txt", "r", stdin);
	int n, m;
	scanf("%d%d", &n, &m);
	f(i, 1, n)scanf("%d", &w[i]);
	string op;
	int l, r, d;
	build(1, 1, n);
	while (m--)
	{
		cin >> op;
		scanf("%d %d", &l, &r);
		if (op == "C")
		{
			scanf("%d", &d);
			modify(1, l, r, d);
		}
		else printf("%lld\n", query(1,l,r));
	}
	return 0;
}