线段树专题-六虎

前言

本文章主要由浅入深的介绍线段树的各种操作，由于线段树特别重要。支持几乎所有的区间操作，所以笔者也会分享一些理解，同时存在难以避免的错误，还请读者指出！

线段树的定义

线段树的定义：使用树形结构通过维护操作子节点的信息，来统计区间信息的树形结构。

为什么需要线段树

支持在时间复杂度 $n (l o g n)$ 内完成单点（区间）修改、单点（区间）查询、区间翻转、区间最值、区间众数、区间数点等一系列区间操作，具有可拓展、灵活操作等特点。

注 : 线段树支持的操作过多，本文不会提及所有操作！

如何实现基本的线段树

建树

建树非常简单！就是划分线段

我们将划分区间的操作称之为裂开区间

将其画成树形结构更加的形象

首先通过上图我们可以发现，其实线段树是一种堆式存储的形式，我们设父节点的编号是 $u$ 的话，那么我们的左孩子是 $u << 1$ , 右孩子是 $u << 1∣1$ (~~位运算不懂的，请查bing~~)。
其次通过上图我们发现区间只有一个数的结点，那就是叶子结点，这些叶子结点只存储值，当然我们也可以看成它是存储的区间信息(~~个人觉得这样更好理解~~)。

我们知道了存储方式，以及每个结点存储的数据，那么我们就可以建树了

递归建树

void build(int u , int l , int r){
	tr[u] = {l , r , 0 , 0 };
	if (l == r) return ;
	int mid = (l   r) >> 1;           // 区间裂开
	build(ls , l , mid);
	build(rs , mid   1 , r);
}

区间修改、查询

这里给出两种区间修改的方式，请按照情况选择。

差分，将区间操作转化为单点操作。
懒标记 , 优化未进行的操作。

差分

先介绍第一种方法，差分，我们可以对原序列进行差分。

修改操作步骤
- 对原序列进行差分
- 对于区间 $[l, r]$ 修改只需要对 $l$ 点加上 C ，再对 $r 1$ 点减去C即可（ $r 1 \leq n$ 注意边界）
查询
- 单点查询直接求 $[1, i]$ 的前缀和 , 这个操作的是时间复杂度是 $O (l o g n)$
- 区间查询那么就需要一点技巧这里给出步骤，并附上证明
  - 步骤
    1. 考虑维护两棵线段树，一棵线段树维护序列差分区间和 $∑i=lrdisum_{i=l}^r d_i$ , 另外一棵线段树维护 $∑i=lrdi∗isum_{i = l}^r d_i* i$
    2. 求区间和只需要对使用公式 $1)sum_{i = 1}^{r} d_i – lsum_{i = 1}^{l-1} d_i – (sum_{i=1}^r d_i * i – sum_{i=1}^{l-1} d_i* i)$
  - 证明
    1. 区间和我们可以表示成这样 (~~笔者是类比树状数组求区间和的方法，可能存在错误~~)
    $1)∑i=1l−1di)−(∑i=1rdi∗i−∑i=1l−1di∗i)sum_{i=l}^rsum_{j = 1}^i d_j = ( (r 1)sum_{i = 1}^{r} d_i – (l – 1 1)sum_{i = 1}^{l-1} d_i ) – (sum_{i=1}^r d_i * i – sum_{i=1}^{l-1} d_i* i)$
    核心思想：求前缀和再做差
第一种方法代码不给出，主要就是介绍思想 , 代码可以自行网络查找。如果遇到这种情况，可以借助另外一种数据结构更为方便。

懒标记

区间修改、查询

先瞅瞅懒标记tag

先好好说说

懒标记
- 是什么？ 用于记录历史修改操作的区间标记，大白话就是把之前没有进行的操作进行一下。
- 有什么用？ 用于记录历史标记，对区间进行修改时减少许多不必要的操作。
  
  例如：我一直对区间 $l_1 , r_1]$ 操作，但是我只询问 $l_2 , r_2]$ , 明显 $l_1 , r_1]$ 那个区间不需要修改
- 什么时候使用它？ 在需要对这个区间操作的时候，如果存在懒标记，那么将子节点的信息算好，懒标记再下传即可。
- 核心要点：
  - 懒标记是给子节点用的！
  - 下传懒标记操作，实际是先通过操作父结点懒标记时算好子结点的信息，再将父结点懒标记传给子结点（这里称维护结点信息）。
  - 这个操作往往发生在查询和修改的时候（一般会另外写一个pushdown函数）

上文指到的是加法标记，其实线段树可以维护非常多的标记。本人目前还最多接触过同时维护两种运算标记。凡是父节点信息可以通过子结点拼凑的，都是使用线段树维护。这是一点对线段树的理解！

理解了懒标记，就好做区间修改和区间查询了。

区间修改

其实看到图就是怎么修改了。

先给定一个区间 [1 , 4] , 操作方式就是懒标记停在[1 , 3] , 因为我们不要用到这个区间。 [4 , 4] 这个区间操作我们其实也可以理解成停在 [4 , 4].
注意在第二次操作的时候 , 我们对 [2 , 5] 进行操作。这时候，我们需要操作这个区间的元素 [1 , 3] , 那么在操作这个区间时，也就是触的时候，我们就要将懒标记下传，维护信息，然后再对对应区间进行操作（~~因为笔者不会如何制作动图，不然就非常的直观 , 水平菜了~~）。

区间查询

其实区间查询就是区间修改的阉割版，不是吗？我只需要一路将需要处理的懒标记处理了，然后发挥对应区间的信息即可。

给定一张图，来看看如何进行区间查询。

我们发现，我们将 [4 , 5] 标记维护完了，父节点和子节点的信息。怎么维护的呢？ 一般步骤：

通过父节点懒标记维护子节点信息
将父节点的懒标记下传给子节点
将父节点的懒标记清除
请记住一点，父节点的信息一定是维护正确的，懒标记是用来给子节点用的。父节点拥有的懒标记，一定给父节点用，这一点非常重要！

注: 懒标记本质就是未操作完的动作，被保存了下来

参考代码

 #include <iostream>
 #include <cstring>
 #include <algorithm>
 #define LL long long
 #define ls u << 1
 #define rs u << 1 | 1
 const int N = 100010;
 int n , m; 	
 LL a[N];
 struct Node{
     int l , r;
     LL sum , tag;
 }tr[4 * N];
 void pushup(Node &u , const Node &L , const Node &R){
     u.sum = L.sum   R.sum;
 }
 void puhsdown(int u){
 if (tr[u].tag){
         tr[ls].sum  = (tr[ls].r - tr[ls].l   1) * tr[u].tag;
         tr[rs].sum  = (tr[rs].r - tr[rs].l   1) * tr[u].tag;
         tr[ls].tag  = tr[u].tag;
         tr[rs].tag  = tr[u].tag;
         tr[u].tag = 0;
   }
 }
 void modify(int u , int l , int  r , LL c){
     if (l <= tr[u].l && tr[u].r <= r){						// 修改区间信息
             tr[u].sum  = (tr[u].r - tr[u].l   1) * c;			// 维护结点信息
             tr[u].tag  = c;										// 打上结点标记
             return ;
     }
     puhsdown(u);
     int mid = (tr[u].r   tr[u].l) >> 1;
     if (r <= mid) modify(ls , l , r , c);
     else if (l > mid) modify(rs , l , r , c);
     else{														// 区间左右孩子都有 , 裂开
             modify(ls , l , mid , c);
             modify(rs , mid   1 , r , c);
     }
     pushup(tr[u] , tr[ls] , tr[rs]);
 }
 LL query(int u , int l , int r){
     if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
     puhsdown(u);               // 懒标记下传
     int mid = (tr[u].l   tr[u].r) >> 1;
     LL sum = 0;
     if (r <= mid) sum = query(ls , l , r);
     else if (l > mid) sum = query(rs , l , r);
     else {
             sum  = query(ls , l , mid);
             sum  = query(rs , mid   1 , r);
     }
     pushup(tr[u] , tr[ls] , tr[rs]);
     return sum;
 }

学完可以去刷【模板】线段树 1这道题。

线段树的应用

区间最值

这个维护就比较的简单，因为区间最值是通过子节点拼凑出来的信息，也就是说，[3 , 5] 的最大值是 [3 , 4 , 5] 三个结点的信息拼凑出来的，这样只需要向上 pushup 即可。

就像这样，通过子节点不断向上维护即可。

学完可以去刷这道题扶苏的问题 , 这题有点毒瘤。

区间最大子段和

区间最大子段和，可以参照这道题小白逛公园。即，快速求出给定区间 [l , r] 的最大子段和。

对于这题也是一个区间信息拼凑的问题。

求出最大子段和的方法 :

$ma x = ma x (t r [l s] . ma x, t r [rs] . ma x, t r [l s] . ma x t r [rs] . ma x)$

为什么是这样的呢？我们来分类讨论可能的情况
1. 左边最大子段和是整个区间的最大子段和

2. 右边最大子段和是整个区间的最大子段和

3. 左边区间和右边区间拼接起来，组成区间最大子段和

因为我们需要考虑三种情况，所以我们的维护方式这样的。且除此之外，没有其他的情况了。

但是问题来了，如何维护区间最大左子段和、区间最大右子段和？

对于区间最大左子段和我们可以通过分类讨论，来确定

直接将左孩子的最大左子段和上传

2. 将左孩子的整个区间和sum 和 右孩子的最大左子段和拼凑上来

对这两种情况，我们肯定要贪心的取求出区间最大左子段和方法:

$t r [u] . l ma x = ma x (t r [l s] . s u m t r [rs] . l ma x, t r [l s] . l ma x)$

维护区间最大右子段和方法，就是类似的啦。直接给出方法:

$t r [u] . r ma x = ma x (t r [rs] . s u m t r [l s] . r ma x, t r [rs] . r ma x)$

如何维护区间和，那就非常简单啦。前面已经讲过了。(如果是新手，还请扎扎实实地学，一步一步来)

参考代码

#include <iostream>
#include <cstring>
#include <algorithm>
#define ls u << 1
#define rs u << 1 | 1
#define LL long long
const int N = 500010;
const LL INF = 1E18;
int n , m;
int a[N];
struct node{
	int l , r;
	LL sum , lmx  , rmx , mx;
}tr[4 * N];
void pushup(node &T , const node &L , const node &R){
	T.sum = L.sum   R.sum;
	T.mx = std::max(std::max(L.mx , R.mx), L.rmx   R.lmx);
	T.lmx = std::max(L.lmx , L.sum   R.lmx);
	T.rmx = std::max(R.rmx , R.sum   L.rmx);
}
void build(int u , int l , int r){
	tr[u] = {l , r , a[l] , a[l] , a[l] , a[l]};
	if(l == r) return ;
	int mid = (l   r) >> 1;
	build(ls , l , mid);
	build(rs , mid   1 , r);
	pushup(tr[u] , tr[ls] , tr[rs]);
}
void modify(int u , int x , LL c){
	if(tr[u].l == x && tr[u].r == x) {
		tr[u] = {x , x , c , c , c , c};
		return ;
	}
	int mid = (tr[u].l   tr[u].r ) >> 1;
	if(x <= mid) modify(ls , x , c);
	else
		modify(rs , x,  c);
	pushup(tr[u] , tr[ls] , tr[rs]);
}
node query(int u , int l , int r ){
	if(l <= tr[u].l && tr[u].r <= r) return tr[u];
	int mid = (tr[u].l   tr[u].r) >> 1;
	if(r <= mid) return query(ls , l , r);
	if(l > mid) return query(rs , l , r);
	node T ;
	pushup(T , query(ls , l , mid) , query(rs , mid   1 , r) );
	return T;
}
int main(){
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin >> n >> m;
	for (int i = 1; i <= n; i    ) std::cin >> a[i];
	build(1 , 1 , n);
	while(m -- ){
		int opt , l , r;
		std::cin >> opt >> l >> r;
		if(opt == 1){
			if(l > r) std::swap(l , r);
			std::cout << query(1 , l , r).mx << 'n';
		}else
			modify(1 , l , r);
	}
	return 0;
}

区间gcd

懒标记

对于gcd(a , b) 存在一些性质，比如 gcd(a , b , c) = gcd(gcd(a , b) , c) 如果你对gcd 不了解的话，请你看我的关于gcd 和 lcm 相关结论和性质的介绍。

那么这就是区间信息的维护，需要的话加上懒标记对吧，所以比较简单。

差分维护

我们介绍另外一种，比较简单的维护方法的。

引入gcd性质

$gcd(a_1 , a_2 , a_3 …. , a_n) = gcd(a_1 , a_2 – a_1 , …..a_n – a_{n – 1})$

即原序列的gcd 也是差分的gcd

这种做法的延展性也非常好，直接维护序列差分信息。
1. 求区间和，这个非常好求。前面讲过，只需要维护两棵线段树即可。
2. 区间修改，差分的区间修改，只需要进行单点修改即可.
3. 区间gcd 查询， $gcd(a[l] , gcd(b_{l 1} , b_{l 2}…. , b_r))$ 这样求出即可。本人对于这种做法理解也不是特别深刻，建议去b站找相关视频再理解理解！哔哩哔哩

无法维护通过子节点维护区间信息的情况

一种做法：分块、莫队

另外一种可能的做法：线段树

通过题目给出的一些信息也可以发现一些性质，从题设的性质出发，找到突破口。 P4145 上帝造题的七分钟 2 / 花神游历各国 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这个题目需要发现一个性质：

题设给出数据范围最多 $10^{12}$ , 那么开方多少次就是1了呢（因为1开方不变）？

只需要6次开方就可以到1 所以我们可以考虑直接暴力区间修改，序列中所有的数，每个数最多可以开方6次，那么意味着区间修改是常数级别的。总的时间复杂度还是 $O (n l o g n)$ , 所以考虑直接暴力区修。 2 . 区间和，每次区间修改之后，pushup维护区间和即可。

这里推荐董哓算法的讲解

总结

线段树，还支持其他非常多的操作，无法一一列举。原因有二，一是、太多操作无法一一列举，情况太多。二是、笔者本身实力有限，暂时无法介绍更加深入的运用。类似于zkw 线段树、区间众数，李超线段树、线段树分裂等等算法，还请读者自行了解！祝大家 RP

线段树专题

前言

线段树的定义

为什么需要线段树

如何实现基本的线段树

建树

区间修改、查询

差分

懒标记

区间修改、查询

线段树的应用

区间最值

区间最大子段和

区间gcd

懒标记

差分维护

无法维护通过子节点维护区间信息的情况

一种做法 ：分块、莫队

另外一种可能的做法 ： 线段树

总结

相关文章

🏆 【革命尚未成功，同志还需努力】「写作之路，规划人生，距离目标我们还有多远？」｜2021 年中总结

LabVIEW+OpenCV快速搭建人脸识别系统(附源码)

清北「学渣」创业心路：AI 新时代已来，不参与对不起自己

【Python实战】Python采集地震信息

作者信息

一种做法：分块、莫队

另外一种可能的做法：线段树