线段树专题

前言

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

线段树的定义

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

为什么需要线段树

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

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

如何实现基本的线段树

建树

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

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

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

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

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

3. 递归建树

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

区间修改、查询

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

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

差分

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

• 修改操作步骤

  • 对原序列进行差分
  • 对于区间$[l,r]$修改只需要对 $l$点加上 C ，再对$r1$ 点减去C即可（$r1\le n$ 注意边界）

• 查询

  • 单点查询 直接求 $[1,i]$ 的前缀和 , 这个操作的是时间复杂度是$O(logn)$
  • 区间查询 那么就需要一点技巧这里给出步骤，并附上证明
    • 步骤
      1. 考虑维护两棵线段树 ，一棵线段树维护序列差分区间和∑i=lrdisum_{i=l}^r d_i∑i=lr​di​ , 另外一棵线段树维护∑i=lrdi∗isum_{i = l}^r d_i* i∑i=lr​di​∗i
      2. 求区间和只需要对使用公式 (r 1)∑i=1rdi−l∑i=1l−1di−(∑i=1rdi∗i−∑i=1l−1di∗i)(r 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)(r 1)∑i=1r​di​−l∑i=1l−1​di​−(∑i=1r​di​∗i−∑i=1l−1​di​∗i)
    • 证明
      1. 区间和我们可以表示成这样 (笔者是类比树状数组求区间和的方法，可能存在错误)
      ∑i=lr∑j=1idj=((r 1)∑i=1rdi−(l−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)i=l∑r​j=1∑i​dj​=((r 1)i=1∑r​di​−(l−1 1)i=1∑l−1​di​)−(i=1∑r​di​∗i−i=1∑l−1​di​∗i)
      核心思想：求前缀和再做差

  第一种方法代码不给出，主要就是介绍思想 , 代码可以自行网络查找。如果遇到这种情况，可以借助另外一种数据结构更为方便。

懒标记

• 区间修改、查询

先瞅瞅懒标记tag

先好好说说

• 懒标记

  • 是什么？ 用于记录历史修改操作的区间标记，大白话就是把之前没有进行的操作进行一下。

  • 有什么用？ 用于记录历史标记，对区间进行修改时减少许多不必要的操作。

    例如：我一直对区间[l1,r1][l_1 , r_1][l1​,r1​] 操作 ， 但是我只询问[l2,r2][l_2 , r_2][l2​,r2​] , 明显[l1,r1][l_1 , r_1][l1​,r1​] 那个区间不需要修改

  • 什么时候使用它？ 在需要对这个区间操作的时候，如果存在懒标记，那么将子节点的信息算好，懒标记再下传即可。

  • 核心要点：

    • 懒标记是给子节点用的！
    • 下传懒标记操作，实际是先通过操作父结点懒标记时算好子结点的信息，再将父结点懒标记传给子结点（这里称维护结点信息）。
    • 这个操作往往发生在查询和修改的时候（一般会另外写一个pushdown函数）

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

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

• 区间修改

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

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

• 区间查询

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

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

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

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

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

• 参考代码

 #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] 的最大子段和。

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

求出最大子段和的方法 :

$max=max(tr[ls].max,tr[rs].max,tr[ls].maxtr[rs].max)$

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

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

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

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

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

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

$tr[u].lmax=max(tr[ls].sumtr[rs].lmax,tr[ls].lmax)$

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

$tr[u].rmax=max(tr[rs].sumtr[ls].rmax,tr[rs].rmax)$

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

• 参考代码

#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(a1,a2,a3….,an)=gcd(a1,a2−a1,…..an−an−1)gcd(a_1 , a_2 , a_3 …. , a_n) = gcd(a_1 , a_2 – a_1 , …..a_n – a_{n – 1})gcd(a1​,a2​,a3​….,an​)=gcd(a1​,a2​−a1​,…..an​−an−1​)

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

  这种做法的延展性也非常好，直接维护序列差分信息。

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

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

一种做法 ：分块、莫队

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

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

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

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

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

这里推荐董哓算法的讲解

总结

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