算法提高课汇总

线段树

无懒标记

原理

结构

对于线段树的内部节点, 假设其管理区间$[l, r]$的信息, $mid = \lfloor (l + r)/2 \rfloor$,
其左右子节点分别管理区间$[l, mid], [mid + 1, r]$的信息. 线段树的根节点
管理整个区间的信息, 从上至下节点管理区间依次减半直到叶节点管理区间
长度为$1$的区间 — 单个元素的信息.

存储

线段树是一颗满二叉树 — 内部节点均有左右子节点, 可以用一维数组存储.
根节点编号为$1$, 对于某个节点$x$, 其父节点和左右节点的编号分别是:
$\lfloor x/2 \rfloor, 2\times x. 2\times x + 1$.

存储空间

考虑存储线段树的一维数组需要多大的空间, 这里我们要考虑的是编号的
最大范围而不是节点个数. 假设数列的长度为$n$:

• 如果$n = 2^k$, 线段树恰好是一颗完全二叉树, 深度$h = k + 1$, 节点的最大
  编号为$2^h - 1 = 2^{k + 1} - 1 = 2n - 1$.

• 如果$2^k\lt n\lt 2^{k + 1}$, 相比于上一种情况线段树需要额外一层存储多出的节点,
  若编号最大的节点$2n - 1$有子节点, 则其右儿子编号为$4n - 1$, 实现时一般为
  一维数组开辟$4n$的存储空间.

操作

$pushup$

用左右子节点信息更新父节点信息.

pushup(u) //u为待更新节点编号
    tr(u) = op{tr(u << 1), tr(u << 1 | 1)} //op对应线段树需要维护信息的操作

$build$

根据输入数列自底向上建立线段树.

build(u, l, r) //u为节点编号, [l, r]为节点管理区间
    tr(u) = {l, r}
    if l == r:
        叶节点管理单个元素信息
    else:
        mid = (l + r) / 2
        //先递归创建左右子子节点
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r)
        pushup(u) //用已经建立完毕的左右子节点信息更新当前节点

$query$

查询某段区间的信息.

查询思路: 设$[L, R]$为查询区间, $T_l, T_r$为当前节点管理区间,
查询时考虑下述几种可能:

1. $[T_l, T_r]\subset [L, R]$, 节点管理的区间在查询区间内, 直接返回当前区间信息.
   当前节点管理的信息不含查询区间外信息, 继续向下查询不会得到额外信息.

2. $[T_l, T_r]\cap [L, R]$, 递归查询区间与$L, R$相交的子节点.

3. 查询过程中不会出现$[T_l, T_r]\cap [L, R] = \emptyset$的情况: 根节点管理
   整个区间, 查询区间一定与其相交; 查询操作保证只对有交集的子节点递归查询.

查询的时间复杂度:

1. 查询时如果出现$[T_l, T_r]\subset [L, R]$, 函数返回, 时间为常数.

2. 考虑三种情况:

   • 2.1
     
     2.1.1 $L\gt T_{mid}$, 则只有右半区间与查询区间有交集, 只需递归右子节点.
     2.1.2 $L\le T_{mid}$, 此时左右子节点都需递归查询, 如果每次都需要递归
     左右子节点, 时间复杂度为深度的指数; 考虑查询函数进入右子节点: 出现
     情况$1$, 函数直接返回, 不会出现每次都需递归左右子节点情况.
   • 2.2
     
     与情况$2.1$对称, 函数基本只有向下的一条链.
   • 2.3
     
     2.3.1 $R\le T_{mid}$, 此时只有左半边区间与查询区间相交, 只需递归左子节点.
     
     2.3.2 $L\gt T_{mid}$, 与2.3.1对称, 只需要递归右子节点.
     2.3.3 $L\le T_{mid}\lt R$, 此时需要递归左右子树. 对于左子树: 其管理区间为
     $T_l, T_{mid}$(这里的数值使用其父节点区间), 而$T_{mid}\lt R$, 不会存在查询区间
     完全被节点区间包含的情况(即情况2.3.3), 所以2.3.3需要递归左右子树的情况
     最多只会出现一次.

综上, 考虑时间复杂度最差情况: 首先出现情况2.3.3, 存在两条向下递归的
函数链条; 对于后续每个节点, 均为一个子节点向下持续递归, 另一个子节点
进入后返回的情况(如2.1.2). 由于线段树深度为$\lg{n}$, 每层都有$4$个节点,
所以时间复杂度最差为$O(4\times \lg{n})$.

下图为一种搜索路径的展示, 图中仅画出函数进入的节点:

$modify$

修改单个元素, 思路: 递归向下直到对应该单个元素的叶节点, 修改叶节点并通过$pushup$
操作自底向上更新父节点(将修改后的信息向上传递).

带懒标记