线段树入门 学习笔记

1. 前言

线段树是所有数据结构中最重要的之一。本文主要用于帮助线段树的初学者更好地理解与掌握它，例题难度均不大于中位蓝，想进一步进阶的大佬们可以跳过这篇文章。

本文长度较长，可以选择性地观看。

本文的结构上参考了 @Hoks 的这篇和这篇学习笔记，内容部分参考了 OI-Wiki。

2. 线段树基础

2.1 定义

线段树是一种可以支持区间修改、区间查询的数据结构，本质上是一棵二叉树。线段树的修改与查询操作都是 O(n\log n) 的。

2.2 结构

对于树上的每一个节点，我们需要维护一段区间的信息。

让每个节点的子节点维护这段区间的子区间信息，且各个子节点之间维护的区间不重不漏，然后再用恰当的方式进行子节点向父亲节点的合并以及父节点向子节点的传递信息，这就是线段树的基本思想。

直觉上，少的节点肯定比多的节点好维护，所以每次修改时从上向下传递信息。

由于线段树是一棵二叉树，所以容易想到如下结构：

• 如果当前节点维护区间 [i,i]，该节点为叶子结点。
• 否则，设当前节点维护的区间为 [l,r]，\text{mid}=\dfrac{l+r}{2}，左儿子维护区间 [l,\text{mid}]，右儿子维护区间 [\text{mid}+1,r]。

这样做的好处是，由于每一层线段树每个节点所维护的区间长度都是父亲节点的一半，所以线段树深度为 \log n。

考虑这棵线段树的节点数量与维护序列长度 n 的关系。

上文提到线段树的深度最大为 \lceil\log n\rceil，故这棵二叉树的节点数量最多为 2^{\lceil\log n\rceil+1}-1，最大值当 n=2^x+1 时取到，此时原式最大值为 4n-5，所以线段树的数组大小大约要开到 4n。

2.3 代码实现

2.3.1 建树

以每个节点维护区间和为例。

由于二叉树的递归性质，所以在线段树上进行操作用递归实现比较方便。

假设线段树上当前节点编号为 x，该节点维护区间 [l,r] 的区间和。那么容易想到如下建树方法：

• 如果该节点为叶子结点，那么该节点的值为 a_l。
• 否则递归先更新两个子节点的值，然后将该节点的值设为两个子节点的线段树值之和。
• 令根节点为 1 号节点，节点 x 的左儿子编号为 2x，右儿子编号为 2x+1。

参考代码如下：

void pushup(int x){//更新线段树 x 号节点
    tr[x]=tr[2*x]+tr[2*x+1];//tr 为线段树数组
}
void build(int x,int l,int r){
    if(l==r)tr[x]=a[l];
    else{
        int mid=(l+r)/2;
        build(2*x,l,mid);//更新左儿子
        build(2*x+1,mid+1,r);//更新右儿子
        pushup(x);
    }
}

2.3.2 查询

假设现在需要求出序列区间 [\text{from},\text{to}] 的和，已经建好了线段树。

同样考虑递归。假设当前位于 x 号节点，维护的区间为 [l,r]，并且该区间与查询区间有交集，需要求出这个交集中所有的数之和。分情况讨论：

• 假设 [l,r] 不是查询区间的子集：
  • 定义 \text{ans=0}；
  • 如果查询区间与左儿子维护区间有交集，那么递归查询左儿子维护区间与 [\text{from},\text{to}] 的交集的和，然后让 \text{ans} 加上这个值；
  • 如果查询区间与右儿子维护区间有交集，那么递归查询右儿子维护区间与 [\text{from},\text{to}] 的交集的和，然后让 \text{ans} 加上这个值。
  • 返回 \text{ans}。
• 假设 [l,r] 是查询区间的子集，直接返回该节点的值。

由于 [\text{from},\text{to}] 一定是 [1,n] 的子集，所以答案就是从 1 号节点执行如上递归操作的结果。

代码：

int query(int x,int l,int r,int from,int to){
    int ans=0;
    if(from<=l&&r<=to)return tr[x];
    if(from<=mid)ans+=query(2*x,l,mid,from,to);
    if(to>mid)ans+=query(2*x+1,mid+1,r,from,to);
    return ans;
}

由于每次执行递归的节点只有可能是查询区间的两个端点所在的维护区间，所以每一层最多递归两个节点，总时间复杂度 O(\log n)。

2.3.3 单点修改

考虑将第 k 个数增加 v 时应该如何修改线段树。

如果 k 位于左儿子维护区间，递归更新左儿子；右儿子同理；如果当前节点为叶子结点，更新该节点的值加上 v，接下来回溯的过程中执行 2.3.1 中的 pushup 函数更新递归路径上的节点。

容易发现时间复杂度为 O(\log n)。

代码：

void update(int x,int l,int r,int k,int v){
    if(l==r&&l==k){
        tr[x]+=v;
        return ;
    }
    if(k<=mid)update(2*x,l,mid,k,v);
    else update(2*x+1,mid+1,r,k,v);
    pushup(x);
}

2.3.4 懒标记与区间修改

区间修改时，需要把修改区间中覆盖的每个节点都修改一遍，时间复杂度退化到 O(n\log n)，无法承受。因此，我们引入懒标记的概念来解决这一问题。

当区间修改把一个区间修改完之后，如果要往下一直递归修改，会导致时间复杂度爆掉。此时我们在这个节点打一个标记 v，表示现在这个节点的子树（除该节点本身）维护的值比实际的值少 v。

等到下一次区间修改或区间查询需要用到这个节点的子节点的维护值时，再把两个子节点的维护值更新，并且将该节点的懒标记清空（两个子节点的值之和已经与父节点维护值相同），将两个子节点的懒标记加上原来该节点的懒标记值（这两个子节点的四个子节点现在比她们的父节点又少了 v）。

这样复杂度就会变成 O(\log n)。

参考代码：

void pushdown(int x,int l,int r){
    if(l==r)return ;
    tr[2*x].sum+=(mid-l+1)*tr[x].tag;
    tr[2*x+1].sum+=(r-mid)*tr[x].tag;
    tr[2*x].tag+=tr[x].tag;//注意这里需要 + 而不是直接赋值
    tr[2*x+1].tag+=tr[x].tag;
    tr[x].tag=0;
}
void update(int x,int l,int r,int from,int to,int v){
    if(from<=l&&r<=to){
        tr[x].sum+=(r-l+1)*v;//区间长度*更新值
        tr[x].tag+=v;
        return ;
    }
    pushdown(x,l,r);//更新懒标记与子节点的值
    if(from<=mid)update(2*x,l,mid,from,to,v);
    if(to>mid)update(2*x+1,mid+1,r,from,to,v);
    pushup(x);
}

注意有区间修改操作时区间查询向下递归前也需要调用 pushdown 函数下传懒标记。

2.4 例题

2.4.1 P3372

例 1：P3372 【模板】线段树 1

给定一个长度为 n 的数列，q 次操作，操作为区间加或查询区间和。

解析：直接把上面的代码拼到一起即可。

参考代码。

2.4.2 P1816

例 2：P1816 忠诚

给定一个长度为 n 的数列，q 次询问，查询区间最小值。

解析：线段树每一个区间维护区间最小值，由于没有修改操作，不需要写懒标记和 update。

参考代码。

2.4.3 P3870

例 3：P3870 [TJOI2009] 开关

给定一个长度为 n 的 0-1 数列，q 次操作，每次操作为区间取反或区间求和。数列一开始都为 0。

解析：每次修改更新时只需要更新为区间长度减去原线段树值即可。由于初始序列全为 0 所以无需建树。

2.4.4 P3373

例 4：P3373 【模板】线段树 2

给定一个长度为 n 的数列，三种操作：区间乘、区间加、区间求和。

解析：

本题主要涉及两种标记：乘法懒标记和加法懒标记。

这样本题涉及了三种更新：线段树维护的区间和对区间和的更新、标记对线段树维护值的更新和标记对标记的更新。

首先考虑节点对节点的更新：很简单，就是 P3372 中 pushup 的更新。

然后考虑标记对标记的更新：如果打上一个区间加标记，那么该标记对区间乘标记没有影响；反之区间乘标记会使原来的区间加标记乘上这次更新的乘数。

最后是标记对节点的更新：先乘上乘标记，再加上加标记。顺序不能调换，否则会使加标记乘上不该乘的乘标记。

代码好久之前写的，很丑。

3. 值域线段树

3.1 概念

不对维护序列本身建线段树，而是对维护序列的值域（即 a_i 的范围）建树维护，然后按照一定的顺序，依次将序列中的数加入线段树中，在求解二维偏序问题时常常有奇效。

有时值域可能过大，此时需要先将数据离散化。

光描述可能有些抽象，让我们看几道例题。

3.2 例题

3.2.1 P1908

例 5：P1908 逆序对

给定一个长度为 n 的数列，求数列中逆序对的数量。

解析：

很多人都写过本题的归并排序写法，但是树状数组/线段树写法的泛用性更强一些。

考虑先将原序列离散化。注意到 n\leq5\times10^5，因此离散化后的数列 b 中的最大值不会超过 5\times10^5。

接下来建一棵值域为 [1,5\times10^5] 的空线段树，结点维护区间和。然后从左往右扫描序列 b，每次将线段树中 b_i 的值增加 1。这样，线段树中所维护的就相当于 b_1 到 b_i 中值在 [l,r] 范围中的数的个数。

在修改操作完成之后，查询 [b_i+1,5\times10^5] 范围的数。由于目前加入的所有数所对应的下标都不超过 i，所以线段树中只要值比 b_i 大的元素与 b_i 构成一对逆序对，因此直接把查询到的值加入答案。

拿归并排序写的，就不放代码了。

3.2.2 P10814

例 6：P10814 【模板】离线二维数点

给定一个长度为 n 的数列 a，q 次询问，每次询问给定三个数 l,r,x，求区间 [l,r] 中不大于 x 的元素的数量。

注：本题轻微卡常，建议优化读入。

解析：

本题不需要离散化，还算良心。

询问区间 [1,r] 内不大于 x 的元素个数可以拆成两个询问相减，也就是 [1,r] 内不大于 x 的元素个数减掉 [1,l-1] 中不大于 x 的元素个数。

这样就拆成了 2q 组询问，然后按询问区间的右端点递增排序。

对 a 数组建值域线段树，然后从左往右依次加入 a 中的元素。如果往值域线段树中加入了 a_i，此时恰好有一组询问 [1,i]，那么就对询问作出回答。

这样就可以 O((n+q)\log V) 来求出拆开的 2q 组询问的答案，其中 V 是值域。然后就可以计算出初始的 q 组询问了。

略微抽象的代码。

4. 线段树上二分

4.1 介绍

由于二叉树的性质，如果把二分的过程放到线段树上实现，二分的 \log 放到了线段树上，所以只需要一只 \log 就可以完成二分套线段树中两只 \log 的操作。

4.2 例题

4.2.1 P1168

例 7：P1168 中位数

给定一个长度为 n 的数列 a，对于所有 n 以内的奇数求区间 [1,i] 的中位数。

解析：

首先考虑将 a_i 离散化之后建权值线段树。从左往右将离散化后的 b_i 加入线段树中，加入完后如果 i 是奇数那么就查找线段树中的中位数。

那么如何查询呢？由于权值线段树中每个节点的右节点所维护的 b_i 值都比左节点所维护的大，所以满足单调性，考虑二分。

考虑线段树每个节点维护区间和。假设我们现在需要查询线段树维护区间 [l,r] 中的第 k 大值，只要看一眼左儿子维护的区间 [l,\text{mid}] 中的 b_i 的个数。如果区间中的数字个数大于等于 k，那么第 k 大值的值一定位于区间 [l,\text{mid}] 上，递归查询左儿子的第 k 大值；否则记左儿子维护区间中 b_i 的个数为 c，递归查询 [\text{mid+1},r] 中的第 k-c 大值即是答案。

拿对顶堆写的，不放代码了。

5. 可持久化权值线段树

5.1 动态开点线段树

容易发现朴素的线段树有时会浪费掉空间，所以可以不让二叉树的两个儿子编号为 2x 和 2x+1，而是按顺序用到时再建，这样空间复杂度就会降低（虽然没有什么用）。

假设当前节点左儿子编号为 \text{lc}，右儿子为 \text{rc}，每一次修改或查询时只需要将 2x 或 2x+1 改为 \text{lc} 或 \text{rc}。

建树也同理。

5.2 引入

例 8：P3834 【模板】可持久化线段树 2

给定 n 个整数组成的序列 a，q 次询问，每次询问对于指定的闭区间 [l,r]查询其区间内的第 k 小值。

为了解决这个问题，我们引入可持久化值域线段树。

5.3 可持久化线段树的概念与思路

5.3.1 介绍

可持久化线段树又名主席树，与普通线段树的区别在于可以维护历史区间信息，也就是可以维护某一次修改前的历史版本信息。缺点在于空间复杂度为 O(n\log n)，常数比较大。

5.3.2 实现思路

由于普通的线段树每次更新时会覆盖原来节点维护的信息，所以考虑保留原来的节点。

为了维护新的更新值，可以新开一个节点来维护信息。

下面以例 8 为例。

首先离散化。假设离散化后的数组仍叫做 a。

考虑比较暴力的做法，建 n 棵值域线段树，第 i 棵树存储 a_1\sim a_i 的值在值域中的情况。对于询问 [l,r]，可以把第 r 棵线段树与第 l-1 棵线段树对应节点相减，在减完后的线段树上二分出区间的第 k 小。如果二分到一个节点的时候的时候相减对应的区间，可以保证单次询问时间复杂度 O(\log V)。但是这样显然会 MLE。

容易发现由于每个 a_i 进行的修改都是单点修改，所以最多修改 \log V 个节点。因此第 i 棵树与第 i-1 棵树最多只有 \log V 个节点值不同。这启示我们将第 i 棵树与第 i-1 棵树共用一个数组，然后新建 \log V 个节点，一共 n 棵树，空间复杂度大约是 O(n\log V) 的。

我们刚刚介绍到了动态开点线段树，这个新建节点的操作正好可以用动态开点线段树来实现。

5.3.3 代码实现

考虑代码实现。

5.3.3.1 建树

令 \text{rt}_i 表示第 i 棵线段树的根节点的节点编号（这个节点显然每棵树都不能共用）。

首先建一棵树编号为 0 的空树，以后的每一棵树都在树编号为 i-1 的树的基础上修改一条链得到。

建空树的代码如下：

int build(int l,int r){
    int rt=++tot;//rt 代表这个节点的节点编号，tot 代表节点数量
    if(l==r)return rt;
    tr[rt].ls=build(l,mid);//ls 代表左儿子节点编号，rs 代表右儿子节点编号
    tr[rt].rs=build(mid+1,r);
    return rt;
}

rt[0]=build(1,n);

5.3.3.2 更新

考虑更新。正常的动态开点线段树写法。

#define mid (l+r)/2

int update(int k,int l,int r,int rt){
  //k 代表插入的值，[l,r] 表示该节点维护的区间
    int dir=++tot;//dir 代表新建的节点，rt 表示上一棵线段树与 dir 维护区间对应的节点编号
    tr[dir].ls=tr[rt].ls;
    tr[dir].rs=tr[rt].rs;
    tr[dir].sum=tr[rt].sum+1;//加上 k 这个数
    if(l==r)return dir;
  //更新子节点
    if(k<=mid)tr[dir].ls=update(k,l,mid,tr[dir].ls);
    else tr[dir].rs=update(k,mid+1,r,tr[dir].rs);
    return dir;
}

rt[i]=update(a[i],1,len,tr[i-1].rt);//len 为离散化之后的值域

5.3.3.3 查询

线段树上二分，查询左子树中 a_i 个数时现减两个对应节点。

int query(int u,int v,int l,int r,int k){
  //第 v 棵树减去第 u 棵树对应节点，查询区间 [l,r] 内第 k 小
    int x=tr[tr[v].ls].sum-tr[tr[u].ls].sum;
  //查询左儿子维护区间中的 ai 个数
    if(l==r)return l;
    if(k<=x)return query(tr[u].ls,tr[v].ls,l,mid,k);
    else return query(tr[u].rs,tr[v].rs,mid+1,r,k-x);
}

query(rt[l-1],rt[r],1,len,k);

完整代码。

5.4 例题

5.4.1 P3919

例 9：P3919 【模板】可持久化线段树 2

给定 n 个整数组成的序列 a，q 次操作：

1. 在某个历史版本上修改某一个位置上的值
2. 访问某个历史版本上的某一位置的值 编号为 x 的历史版本意思是执行完毕第 x 次操作的序列。版本 0 是指初始数组。

解析：板子题，基本上代码和上面的思路一样。版本就相当于建的第几棵树。

AC 代码。

5.4.2 P1383

例 10：P1383 高级打字机

给定一个小写字母构成的字符串，n 次操作：

1. 在末尾插入小写字母 x。
2. 查询第 x 个字母输出。
3. 撤销最后 x 次插入或撤销操作。

解析：

撤销修改操作就相当于这棵树与第 i-x 棵树完全相同，将这棵树的根节点设为第 i-x 棵树的根节点即可。

主席树的叶节点维护节点对应字母权值，非叶结点除了左右儿子外什么都不需要维护。

Code.

6. 线段树优化 DP

6.1 何时能优化

有时在动态规划的状态转移方程中，涉及到查询区间求和或区间最值或区间平方和等等操作，这时就可以利用数据结构进行优化。

接下来看几道例题。

6.2 例题

6.2.1 AT_chokudai_S001_h

例 11：AT_chokudai_S001_h LIS

给定一个长为 n 的序列 a，求这个序列的最长单调上升子序列（LIS）长度。

解析：

本题可以用二分来解决，但是此处讲解数据结构做法。

设 f_i 表示 a 中以 a_i 结尾的 LIS 的长度，那么容易列得转移方程

f_i=\max_{1\leq j\leq i-1,a_j<a_i}f_j+1

考虑建值域线段树，对于第 i 个数 a_i，首先查询区间 1\sim a_i-1 中线段树的最大值，加 1 记为 f_i，然后向线段树第 a_i 个位置对 f_i 取 \max。

答案即为 f 中的最大值。

6.2.2 AT_dp_q

例 12：AT_dp_q Flowers

有一排花，一共 n 盆，第 i 盆花的高度为 h_i，权值为 a_i，保证 h_i 互不相同。

现在拿走一些花，使剩下的花高度单调递增，问剩下的花权值之和最大是多少。

解析：

设 f_i 表示前 i 盆花中，必选第 i 盆花的所有选法中权值和最大为多少，容易列得状态转移方程

f_i=\max_{1\leq j\leq i-1,a_j<a_i}f_j+a_i

发现满足条件的 f_j 最大值可以用权值线段树来维护，于是就可以 O(n\log V) 解决这道题目。

代码。