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

SnowFlavour · 2025-11-21 10:34:24 · 休闲·娱乐

正常情况下，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)。