《算法竞赛进阶指南》0x40线段树

2021-08-27 22:13:27

来，骗（建树、查询）

#include <iostream>
#include <cstdio>
using namespace std;

const int N = 1e6 + 10;
int n, q, a[N];

struct SegmentTree {
	int l, r, val;
}tr[4 * N];

//当前建立的是u号结点，范围是[l,r] 
void build(int u, int l, int r) {
	tr[u] = {l, r};
	
	if (l == r) {
		//叶子结点的值，直接取a数组的值 
		tr[u].val = a[l];
		return;
	}
	
	int mid = l + r >> 1;
	build(u << 1, l, mid);
	build(u << 1 | 1, mid + 1, r);
	//非叶子结点的值，由它的两个孩子决定 
	tr[u].val = tr[u << 1].val + tr[u << 1 | 1].val;
}

//当前查询的是u号结点，要查询的区间范围是[A,B] 
int query(int u, int A, int B) {
	if (A <= tr[u].l && tr[u].r <= B) {
		return tr[u].val; 
	} 
	 
	int mid = tr[u].l + tr[u].r >> 1, ans = 0;
	if (A <= mid) {
		ans += query(u << 1, A, B);
	}
	if (mid < B)  {
		ans += query(u << 1 | 1, A, B);
	}
	return ans;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);
	build(1, 1, n);							//建立线段树 
	
	scanf("%d", &q);
	while (q --) {
		int A, B;
		scanf("%d%d", &A, &B);
		printf("%d\n", query(1, A, B));		//查询区间和 
	}

	return 0;
}

数列区间最大值（建树、查询）

#include <iostream>
#include <cstdio>
using namespace std;

const int N = 1e6 + 10;
int n, q, a[N];

struct SegmentTree {
	int l, r, val;
}tr[4 * N];

//当前建立的是u号结点，范围是[l,r]
void build(int u, int l, int r) {
	tr[u] = {l, r};
	
	if (l == r) {
		//叶子结点的值，直接取a数组的值 
		tr[u].val = a[l];
		return;
	}
	
	int mid = l + r >> 1;
	build(u << 1, l, mid);
	build(u << 1 | 1, mid + 1, r);
	//非叶子结点的值，由它的两个孩子决定 
	tr[u].val = max(tr[u << 1].val, tr[u << 1 | 1].val);
}

//当前查询的是u号结点，要查询的区间范围是[A,B]
int query(int u, int A, int B) {
	if (A <= tr[u].l && tr[u].r <= B) return tr[u].val;
	
	int mid = tr[u].l + tr[u].r >> 1, ans = -1e9;
	if (A <= mid) ans = max(ans, query(u << 1, A, B));
	if (mid < B)  ans = max(ans, query(u << 1 | 1, A, B));
	return ans;
}

int main() {
	scanf("%d%d", &n, &q);
	for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);
	build(1, 1, n);
	
	while (q --) {
		int A, B;
		scanf("%d%d", &A, &B);
		printf("%d\n", query(1, A, B));
	}

	return 0;
}

数列操作 （单点增加 、查询区间和）

#include <iostream>
#include <cstdio>
using namespace std;

const int N = 1e5 + 10;
int n, q, a[N];

struct SegmentTree {
	int l, r, val;
}tr[4 * N];

//当前建立的是u号结点，范围是[l,r]
void build(int u, int l, int r) {
	tr[u] = {l, r};
	
	if (l == r) {
		//叶子结点的值，直接取a数组的值 
		tr[u].val = a[l];
		return;
	}
	
	int mid = l + r >> 1;
	build(u << 1, l, mid);
	build(u << 1 | 1, mid + 1, r);
	//非叶子结点的值，由它的两个孩子决定
	tr[u].val = tr[u << 1].val + tr[u << 1 | 1].val;
}

//当前查询的是u号结点; 将a[pos]改为x
void modify(int u, int pos, int x) { 
	if (tr[u].l == tr[u].r) {
		//查询到叶子结点，将其修改 
		tr[u].val += x;
		return;
	}
	
	int mid = tr[u].l + tr[u].r >> 1;
	if (pos <= mid) modify(u << 1, pos, x);
	else modify(u << 1 | 1, pos, x);
	//非叶子结点的值，由它的两个孩子决定
	tr[u].val = tr[u << 1].val + tr[u << 1 | 1].val;
}

//当前查询的是u号结点; 要查询的区间范围是[A,B] 
int query(int u, int A, int B) {
	if (A <= tr[u].l && tr[u].r <= B) return tr[u].val; 
	 
	int mid = tr[u].l + tr[u].r >> 1, ans = 0;
	if (A <= mid) ans += query(u << 1, A, B);
	if (mid < B)  ans += query(u << 1 | 1, A, B);
	return ans;
}

int main() {
	scanf("%d%d", &n, &q);
	for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);
	build(1, 1, n);
	
	while (q --) {
		int k, s, t;
		scanf("%d%d%d", &k, &s, &t);
		if (k == 0) printf("%d\n", query(1, s, t));
		else modify(1, s, t);
	}

	return 0;
}

最大数（单点修改 、查询区间最大数）

#include <iostream>
#include <cstdio>
using namespace std;

const int M = 2e5 + 10;
int n, m, p;
struct SegementTree {
	int l, r, val;
}tr[4 * M];

void build(int u, int l, int r) {
	tr[u] = {l, r};
	
	if (l == r) return;
	
	int mid = l + r >> 1;
	build(u << 1, l, mid);
	build(u << 1 | 1, mid + 1, r);
}

void modify(int u, int pos, int x) {
	if (tr[u].l == tr[u].r) {
		tr[u].val = x;
		return;
	}
	
	int mid = tr[u].l + tr[u].r >> 1;
	if (pos <= mid) modify(u << 1, pos, x);
	else modify(u << 1 | 1, pos, x);
	tr[u].val = max(tr[u << 1].val, tr[u << 1 | 1].val);
}

int query(int u, int A, int B) {
	if (A <= tr[u].l && tr[u].r <= B) return tr[u].val; 
	
	int mid = tr[u].l + tr[u].r >> 1, ans = 0;
	if (A <= mid) ans = max(ans, query(u << 1, A, B));
	if (mid < B)  ans = max(ans, query(u << 1 | 1, A, B));
	return ans;
}

int main() {
	scanf("%d%d", &m, &p);
	build(1, 1, m);

	char op[2];
	int num, res = 0;
	while (m --) {
		scanf("%s%d", op, &num);
		if (op[0] == 'Q') res = query(1, n - num + 1, n), printf("%d\n", res);
		else modify(1, ++ n, ((long long)num + res) % p);
	}

	return 0; 
}

花神游历各国（特殊的单点修改 、查询区间和）

#include <iostream>
#include <cstdio>
#include <cmath>
#define LL long long
using namespace std;

const int N = 1e5 + 10;
int n, m, a[N];
struct SegmentTree {
	int l, r, maxx;
	LL val;
}tr[4 * N];

void build(int u, int l, int r) {
	tr[u] = {l, r};
	
	if (l == r) {
		tr[u].val = tr[u].maxx = a[l];
		return;
	}
	
	int mid = l + r >> 1;
	build(u << 1, l, mid);
	build(u << 1 | 1, mid + 1, r);
	tr[u].val = tr[u << 1].val + tr[u << 1 | 1].val;
	tr[u].maxx = max(tr[u << 1].maxx, tr[u << 1 | 1].maxx);
}

void modify(int u, int A, int B) {
	if (tr[u].maxx <= 1) return;
	if (tr[u].l == tr[u].r) {
		tr[u].val = tr[u].maxx = sqrt(tr[u].val);		
		return;
	}	
	
	int mid = tr[u].l + tr[u].r >> 1;
	if (A <= mid) modify(u << 1, A, B);
	if (mid < B)  modify(u << 1 | 1, A, B);
	tr[u].val = tr[u << 1].val + tr[u << 1 | 1].val;
	tr[u].maxx = max(tr[u << 1].maxx, tr[u << 1 | 1].maxx);
}

LL query(int u, int A, int B) {
	if (A <= tr[u].l && tr[u].r <= B) return tr[u].val;
	
	int mid = tr[u].l + tr[u].r >> 1;
	LL res = 0;
	if (A <= mid) res += query(u << 1, A, B);
	if (mid < B)  res += query(u << 1 | 1, A, B);
	return res;	
}

int main() { 
	scanf("%d", &n);
	for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);
	build(1, 1, n);
	
	scanf("%d", &m);
	while (m --) {
		int x, A, B;
		LL res;
		scanf("%d%d%d", &x, &A, &B);
		if (x == 2) modify(1, A, B);
		else res = query(1, A, B), printf("%lld\n", res);
	}

	return 0;
}

A Simple Problem with Integers （区间修改、区间查询）

#include <iostream>
#include <cstdio>
#define LL long long
using namespace std;

const int N = 1e6 + 10;
int n, q, a[N], tag[N];

struct SegmentTree {
	int l, r;
	LL val, tag;
}tr[4 * N];

void build(int u, int l, int r) {
	if (l == r) {
		tr[u] = {l, r, a[l], 0};
		return;
	}
	
	int mid = l + r >> 1;
	build(u << 1, l, mid);
	build(u << 1 | 1, mid + 1, r);
	tr[u] = {l, r, tr[u << 1].val + tr[u << 1 | 1].val, 0};
}

void update(int u, int x) {
	tr[u].tag += x;
	tr[u].val += (LL)(tr[u].r - tr[u].l + 1) * x;
}

void modify(int u, int A, int B, int x) {
	if (A <= tr[u].l && tr[u].r <= B) {
		update(u, x);
		return;
	}
	
	//在往下递归之前，检查一下是否需要下传懒标记
	if (tr[u].tag) {
		update(u << 1, tr[u].tag);
		update(u << 1 | 1, tr[u].tag);
		tr[u].tag = 0;
	}
	
	int mid = tr[u].l + tr[u].r >> 1;
	if (A <= mid) modify(u << 1, A, B, x);
	if (mid < B)  modify(u << 1 | 1, A, B, x);
	
	tr[u].val = tr[u << 1].val + tr[u << 1 | 1].val;
}

LL query(int u, int A, int B) {
	if (A <= tr[u].l && tr[u].r <= B) return tr[u].val;

	if (tr[u].tag) {
		update(u << 1, tr[u].tag);
		update(u << 1 | 1, tr[u].tag);
		tr[u].tag = 0;		
	}
	
	int mid = tr[u].l + tr[u].r >> 1;
	LL res = 0;
	if (A <= mid) res += query(u << 1, A, B);
	if (mid < B)  res += query(u << 1 | 1, A, B);
	
	return res;
}

int main() {
	scanf("%d%d", &n, &q);
	for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);
	build(1, 1, n);

	while (q --) {
		int op, A, B, x;
		scanf("%d", &op);
		if (op == 1) {
			scanf("%d%d%d", &A, &B, &x);
			modify(1, A, B, x);
		}
		else {
			scanf("%d%d", &A, &B);
			LL res = query(1, A, B);
			printf("%lld\n", res);
		}
	}

	return 0;
}

维护序列（区间修改、区间查询）

#include <iostream>
#include <cstdio>
#define LL long long
using namespace std;

const int N = 1e5 + 10;
int n, m;
LL P, a[N];
struct SegmentTree{
	int l, r;
	LL val, t1, t2;	//t1: 乘，t2：加 
}tr[N * 4];

void build(int u, int l, int r) {
	if (l == r) {
		tr[u] = {l, r, a[l], 1, 0};
		return;
	}
	
	int mid = l + r >> 1;
	build(u << 1, l, mid);
	build(u << 1 | 1, mid + 1, r);
	
	LL t = (tr[u << 1].val + tr[u << 1 | 1].val) % P;
	tr[u] = {l, r, t, 1, 0};
}

//(data * t1 + t2) * x1 + x2 = data * (t1 * x1) + (t2 * x1 + x2)
void update(int u, int x1, int x2) {
	tr[u].t1 = tr[u].t1 * x1 % P;
	tr[u].t2 = (tr[u].t2 * x1 + x2) % P;
	tr[u].val = (tr[u].val * x1 + (tr[u].r - tr[u].l + 1) * (LL)x2) % P;
}

void modify(int u, int A, int B, int x1, int x2) {
	if (A <= tr[u].l && tr[u].r <= B) {
		update(u, x1, x2);
		return;
	}
	
	//在往下递归之前，检查一下是否需要下传懒标记 
	//如果不判断，也不会影响结果 
	update(u << 1, tr[u].t1, tr[u].t2);
	update(u << 1 | 1, tr[u].t1, tr[u].t2);
	tr[u].t1 = 1;
	tr[u].t2 = 0;
	
	int mid = tr[u].l + tr[u].r >> 1;
	if (A <= mid) modify(u << 1, A, B, x1, x2);
	if (mid < B)  modify(u << 1 | 1, A, B, x1, x2);
	tr[u].val = (tr[u << 1].val + tr[u << 1 | 1].val) % P;
}

LL query(int u, int A, int B) {
	if (A <= tr[u].l && tr[u].r <= B) return tr[u].val;

	update(u << 1, tr[u].t1, tr[u].t2);
	update(u << 1 | 1, tr[u].t1, tr[u].t2);
	tr[u].t1 = 1;
	tr[u].t2 = 0;
	
	int mid = tr[u].l + tr[u].r >> 1;
	LL res = 0;
	if (A <= mid) res += query(u << 1, A, B);
	if (mid < B)  res += query(u << 1 | 1, A, B);
	return res % P;
}

int main() {
	scanf("%d%d", &n, &P);
	for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);
	build(1, 1, n);
	
	scanf("%d", &m);
	while (m --) {
		int op, A, B, x;
		scanf("%d", &op);
		if (op == 1) scanf("%d%d%d", &A, &B, &x), modify(1, A, B, x, 0);
		else if (op == 2) scanf("%d%d%d", &A, &B, &x), modify(1, A, B, 1, x);
		else scanf("%d%d", &A, &B), printf("%lld\n", query(1, A, B));
	}

	return 0;
}
上一篇：P1908 逆序对


下一篇：常州开发基于QT的安卓手机蓝牙APP软件公司