JZTXT

线段树

发布时间 2023-08-31 17:33:51作者: RonChen

P3372【模板】线段树 1

参考代码 
#include <cstdio>
#define LC (cur*2)
#define RC (cur*2+1)
typedef long long LL;
const int MAXN = 500005;
struct Node {
	int l, r;
	LL value, add;
};
LL a[MAXN];
Node tree[MAXN*4];
void pushup(int cur) {
	tree[cur].value = tree[LC].value + tree[RC].value;
}
void build(int cur, int l, int r) {
	tree[cur].l = l;
	tree[cur].r = r;
	if (l == r) {
		tree[cur].value = a[l];
		return;
	}
	int mid = (l + r) / 2;
	build(LC, l, mid);
	build(RC, mid+1, r);
	pushup(cur);
}
void work(int cur, LL x) {	//对cur这个节点进行具体的更新操作
	tree[cur].value += x * (tree[cur].r-tree[cur].l+1);
	tree[cur].add += x;
}
void pushdown(int cur) {
	if (tree[cur].add != 0) {
		work(LC, tree[cur].add); work(RC, tree[cur].add);
		tree[cur].add = 0;
	}
}
void update(int cur, int l, int r, LL delta) {
	if (tree[cur].l >= l && tree[cur].r <= r) {
		work(cur, delta);
		return;
	}
	pushdown(cur);
	int mid = (tree[cur].l + tree[cur].r) / 2;
	if (mid >= l) update(LC, l, r, delta);
	if (mid < r) update(RC, l, r, delta);
	pushup(cur);
}
LL query(int cur, int l, int r) { // 区间查询
	if (tree[cur].l >= l && tree[cur].r <= r) { // 完全包含
		return tree[cur].value;
	}
	pushdown(cur);
	int mid = (tree[cur].l + tree[cur].r) / 2;
	LL res = 0;
	if (mid >= l) res += query(LC, l, r);
	if (mid < r) res += query(RC, l, r);
	return res;
}
int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
	build(1, 1, n);
	while (m--) {
		int op;
		scanf("%d", &op);
		if (op == 1) {
			int x, y;
			LL k;
			scanf("%d%d%lld", &x, &y, &k);
			update(1, x, y, k);
		} else {
			int x, y;
			scanf("%d%d", &x, &y);
			printf("%lld\n", query(1, x, y));
		}
	}
	return 0;
}

P1253 扶苏的问题

参考代码 
#include <cstdio>
#include <algorithm>
#define LC (cur*2)
#define RC (cur*2+1)
using namespace std;
typedef long long LL;
const int MAXN = 1000005;
const LL INF = 1e16;
struct Node {
	int l, r;
	LL value, add, cover;
};
LL a[MAXN];
Node tree[MAXN*4];
void pushup(int cur) {
	tree[cur].value = max(tree[LC].value, tree[RC].value);
}
void build(int cur, int l, int r) {
	tree[cur].l = l;
	tree[cur].r = r;
	tree[cur].cover = INF;
	if (l == r) {
		tree[cur].value = a[l];
		return;
	}
	int mid = (l + r) / 2;
	build(LC, l, mid);
	build(RC, mid+1, r);
	pushup(cur);
}
void work(int cur, LL x, int op) { //对cur这个节点进行具体的更新操作
	if (op == 1) {
		tree[cur].value = tree[cur].cover = x;
		tree[cur].add = 0;
	} else {
		tree[cur].value += x;
		if (tree[cur].cover != INF) tree[cur].cover += x;
		else tree[cur].add += x;
	}
}
void pushdown(int cur) {
	if (tree[cur].cover != INF) {
		work(LC, tree[cur].cover, 1); work(RC, tree[cur].cover, 1);
		tree[cur].cover = INF;
	}
	if (tree[cur].add != 0) {
		work(LC, tree[cur].add, 2); work(RC, tree[cur].add, 2);
		tree[cur].add = 0;
	}
}
void update(int cur, int l, int r, LL delta, int op) {
	if (tree[cur].l >= l && tree[cur].r <= r) {
		work(cur, delta, op);
		return;
	}
	pushdown(cur);
	int mid = (tree[cur].l + tree[cur].r) / 2;
	if (mid >= l) update(LC, l, r, delta, op);
	if (mid < r) update(RC, l, r, delta, op);
	pushup(cur);
}
LL query(int cur, int l, int r) { // 区间查询
	if (tree[cur].l >= l && tree[cur].r <= r) { // 完全包含
		return tree[cur].value;
	}
	pushdown(cur);
	LL res = -INF;
	int mid = (tree[cur].l + tree[cur].r) / 2;
	if (mid >= l) res = max(res, query(LC, l, r));
	if (mid < r) res = max(res, query(RC, l, r));
	return res;
}
int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
	build(1, 1, n);
	while (m--) {
		int op;
		scanf("%d", &op);
		if (op < 3) {
			int x, y;
			LL k;
			scanf("%d%d%lld", &x, &y, &k);
			update(1, x, y, k, op);
		} else {
			int x, y;
			scanf("%d%d", &x, &y);
			printf("%lld\n", query(1, x, y));
		}
	}
	return 0;
}

P3373【模板】线段树 2

参考代码 
#include <cstdio>
#define LC (cur*2)
#define RC (cur*2+1)
typedef long long LL;
const int MAXN = 500005;
struct Node {
	int l, r;
	LL value, add, mul;
};
LL a[MAXN], m;
Node tree[MAXN*4];
void pushup(int cur) {
	tree[cur].value = (tree[LC].value + tree[RC].value) % m;
}
void build(int cur, int l, int r) {
	tree[cur].l = l;
	tree[cur].r = r;
	tree[cur].mul = 1;
	if (l == r) {
		tree[cur].value = a[l] % m;
		return;
	}
	int mid = (l + r) / 2;
	build(LC, l, mid);
	build(RC, mid+1, r);
	pushup(cur);
}
void work(int cur, LL x, int op) { //对cur这个节点进行具体的更新操作
	if (op == 1) {
		tree[cur].value *= x; tree[cur].value %= m;
		tree[cur].mul *= x; tree[cur].mul %= m;
		tree[cur].add *= x; tree[cur].add %= m;
	} else {
		tree[cur].value += x * (tree[cur].r-tree[cur].l+1) % m;
		tree[cur].value %= m;
		tree[cur].add += x; tree[cur].add %= m;
	}
}
void pushdown(int cur) {
	if (tree[cur].mul != 1) {
		work(LC, tree[cur].mul, 1); work(RC, tree[cur].mul, 1);
		tree[cur].mul = 1;
	}
	if (tree[cur].add != 0) {
		work(LC, tree[cur].add, 2); work(RC, tree[cur].add, 2);
		tree[cur].add = 0;
	}
}
void update(int cur, int l, int r, LL x, int op) {
	if (tree[cur].l >= l && tree[cur].r <= r) {
		work(cur, x, op);
		return;
	}
	pushdown(cur);
	int mid = (tree[cur].l + tree[cur].r) / 2;
	if (mid >= l) update(LC, l, r, x, op);
	if (mid < r) update(RC, l, r, x, op);
	pushup(cur);
}
LL query(int cur, int l, int r) { // 区间查询
	if (tree[cur].l >= l && tree[cur].r <= r) { // 完全包含
		return tree[cur].value;
	}
	pushdown(cur);
	int mid = (tree[cur].l + tree[cur].r) / 2;
	LL res = 0;
	if (mid >= l) {
		res += query(LC, l, r); res %= m;
	}
	if (mid < r) {
		res += query(RC, l, r); res %= m;
	}
	return res;
}
int main() {
	int n, q;
	scanf("%d%d%lld", &n, &q, &m);
	for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
	build(1, 1, n);
	while (q--) {
		int op;
		scanf("%d", &op);
		if (op < 3) {
			int x, y;
			LL k;
			scanf("%d%d%lld", &x, &y, &k);
			update(1, x, y, k, op);
		} else {
			int x, y;
			scanf("%d%d", &x, &y);
			printf("%lld\n", query(1, x, y));
		}
	}
	return 0;
}