相关概念
节点
线段树中的每个节点对应一个区间 $[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$ 的线段树体会。
节点信息一般分为:
- 待查询信息
- 延迟标记信息
- 辅助信息,如该编号节点对应区间的长度。
待查询信息
如:区间和,区间最值,区间异或和,区间 $GCD$ 等,需满足区间可加性。
即:根据两个子区间的信息,可以推导出合并区间后的信息。
一般在函数结尾时合并。
1
t[rt].sum = op(t[ls].sum, t[rs].sum);
延迟标记信息
涉及区间更新时,需要用到延迟标记,以保证复杂度。
本质为,暂存下对于某个区间的多次更新的操作,
当需要查询该区间的子区间时,能够对子区间一次性完成所有更新。
解题过程
-
前提:区间查询的结果满足区间可加性。
-
列出关于区间修改的表达式
-
列出关于单点修改的表达式
\[x_i = F(x_i)\] -
列出关于区间修改的表达式
\[sum(l, r) = F(\ sum(l, r)\ )\] -
列出重复在同一区间上修改 $k$ 次的表达式
\[sum(l, r) = F(\ sum(l, r),\ k\ )\] -
包含有 $k$ 的部分即为延迟标记需要维护的部分
\[sum(l, r) = F(\ lazy(k),\ sum(l, r)\ )\]
-
-
$build(1, n, 1)$ 中初始化 “待查询信息” 与 “延迟标记信息”
-
区间更新 $upd(l, r, val, 1, n, 1)$
-
$Add(rt, val)$ 可看作一次 $pushdown$ ,将更新内容作用到对应节点,
更新结点所维护的 待查询信息 和 延迟标记 。
-
-
区间查询 $qry(l, r, 1, n, 1)$
例题
深入理解延迟标记: HDU 6562 Lovers