线段树-zkw、伪动态开点、永久化标记模板

线段树空间##

下面“空间”是指实际维护的区间长度所占空间

• 指针版动态开点由于 C++ 里 struct 的“对齐”操作，会额外占用内存。所以内存非常紧张的时候还是必须牺牲一点效率写数组版动态开点。
• zkw 线段树由于必须是一颗有 (2^k) 个叶节点的满二叉树，所以需要 4 倍空间。
• 普通线段树需要 2 倍空间。

指针版伪动态开点 + 永久化标记##

区间 max NKOJ2297 数列操作
实际上是静态数组，动态开点只是指用到某个节点才去 p = &[++STCnt] 。

#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long ll;

const ll INF = 1e18;
const int _N = 110000;

int N, M, STCnt;

struct node {
	ll mx, lazy;
	node *l, *r;
} ST[_N * 2], *Rt;

void build(node *&p, int l, int r)
{
	if (p == NULL) p = &ST[++STCnt];
	if (l == r) {
		scanf("%lld", &p->mx);
		return;
	}
	int mid = (l + r) >> 1;
	build(p->l, l, mid), build(p->r, mid + 1, r);
	p->mx = max(p->l->mx, p->r->mx);
	return;
}

void add(node *&p, int l, int r, int s, int t, ll v)
{
	if (s <= l && r <= t) {
		p->mx += v, p->lazy += v;
		return;
	}
	int mid = (l + r) >> 1;
	if (s <= mid) add(p->l, l, mid, s, t, v);
	if (t > mid) add(p->r, mid + 1, r, s, t, v);
	p->mx = max(p->l->mx, p->r->mx) + p->lazy;
	return;
}

void query(node *&p, int l, int r, int s, int t, ll &v)
{
	if (s <= l && r <= t) {
		v = p->mx;
		return;
	}
	int mid = (l + r) >> 1;
	ll a = -INF, b = -INF;
	if (s <= mid) query(p->l, l, mid, s, t, a);
	if (t > mid) query(p->r, mid + 1, r, s, t, b);
	v = max(a, b) + p->lazy;
	return;
}

int main()
{
	scanf("%d", &N);
	build(Rt, 1, N);
	scanf("%d", &M);
	while (M--) {
		char ins[5];
		int x, y;
		ll z;
		scanf("%s", ins);
		if (ins[1] == 'D') {
			scanf("%d%d%lld", &x, &y, &z);
			add(Rt, 1, N, x, y, z);
		} else {
			scanf("%d%d", &x, &y);
			query(Rt, 1, N, x, y, z);
			printf("%lld
", z);
		}
	}
	return 0;
}

zkw 线段树##

zkw 线段树的区间修改暂时还不会，有点惨呀 OrzOrzOrz 。学是不可能学的，就只有写指针线段树再拼命卡卡常数才能维持得了生活这样子……

NKOJ2742 【线段树】区间极大值1

#include <stdio.h>
#include <algorithm>

using namespace std;

const int INF = 1e9;

int N, M, zkw;
int A[420000];

int main()
{
	scanf("%d%d", &N, &M);
	
	for (zkw = 1; zkw <= N; zkw <<= 1);
	for (int i = 0; i <= N + 1; ++i)
		A[zkw + i] = -INF;
	for (int i = 1; i <= N; ++i)
		scanf("%d", &A[zkw + i]);
	for (int i = zkw - 1; i >= 1; --i)
		A[i] = max(A[i << 1], A[i << 1 | 1]);
	while (M--) {
		int x, y, ans = -INF;
		scanf("%d%d", &x, &y);
		int a = zkw + x - 1, b = zkw + y + 1;
		while (a ^ 1 ^ b) {
			if (a & 1 ^ 1) ans = max(ans, A[a ^ 1]);
			if (b & 1) ans = max(ans, A[b ^ 1]);
			a >>= 1, b >>= 1;
		}
		printf("%d
", ans);
	}
	return 0;
}

数组版伪动态开点##

写 struct 是因为这份代码是当时写完指针版之后改的，太懒，就是不想把 mx 改成数组。

NKOJ2742 【线段树】区间极大值1

#include <stdio.h>
#include <algorithm>

using namespace std;

const int INF = 1e9;

int N, M, Cnt, Rt, L[420000], R[420000];

struct node {
	int mx;
	node()
	{
		mx = -INF;
		return;
	}
} A[420000];

void modify(int &p, int l, int r, int k, int d)
{
	if (!p) p = ++Cnt;
	if (l == r) { A[p].mx = d; return; }
	int mid = (l + r) >> 1;
	if (k <= mid) modify(L[p], l, mid, k, d), A[p].mx = max(A[p].mx, A[L[p]].mx);
	else modify(R[p], mid + 1, r, k, d), A[p].mx = max(A[p].mx, A[R[p]].mx);
	return;
}

int query(int &p, int l, int r, int s, int t)
{
	if (!p) p = ++Cnt;
	if (s <= l && r <= t) return A[p].mx;
	int mid = (l + r) >> 1, tmp = -INF;
	if (s <= mid && t >= l) tmp = max(tmp, query(L[p], l, mid, s, t));
	if (s <= r && t > mid) tmp = max(tmp, query(R[p], mid + 1, r, s, t));
	return tmp;
}

int main()
{
	scanf("%d%d", &N, &M);
	
	for (int t, i = 1; i <= N; ++i) {
		scanf("%d", &t);
		modify(Rt, 1, N, i, t);
	}
	while (M--) {
		int x, y;
		scanf("%d%d", &x, &y);
		printf("%d
", query(Rt, 1, N, x, y));
	}
	return 0;
}