【小技巧】树剖套线段树优化建图如何做到 O(nlogn)

前提:用树剖套线段树优化树链连边。例题:bzoj4699

我们说树剖的时间复杂度是 $O(n imes log(n))$,是因为访问一条链时需要经过 $log(n)$ 级别条重链,对于每条重链还需要 $O(log(n))$ 的时间来区间查询。

但不难发现每次访问一条链时,只有两端的两条重链只被覆盖了其中一段,必须要用线段树找到那一段。每次查询只有常数条必须要用线段树的重链。

而中间一堆重链都被完全覆盖了。我们可以给每条重链建一个点,这个点连向重链在线段树上的对应区间,这样访问这些重链整体时就只需要 $O(1)$ 提取这个点的信息了,省掉了线段树区间查询的 $O(log(n))$ 的复杂度。

由于每次查询只有常数条必须要用线段树的重链,假设 $n,q$ 同阶($q$ 是访问次数),总时间复杂度降至 $O(n imes log(n))$。

这种题能给每个重链建一个点,是因为这种题不用 pushup / pushdown,不用考虑一个点与 $log(n)$ 级别个点间 pushup / pushdown 的问题。

原文地址:https://www.cnblogs.com/scx2015noip-as-php/p/10833028.html