前言

树状数组解法：树状数组+区间更新区间查询
线段树对于区间更新区间查询的问题直接修改更新的函数即可，但每次更新时都把子区间一同更新这样其实是相对暴力的，因为更新完的区间我们可能一次都没有访问到！这里有个关于LazyTag的优化，其实就是让某个区间更新时，只更新其父区间，而对于其子区间我们打一个标记，其含义就是：这个区间的子区间还有更新的任务没做，等到以后的查询动用到它时再临时做(注意，这个标记打在父区间的节点上！可以记录这个区间没个位置要加上的数字)，这样一来对于那些查询区间相对集中，而更新区间相对分散的测试数据效率是十分高的！(Ps:注意区间和可能爆int！要用long long

AC代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <string>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <vector>
#include <utility>

using namespace std;
const int maxn = (int)1e5+5;
typedef long long LL;

struct Node {
	int l,r;
	LL lazy_tag;
	LL sum;
};

int n,q;
LL val[maxn];
Node LTree[maxn << 2];

void pushUp (int idx) {
	LTree[idx].sum = LTree[idx << 1].sum + LTree[idx << 1 | 1].sum;
}

void pushDown (int idx) {
	if (LTree[idx].lazy_tag) {
		LTree[idx << 1].sum += (LTree[idx << 1].r- LTree[idx << 1].l + 1) * LTree[idx].lazy_tag;
		LTree[idx << 1 | 1].sum += (LTree[idx << 1 | 1].r - LTree[idx << 1 | 1].l + 1) * LTree[idx].lazy_tag;
		LTree[idx << 1].lazy_tag += LTree[idx].lazy_tag;
		LTree[idx << 1 | 1].lazy_tag += LTree[idx].lazy_tag; //注意这几个都是+=
		LTree[idx].lazy_tag = 0;
	}
}

void Build (int l, int r, int idx) {
	LTree[idx].l = l;
	LTree[idx].r = r;
	LTree[idx].lazy_tag = 0;
	
	if (l == r) {
		LTree[idx].sum = val[l];
		return ;
	}
	int mid = l + ((r - l) >> 1);
	Build(l, mid, idx << 1);
	Build(mid + 1, r, idx << 1 | 1);
	pushUp(idx);
}

void Modify (int l, int r, int num, int idx) { //[l,r] += num
	if (l <= LTree[idx].l && r >= LTree[idx].r) {
		LTree[idx].sum += (LTree[idx].r - LTree[idx].l + 1) * num;
		LTree[idx].lazy_tag += num;  //注意这里是+=，防止多次更新某个区间出错
		return ;
	}
	pushDown(idx); //下放lazy_tag，因为后面要有新的lazy_tag诞生,并且下面的区间和要更新上来了
	int mid = LTree[idx].l + ((LTree[idx].r - LTree[idx].l) >> 1);
	if (l > mid) {
		Modify(l, r, num, idx << 1 | 1);
	}else if (r <= mid) {
		Modify(l, r, num, idx << 1);
	}else {
		Modify(l, mid, num, idx << 1);
		Modify(mid + 1, r, num, idx << 1 | 1);
	}
	pushUp(idx);
}

LL Query (int l, int r, int idx) {
	if (l <= LTree[idx].l && r >= LTree[idx].r) {
		return LTree[idx].sum;
	}
	pushDown(idx); //下放lazy_tag，因为我要查询其子区间的和了，那个和可能有值还没传下来，所以这步是必要的
	int mid = LTree[idx].l + ((LTree[idx].r - LTree[idx].l) >> 1);
	if (l > mid) {
		return Query(l, r, idx << 1 | 1);
	}else if (r <= mid) {
		return Query(l, r, idx << 1);
	}else {
		return Query(l, mid, idx << 1) + Query(mid + 1, r, idx << 1 | 1);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);	cout.tie(0);
	int i,j,num;
	string command;
	while (cin >> n >> q) {
		for (i = 1; i <= n; i++) {
			cin >> val[i];
		}
		Build(1, n, 1);
		while (q--) {
			cin >> command >> i >> j;
			switch (command.at(0)) {
			case 'Q':
				cout << Query(i, j, 1) << '\n';
				break;
			case 'C':
				cin >> num;
				Modify(i, j, num, 1);
				break;
			default:
				break;
			}
		}
	}
	return 0;
}