线段树模板题

• 洛谷3372 线段树区间加法/区间求和
• 洛谷3373 线段树区间加法/区间乘法/区间求和

洛谷3372 线段树区间加法/区间求和

// by DTTTTTTT 2023/6/2
// Luogu 3372
#include<iostream>
#define ll long long
#define lc (p<<1)
#define rc (p<<1|1)
using namespace std;
const int N = 1e5 + 5;
int n, m, a[N];
struct node {
	int l, r;
	ll sum, tag;
}t[N << 2];

void build(int p, int l, int r) {
	t[p].l = l, t[p].r = r, t[p].tag = 0;
	if (l == r) {
		t[p].sum = a[l];
		return;
	}
	int mid = t[p].l + t[p].r >> 1;
	build(lc, l, mid);
	build(rc, mid + 1, r);
	t[p].sum = t[lc].sum + t[rc].sum;
}
void pushdown(int p) {
	if (t[p].l == t[p].r || t[p].tag == 0)
		return;
	t[lc].sum += (t[lc].r - t[lc].l + 1) * t[p].tag;
	t[rc].sum += (t[rc].r - t[rc].l + 1) * t[p].tag;
	t[lc].tag += t[p].tag;
	t[rc].tag += t[p].tag;
	t[p].tag = 0;
}
void add(int p, int l, int r, ll k) {
	if (t[p].l >= l && t[p].r <= r) {
		t[p].sum += (t[p].r - t[p].l + 1) * k;
		t[p].tag += k;
		return;
	}
	pushdown(p);
	int mid = t[p].l + t[p].r >> 1;
	if (l <= mid)
		add(lc, l, r, k);
	if (r > mid)
		add(rc, l, r, k);
	t[p].sum = t[lc].sum + t[rc].sum;
}
ll query(int p, int l, int r) {
	if (t[p].l >= l && t[p].r <= r)
		return t[p].sum;
	pushdown(p);
	int mid = t[p].l + t[p].r >> 1;
	ll ret = 0;
	if (l <= mid)
		ret += query(lc, l, r);
	if (r > mid)
		ret += query(rc, l, r);
	return ret;
}
int main() {
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	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 l, r;
			ll k;
			cin >> l >> r >> k;
			add(1, l, r, k);
		}
		else { //统计
			int l, r;
			cin >> l >> r;
			cout << query(1, l, r) << endl;
		}
	}
	return 0;
}

洛谷3373 线段树区间加法/区间乘法/区间求和

// by DTTTTTTT 2023/6/2
// Luogu 3373
#include<iostream>
#define ll long long
#define lc (p<<1)
#define rc (p<<1|1)
using namespace std;
const int N = 1e5 + 5;
int n, m, mod, a[N];
struct node {
	int l, r, sum, mul_tag, add_tag;
}t[N << 2];
void build(int p, int l, int r) {
	t[p].l = l, t[p].r = r, t[p].mul_tag = 1, t[p].add_tag = 0;
	if (l == r) {
		t[p].sum = a[l];
		return;
	}
	int mid = t[p].l + t[p].r >> 1;
	build(lc, l, mid);
	build(rc, mid + 1, r);
	t[p].sum = t[lc].sum + t[rc].sum;
}
void pushdown(int p) {
	if (t[p].l == t[p].r || (t[p].mul_tag == 1 && t[p].add_tag == 0))
		return;
	
	t[lc].sum = (1ll * t[lc].sum * t[p].mul_tag % mod + 1ll * (t[lc].r - t[lc].l + 1) * t[p].add_tag % mod) % mod;
	t[rc].sum = (1ll * t[rc].sum * t[p].mul_tag % mod + 1ll * (t[rc].r - t[rc].l + 1) * t[p].add_tag % mod) % mod;
	t[lc].mul_tag = 1ll * t[lc].mul_tag * t[p].mul_tag % mod;
	t[rc].mul_tag = 1ll * t[rc].mul_tag * t[p].mul_tag % mod;
	t[lc].add_tag = (1ll * t[lc].add_tag * t[p].mul_tag % mod + t[p].add_tag) % mod;
	t[rc].add_tag = (1ll * t[rc].add_tag * t[p].mul_tag % mod + t[p].add_tag) % mod;

	t[p].mul_tag = 1, t[p].add_tag = 0;
}
void mul(int p, int l, int r, int k) {
	if (t[p].l >= l && t[p].r <= r) {
		t[p].sum = 1ll * t[p].sum * k % mod;
		t[p].mul_tag = 1ll * t[p].mul_tag * k % mod;
		t[p].add_tag = 1ll * t[p].add_tag * k % mod;
		return;
	}
	pushdown(p);
	int mid = t[p].l + t[p].r >> 1;
	if (l <= mid)
		mul(lc, l, r, k);
	if (r > mid)
		mul(rc, l, r, k);
	t[p].sum = (t[lc].sum + t[rc].sum) % mod;
}
void add(int p, int l, int r, int k) {
	if (t[p].l >= l && t[p].r <= r) {
		t[p].sum = (t[p].sum + 1ll * (t[p].r - t[p].l + 1) * k % mod) % mod;
		t[p].add_tag = (t[p].add_tag + k) % mod;
		return;
	}
	pushdown(p);
	int mid = t[p].l + t[p].r >> 1;
	if (l <= mid)
		add(lc, l, r, k);
	if (r > mid)
		add(rc, l, r, k);
	t[p].sum = (t[lc].sum + t[rc].sum) % mod;
}
int query(int p, int l, int r) {
	if (t[p].l >= l && t[p].r <= r)
		return t[p].sum;
	pushdown(p);
	int mid = t[p].l + t[p].r >> 1;
	int ret = 0;
	if (l <= mid)
		ret += query(lc, l, r), ret %= mod;
	if (r > mid)
		ret += query(rc, l, r), ret %= mod;
	return ret;
}
int main() {
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n >> m >> mod;
	for (int i = 1;i <= n;++i)
		cin >> a[i];
	build(1, 1, n);
	for (int i = 1;i <= m;++i) {
		int op;
		cin >> op;
		if (op == 1) { //乘法
			int l, r, k;
			cin >> l >> r >> k;
			mul(1, l, r, k);
		}
		else if (op == 2) { //加法
			int l, r, k;
			cin >> l >> r >> k;
			add(1, l, r, k);
		}
		else { //求和
			int l, r;
			cin >> l >> r;
			cout << query(1, l, r) << endl;
		}
	}
	return 0;
}