线段树模板

读完题目我们可以知道本题是区间修改区间查询

不难想到线段树（毕竟都叫 线段树1 了）

线段树思路

开数组存线段树

线段树要开4倍数组，因为每个节点都有至多两个子节点，编号为n的4倍

struct Node {
	int l, r;
	ll sum, add;
}tr[N << 2];

区间修改需要懒标记来维护复杂度

建树的函数build

通过递归左右子节点来建树，保证树高为 log n

void pushup (int u) {  //通过左右子节点计算父节点区间和
	tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void build(int u, int l, int r) {
	tr[u] = {l, r};
	if(l == r) {  //如果递归到叶子节点，直接赋值，结束递归
		tr[u].sum = a[l];
		return;
	}
	int mid = tr[u].l + tr[u].r >> 1;  //将该节点二分，递归左右节点
	build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
	pushup(u);
}

区间修改modify

同样递归遍历节点

void pushdown(int u) {  //将懒标记传给子节点，更新子节点sum
	if(tr[u].add) {
		ll c = tr[u].add;
		tr[u << 1].sum += (ll)(tr[u << 1].r - tr[u << 1].l + 1) * c;
		tr[u << 1].add += c;
		tr[u << 1 | 1].sum += (ll)(tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1) * c;
		tr[u << 1 | 1].add += c;
		tr[u].add = 0;  //清空父节点懒标记
	}
}
void modify (int u, int l, int r, ll c) {
	if(tr[u].l >= l && tr[u].r <= r) { //如果该节点完全在所修改区间内，更新sum，更新懒标记
  		tr[u].sum += (ll)(tr[u].r - tr[u].l + 1) * c;
		tr[u].add += c;
		return;//结束递归
	}
//否则继续递归
	int mid = tr[u].l + tr[u].r >> 1;
	pushdown(u);  //递归前保证sum为真实值
	if(l <= mid) modify(u << 1, l, r, c);//如果修改区间覆盖到左子结点，递归左子结点
	if(r > mid) modify(u << 1 | 1, l, r, c);//同理递归右子节点
	pushup(u);
}

区间查询query

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

# include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MID int mid = tr[u].l + tr[u].r >> 1
const int N = 1e5 + 10;
int n, m;
int a[N];
struct Node {
	int l, r;
	ll sum, add;
}tr[N << 2];
void pushup (int u) {
	tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void build(int u, int l, int r) {
	tr[u] = {l, r};
	if(l == r) {
		tr[u].sum = a[l];
		return;
	}
	MID;
	build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
	pushup(u);
}
void pushdown(int u) {
	if(tr[u].add) {
		ll c = tr[u].add;
		tr[u << 1].sum += (ll)(tr[u << 1].r - tr[u << 1].l + 1) * c;
		tr[u << 1].add += c;
		tr[u << 1 | 1].sum += (ll)(tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1) * c;
		tr[u << 1 | 1].add += c;
		tr[u].add = 0;
	}
}
void modify (int u, int l, int r, ll c) {
	if(tr[u].l >= l && tr[u].r <= r) {
		tr[u].sum += (tr[u].r - tr[u].l + 1) * c;
		tr[u].add += c;
		return;
	}
	MID;
	pushdown(u);
	if(l <= mid) modify(u << 1, l, r, c);
	if(r > mid) modify(u << 1 | 1, l, r, c);
	pushup(u);
}
ll query (int u, int l, int r) {
	if(tr[u].l >= l && tr[u].r <= r) {
		return tr[u].sum;
	}
	MID;
	pushdown(u);
	ll ans = 0;
	if(l <= mid) ans = query(u << 1, l, r);
	if(r > mid) ans += query(u << 1 | 1, l, r);
	return ans;
}
int main () {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i ++) cin >> a[i];
	build(1, 1, n);
	while(m --) {
		int op, l, r;
		cin >> op >> l >> r;
		if(op == 1) {
			ll c;
			cin >> c;
			modify(1, l, r, c);
		} else {
			cout << query(1, l, r) << '\n';
		}
	}
	return 0;
}

可以根据个人习惯更改