树状数组是个好东西，写起来也相对好看。但是操作比较局限，区间修改就掉回\(O(nlogn)\)， 那还不如 \(O(n)\)。线段树完美的解决问题。

线段树，也可以理解的一堆线段组成的树。

大致如上，有一线段 \([l, r]\) 当 \(l \ne r\) 可化为 \([l, mid]\) , \([mid + 1, r]\)

PS: \(mid = (l + r) / 2\)

增加

此操作 不是 新加节点，是将一段区间增加一个数。

将 [2, 9] 每个数增加 1

像这样通过递归的方式修改这些节点，然后我们惊喜的发现，访问了 \(n logn\) 个节点......似乎不如没有

这个时候lazy_tag登场（懒人tag）

蓝色的就是lazy_tag(下文称为tag)，标记增加了多少， 这时 \([2,2], [3,3],[4,5], [6,8], [9,9]\) 都有 tag = 1。

用处放到下文

查询

这里，我们可以查询区间的和

在上例子里我们查询 [1, 1]时，不会有问题，查询 [1, 2]时，不会有问题， 查询 [1, 10]时，不会有问题， 但是查询 [6, ]7时，会有问题， 因为没有修改到。

因为 [6, 8] 被标有tag， 然而，在访问 [6, 7]时一定会访问到6, 8，那么我们便可以将tag传下来。

也就是不访问就不修改。

运用以上方案，就可以实现单点修改，单点查询，区间修改（同增同减）， 区间查询。

#include<iostream>

using namespace std;

const long long kMaxN = 1e5 + 5; 

long long n, m, a[kMaxN << 2]; //注意开大4倍

struct L {
	long long sum, tag;
} sgt[kMaxN << 2];

void push_up(long long rt) { //更新这个节点
	sgt[rt].sum = sgt[rt << 1].sum + sgt[rt << 1 | 1].sum;
}	


void build_tree(long long rt, long long l, long long r) { //建树
	sgt[rt].tag=0;
	if (l == r) {
		sgt[rt].sum = a[l];
		return;
	}
	long long mid = l + r >> 1; 
	build_tree(rt << 1, l, mid), build_tree(rt << 1 | 1, mid + 1, r);
	push_up(rt);
}

void add_tag(long long rt, long long l, long long r,long long d) {//建立tag
	sgt[rt].tag += d;
	sgt[rt].sum += d * (r - l + 1);//值也增加
}

void push_down(long long rt, long long l, long long r) { //tag往下传
	if (sgt[rt].tag) {
		long long mid = l + r >> 1;
		add_tag(rt << 1, l, mid, sgt[rt].tag);
		add_tag(rt << 1 | 1, mid + 1, r, sgt[rt].tag);
		sgt[rt].tag = 0;
	}
}

void update(long long L, long long R, long long rt, long long l, long long r, long long d){ //更新[l, r]的值 + d
	if (L <= l && r <= R) {
		add_tag(rt, l, r, d);
		return;
	}
	push_down(rt, l, r);
	long long mid = l + r >> 1;
	if (L <= mid) {
		update(L, R, rt << 1, l, mid, d);
	} if (mid < R) {
		update(L, R, rt << 1 | 1, mid + 1, r, d);
	}
	push_up(rt);
} 

long long query(long long L, long long R, long long rt, long long l, long long r) {//找到 [L, R] 的和
	if (L <= l && r <= R) {
		return sgt[rt].sum;
	}
	push_down(rt, l, r);
	long long mid = l + r >> 1, ans = 0;
	if (L <= mid) {
		ans += query(L, R, rt << 1, l, mid);
	} 
	if (mid < R) {
		ans += query(L, R, rt << 1 | 1, mid + 1, r);
	}
	return ans;
}

int main(){
	cin >> n >> m;
	for (long long i = 1; i <= n; i++) {
		cin >> a[i];
	}
	build_tree(1, 1, n);
	for(long long i = 1, a, x, y, d; i <= m; i++) {
		cin >> a >> x >> y;
		if (a == 1) {
			cin >> d;
			update(x, y, 1, 1, n, d);
		} else {
			cout << query(x, y, 1, 1, n) << '\n';
		}
	}
	return 0;
}