作用

线段树通过维护序列,可以维护一个承载各种操作的时间轴。

通常用于辅助一些不支持删除操作的数据结构(线性基,并查集),
这种情况可以用线段树分治维护操作影响的时间来巧妙地避开删除。

线段树结构

线段树分治用到的线段树(以下简称线段树)是以询问的时间为键值,
没有权值只有标记的线段树。

也就是线段树的一段区间对应的是一段询问(一段时间)。

这样的线段树只需要支持区间修改(打标记)。
每一个操作都会影响一段时间,对应于线段树的区间修改。

例题

这玩意需要一个例题才讲的清。
(由于线段树分治用于辅助其他数据结构,再看例题前得先会线性基)

维护一个集合,每次操作可以加入一个数或删除一个已经存在与集合的数。
每次操作后要回答这个集合的最大异或和。
操作次数 1e5 。

暴力线性基

如果只有插入没有删除,这题就是一遍线性基。

但是不巧线性基不支持删除,所以只能在每次删除后重构线性基。
复杂度平方带对数,稳 T 。

时间轴

将每次操作看做时间点,假设数 x 在时刻 l 被插入, r 被删除,
那么 x 只存在于 [l, r) 这段时间,
假如每个时刻开一个线性基,那么将 x 插入 [l, r) 的每个线性基,
这样就可以在最后通过线性基询问得到每个时刻的答案,
复杂度还是平方带对数,稳 T 的离线算法。

线段树优化

比较上述两种算法,
第一种复杂度瓶颈在于重构线性基,实在是没有什么优化空间,
但是第二种算法中,复杂度瓶颈在于将 x 插入到 [l, r) 的每个线性基,
这个操作相当于一个区间修改,可以用线段树优化。

那么一个优秀的算法就出来了:
线段树每个节点维护一个 vector (相当于懒标记),插入 x 将直接加在线段树对应区间的 vector 内。
所有操作过后会得到一个只有懒标记的线段树,
然后考虑如何通过这样一颗线段树得出所有答案。

处理懒标记

懒标记下传?
不存在的,因为懒标记是一个 vector, 下传的复杂度并不是 O(1) ,
不难验证下传所有懒标记会使复杂度重回 n 方。

既然不能下传,那就进行 n 次单点查询?
一个道理,单点查询的复杂度并不是 log(n), 这样做同样对复杂度没有优化。

那就没救了

分治

线段树分治,不能只有线段树,还要分治啊。

现在需要只把每个懒标记访问一遍就得出所有答案。

dfs 整颗线段树(实际上就是分治),深度是 log 级别的,那么对每一个深度开一个线性基。
如能能让 dfs 每个节点时该深度线性基维护的是这个节点到根的所有懒标记,
最后 dfs 到每个叶子节点就可以得到该叶子节点到根的懒标记的线性基,也就可以求出这个叶子节点的答案。

假设当前 dfs 到 u, 深度为 d, 深度对应的线性基已经是维护其到根的懒标记。
dfs 到一个新点 v 一定会使深度 + 1 ,将当前深度 d 的线性基拷贝到下个深度 d + 1 中。
那么 dfs 到 v 后再将 v 的懒标记加到 d + 1 的线性基中,d + 1 的线性基也就满足了要求。
通过这样的过程就能够做到只访问每个懒标记一遍。

这就是线段树分治了。

真 – 例题

这两道题就没有这么裸了。

洛谷八纵八横 (线段树分治 + 线性基)

BZOJ 二分图 (线段树分治 + 并查集)

分类: 算法

发表评论

电子邮件地址不会被公开。 必填项已用*标注