「OI」线段树优化建图

说实话,这个其实也没什么。线段树优化建图就是一个简单的技巧而已。

假设有 $n$ 个点,每个点都要向其他的很多点($\Theta(n)$)连边,那么建图的时间复杂度就是 $\Theta(n^2)$ 的。

但是利用一点点特殊性质,就可以优化到 $\Theta(n\log_2n)$。

举个例子:每个点向连续的 $K$ 个点连边。

把 $K$ 个点看作线段树最底下的那些长度为一的区间,其他的区间看作是虚点(一些为了快速加边的特殊点,有点像正常线段树的 lazytag),然后画画图,就好了。

显然最多可以连接 $\Theta(\log_2K)$ 条边,所以时间复杂度是 $\Theta(n\log_2K)$。

推荐题目:

POI2015 PUS