线段树学习笔记(基础&进阶)(一) | P3372 【模板】线段树 1 题解

什么是线段树

线段树是一棵二叉树,每个结点存储需维护的信息,一般用于处理区间最值、区间和等问题。

线段树的用处

对编号连续的一些点进行修改或者统计操作,修改和统计的复杂度都是 O(log n)。

基础线段树(+ 懒标记)

为什么不写没有懒标记的版本?
因为我太菜的不会写 因为有懒标记的版本更实用啦。

这是一道线段树区间修改,区间查询的模板题,维护的是区间和。

1. 建树

void build(int rt, int L, int R) {
	l[rt] = L, r[rt] = R;
	if (L == R) {
		sum[rt] = a[L];
		return ;
	}
	int mid = L + R >> 1;
	build(rt << 1, L, mid), build(rt << 1 | 1, mid + 1, R);
	update(rt);
}

作为一棵最最普通的线段树,它有一个性质,对于每个结点 x,它的左儿子的编号是 x * 2 (即代码中的 x << 1),右儿子的编号是 x * 2 + 1 (即代码中的 x << 1 | 1)。
代码中的 l 和 r 数组用于记录编号为 rt 的点所管辖的区间的左右端点。
update 是什么?它是用子节点的数据更新自身的数据,以保证正确性。


  • update 的具体实现
void update(int rt) {
	sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}

它在后续的操作中也会用到


2. 修改

void change(int rt, int L, int R, int x) {
	if (L <= l[rt] && r[rt] <= R) {
		sum[rt] += (r[rt] - l[rt] + 1) * x;
		lazy[rt] += x;
		return ;
	}
	pushdown(rt);
	if (L <= r[rt << 1]) change(rt << 1, L, R, x);
	if (l[rt << 1 | 1] <= R) change(rt << 1 | 1, L, R, x);
	update(rt);
}

其中传入的参数 L 和 R 表示需修改的区间的左右端点,x 表示这个区间上要加的数。
if (L <= l[rt] && r[rt] <= R) 意为当该点管辖的区间被需修改的区间全覆盖时,直接修改这个点上记录的区间和,并打上懒标记,不继续下传,以保证效率。(懒标记就是一种记录修改操作的 tag,用于节省时间。)
pushdown 操作意为该点管辖的区间不完全覆盖于需修改的区间时,下传懒标记。(为什么现在才下传?因为懒标记就是这么用的 因为后面的更改会用到该点的子节点的数据,如果懒标记不下传,后面的修改操作就会出现问题。)
下面的两个 if 是什么?
if (L <= r[rt << 1]) 表示左儿子的区间中有部分(或全部)包含于询问区间,需统计。(如果还是没看出来就翻回去看看定义和性质吖)
那么是不是就知道 if (l[rt << 1 | 1] <= R) 是什么了?
对,它表示的是右儿子的区间中有部分(或全部)包含于询问区间,需统计。
传的参数为什么是这样不用我说了吧?


  • pushdown 的具体实现
void pushdown(int rt) {
	if (!lazy[rt]) return ;
	sum[rt << 1] += (r[rt << 1] - l[rt << 1] + 1) * lazy[rt];
	sum[rt << 1 | 1] += (r[rt << 1 | 1] - l[rt << 1 | 1] + 1) * lazy[rt];
	lazy[rt << 1] += lazy[rt];
	lazy[rt << 1 | 1] += lazy[rt];
	lazy[rt] = 0;
	update(rt);
}

在下传懒标记时给子节点的区间和加上 懒标记的值 × 子节点的区间大小。(给该子节点的管辖区间的所有数都加上懒标记的值,那么该区间的区间和就会加上 懒标记的值 × 区间长度。)
同时,给子节点的懒标记都加上自己的懒标记的值。(没错我还是给你吊在那里,不给你传到底
记得清空自己的懒标记值更新自己的区间和


3. 查询

ll query(int rt, int L, int R) {
	if (L <= l[rt] && r[rt] <= R) return sum[rt];
	pushdown(rt);
	ll res = 0;
	if (L <= r[rt << 1]) res += query(rt << 1, L, R);
	if (l[rt << 1 | 1] <= R) res += query(rt << 1 | 1, L, R);
	return res;
}

查询其实和修改很像。(不妨肉眼观查一下)
在该结点所管辖的区间完全被覆盖时,直接返回区间和。
若未被完全覆盖,则下传懒标记,分左右儿子考虑,统计总答案并返回值。
是不是 so easy?


于是你愉快地切了这题。

完整代码,点击查看
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
inline ll read() {
	ll s = 0, w = 1;
	char c = getchar();
	while (c < '0' || c > '9') {if (c == '-') w = -1; c = getchar();}
	while (c >= '0' && c <= '9') s = (s << 3) + (s << 1) + (c ^ 48), c = getchar();
	return s * w;
}
const int N = 100010;
int n, m, a[N];
struct SegmentTree {
	ll sum[N << 2], lazy[N << 2];
	int l[N << 2], r[N << 2];
	void update(int rt) {
		sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
	}
	void pushdown(int rt) {
		if (!lazy[rt]) return ;
		sum[rt << 1] += (r[rt << 1] - l[rt << 1] + 1) * lazy[rt], lazy[rt << 1] += lazy[rt];
		sum[rt << 1 | 1] += (r[rt << 1 | 1] - l[rt << 1 | 1] + 1) * lazy[rt], lazy[rt << 1 | 1] += lazy[rt];
		lazy[rt] = 0;
		update(rt);
	}
	void build(int rt, int L, int R) {
		l[rt] = L, r[rt] = R;
		if (L == R) {
			sum[rt] = a[L];
			return ;
		}
		int mid = L + R >> 1;
		build(rt << 1, L, mid), build(rt << 1 | 1, mid + 1, R);
		update(rt);
	}
	void change(int rt, int L, int R, int x) {
		if (L <= l[rt] && r[rt] <= R) {
			sum[rt] += (r[rt] - l[rt] + 1) * x;
			lazy[rt] += x;
			return ;
		}
		pushdown(rt);
		if (L <= r[rt << 1]) change(rt << 1, L, R, x);
		if (l[rt << 1 | 1] <= R) change(rt << 1 | 1, L, R, x);
		update(rt);
	}
	ll query(int rt, int L, int R) {
		if (L <= l[rt] && r[rt] <= R) return sum[rt];
		pushdown(rt);
		ll res = 0;
		if (L <= r[rt << 1]) res += query(rt << 1, L, R);
		if (l[rt << 1 | 1] <= R) res += query(rt << 1 | 1, L, R);
		return res;
	}
} tree;
int main() {
	n = read(), m = read();
	for (int i = 1; i <= n; i++) a[i] = read();
	tree.build(1, 1, n);
	while (m--) {
		int op = read();
		if (op == 1) {
			int l = read(), r = read(), x = read();
			tree.change(1, l, r, x); 
		}
		if (op == 2) {
			int l = read(), r = read();
			printf("%lld\n", tree.query(1, l, r));
		}
	}
	return 0;
}

现在,你学会了区间修改区间查询的线段树,不如想想 单点修改区间查询 和 区间修改单点查询 怎么写?(为什么没有单点修改单点查询线段树呢(小声


点击继续研究线段树 – 线段树学习笔记(基础&进阶)(二)(码字中…)