[数据结构与算法] 《算法竞赛进阶指南》0x40线段树

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 《算法竞赛进阶指南》0x40线段树 -> 正文阅读

[数据结构与算法]《算法竞赛进阶指南》0x40线段树

来，骗（建树、查询）

#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;
}