ST表思想用来解决区间最值查询问题。与线段树相比,ST表只支持离线问题,但是在经过$O(n \lg n)$的预处理之后,ST每次询问的复杂度是$O(1)$的,而线段树的询问是$O(\lg n)$的,所以ST适合解决规模更大的离线问题。

Continue reading

Tarjan算法是线性时间求解有向图强连通分量(SCC)的算法,它曾一度把我搞到头皮发麻。如今国内的教程基本来自于byvoid大神的博客,包括我高中时期的OI老师的课件和代码也是从此处来的。这么多年来,虽然能用这个算法解决一些算法题,但是有几个点还是不甚理解。直到我在YouTube上看到了“Tarjans Strongly Connected Components algorithm | Graph Theory – WilliamFiset”这个视频,之前的一些疑问得以解开,因此记录下这篇博文。

Continue reading