【科技】如何对ST表进行卡常

正常情况下，ST 表是 $O(n \log n)$ 预处理并且 $O(1)$ 查询的。这基于其对两个 $2^k$ 的区间的合并。

考虑我们先不采用 ST 表求解 RMQ，而是采用一个比较小众的方法：笛卡尔树+LCA。这样的话问题就变成了如何求 LCA。众所周知，一种非常快速的求 LCA 的方法是欧拉序+RMQ，这样由于欧拉序的长度是原序列的两倍，我们成功将 ST 表的复杂度的常数翻倍。

同时，注意到这种卡常方法具有优秀的可扩展性。因为新问题仍然是一个 RMQ 问题，我们可以考虑再使用笛卡尔树解决，这样新的序列长度继续翻倍。

不难导出以下公式：当嵌套 $k$ 层笛卡尔树的时候，查询的复杂度变为 $O(2^kn\log 2^kn)$。其中，$\log 2^kn=\log2^k + \log n=k + \log n$，因此复杂度为 $(2^kn\log n + 2^knk)$。当 $k > \log n$ 时， 不难发现 $n$ 可以被视作常数，因此我们成功压掉了原来的复杂度瓶颈 $n$，可以将复杂度变为 $O(k2^k)$。