线段树

Segment Tree

Posted by hongzhiyin on November 5, 2019

相关概念

节点

线段树中的每个节点对应一个区间 $[l,\ r]$ ,

区间端点 $l$ 和 $r$ 的值其实维护在函数参数中,如:

1
2
3
void build(int l, int r, int rt);
void upd(int L, int R, int val, int l, int r, int rt);
int qry(int L, int R, int l, int r, int rt);

$l$ 和 $r$ 表示编号 $rt$ 的节点所对应的区间 $[l, r]$

因此 $l$ 和 $r$ 实际上可以为负数,只要其能代表一个区间。

子节点对应区间分别为 $[l, m]$ 和 $[m+1, r]$ , $m$ 为 $l + r » 1$

子节点编号分别为 $rt « 1$ 和 $rt « 1 \vert 1$

节点信息通常用结构体数组存储:

1
struct { int sum, len, lazy; } t[N<<2]

空间需要开区间长度 $N$ 的 $4$ 倍,原因在于大于 $2$ 的幂次的部分会多用节点编号。

可构建一棵区间长度为 $9$ 的线段树体会。

节点信息一般分为:

  1. 待查询信息
  2. 延迟标记信息
  3. 辅助信息,如该编号节点对应区间的长度。

待查询信息

如:区间和,区间最值,区间异或和,区间 $GCD$ 等,需满足区间可加性。

即:根据两个子区间的信息,可以推导出合并区间后的信息。

一般在函数结尾时合并。

1
t[rt].sum = op(t[ls].sum, t[rs].sum);

延迟标记信息

涉及区间更新时,需要用到延迟标记,以保证复杂度。

本质为,暂存下对于某个区间的多次更新的操作,

当需要查询该区间的子区间时,能够对子区间一次性完成所有更新。

解题过程

  1. 前提:区间查询的结果满足区间可加性。

  2. 列出关于区间修改的表达式

    1. 列出关于单点修改的表达式

      \[x_i = F(x_i)\]
    2. 列出关于区间修改的表达式

      \[sum(l, r) = F(\ sum(l, r)\ )\]
    3. 列出重复在同一区间上修改 $k$ 次的表达式

      \[sum(l, r) = F(\ sum(l, r),\ k\ )\]
    4. 包含有 $k$ 的部分即为延迟标记需要维护的部分

      \[sum(l, r) = F(\ lazy(k),\ sum(l, r)\ )\]
  3. $build(1, n, 1)$ 中初始化 “待查询信息” 与 “延迟标记信息”

  4. 区间更新 $upd(l, r, val, 1, n, 1)$

    1. $Add(rt, val)$ 可看作一次 $pushdown$ ,将更新内容作用到对应节点,

      更新结点所维护的 待查询信息 和 延迟标记 。

  5. 区间查询 $qry(l, r, 1, n, 1)$

例题

深入理解延迟标记: HDU 6562 Lovers