线段树 SEGMENT TREE

HYLW · 2024-03-15 21:46:24 · 科技·工程

前言-INTRODUCTION

线段树，是一种功能更全面的树状数组，可以做到更多复杂的操作，然而时间空间复杂度均有提高。

一、线段树基本思想-THE BASIC IDEA OF THE SEGMENT TREE

简单来讲就是分治，分而治之，当然，这里的线段树是二叉树，你也可以看做二分（然而二分也是分治）。

我们按照长度固定为 n 的数列依次确立 n 个节点，每个节点表示一个区间的信息，节点间当然有根叶关系，我们规定节点 k 代表区间 [l,r] ，其左右节点分别为 2k [l,\lfloor\frac{(r+l)}{2}\rfloor ] 与 2k+1 [\lfloor \frac{(r+l)}{2}\rfloor+1,r] 。

可以发现，这里使用了堆的存储方式。那么一个节点 k 满足：

1. 其父节点：\lfloor\frac{k}{2}\rfloor——k>>1
2. 其左儿子：2k——k<<1
3. 其右儿子：2k+1——k<<1|1

其中，根节点编号 k=1 表示区间 [1,n]，所有表示区间 [i,i] 的节点称为元线段，此时可知，所有的非元线段对应节点有左右子节点。

例如一个长度为 10 的数列，得到的线段树如图。

假如你看过这个视频，那么你应该会比较理解。

这里就可以看出线段树的第一个问题：空间复杂度。显然，对于一个长度为 n 的“线段”，其所需空间为 O(x)=O(1+2+4+8+……+\frac{n}{2}+n)\approx O(2n) ，然而，可以看见，在上述例子中 2n 的空间还不够，要开到 4n 。再加上线段树常用结构体，这就很\texttt{逆天}。

下面开始讲操作，这才是核心，我们将顺便看清线段树的时间复杂度。

二、线段树的基本操作-THE BASIC OPERATION OF SEGMENT TREE

一般来讲，最基础的线段树有五个操作——

由于线段树适用极广，我们用例题来示范一下：luogu P3372 【模板】线段树 1

动手。

0.初始化-INIT

一般我们把线段树设为结构体，线段树的每个节点应该包含它的范围、性质信息、懒标记。线段树数组开 4 倍。

当然根据题意也有其他设置。开long long。

const int N = 100100;
typedef long long ll;
int n,m;
struct node{
    int l,r;//范围：左右边界 
    ll sum;//性质信息：区间和 
    ll k;//懒标记 
    #define l(u) tr[u].l
    #define r(u) tr[u].r
    #define sum(u) tr[u].sum
}tr[N*4];//线段树数组：开 4 倍 

1.\texttt{build()} 操作-\texttt{build()} OPERATION

建立一棵线段树，我们从根节点开始分别向左右儿子深搜。