「OI」线段树优化建图

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

[toc]

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

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

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

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

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

推荐题目：

POI2015 PUS