【模板】线段树

#include <iostream>
#define int long long
using namespace std;
const int MAXX = 1e5 + 11;
int a[MAXX];
struct node {
	int l,r,sum,add; // add 为懒标记
} tree[MAXX * 4];
void pushup(int pos) {
	tree[pos].sum = tree[pos * 2].sum + tree[pos * 2 + 1].sum;
}
void build(int pos,int l,int r) { // 建树
	tree[pos].l = l;
	tree[pos].r = r;
	tree[pos].sum = a[l];
	if (l == r) {
		return ;
	}
	int mid = (l + r) >> 1;
	build(pos * 2,l,mid); // 左子树建树
	build(pos * 2 + 1,mid + 1,r); // 右子树建树
	pushup(pos);
}
void pushdown(int pos) {
	if (tree[pos].add) {
		tree[pos * 2].sum += tree[pos].add * (tree[pos * 2].r - tree[pos * 2].l + 1);
		tree[pos * 2 + 1].sum += tree[pos].add * (tree[pos * 2 + 1].r - tree[pos * 2 + 1].l + 1);
		tree[pos * 2].add += tree[pos].add;
		tree[pos * 2 + 1].add += tree[pos].add;
		tree[pos].add = 0;
	}
}
void update(int pos,int x,int y,int k) { // 区间修改
	if (tree[pos].l >= x and tree[pos].r <= y) { // 找到了叶子节点
		tree[pos].sum += (tree[pos].r - tree[pos].l + 1) * k;
		tree[pos].add += k;
		return ;
	}
	int mid = (tree[pos].l + tree[pos].r) >> 1;
	pushdown(pos);
	if (x <= mid) {
		update(pos * 2,x,y,k);
	}
	if (y > mid) {
		update(pos * 2 + 1,x,y,k);
	}
	pushup(pos);
}
int query(int pos,int x,int y) { // 区间查询
	if (tree[pos].l >= x and tree[pos].r <= y) {
		return tree[pos].sum;
	}
	int mid = (tree[pos].l + tree[pos].r) >> 1;
	pushdown(pos);
	int sum = 0;
	if (x <= mid) {
		sum += query(pos * 2,x,y);
	}
	if (y > mid) {
		sum += query(pos * 2 + 1,x,y);
	}
	return sum;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0) , cout.tie(0);
	int n,m;
	cin >> n >> m;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
	}
	build (1,1,n);
	while (m --) {
		int op;
		cin >> op;
		if (op == 1) {
			int x,y,k;
			cin >> x >> y >> k;
			update(1,x,y,k);
		} else {
			int x,y;
			cin >> x >> y;
			cout << query(1,x,y) << "\n";
		}
	}
}