ST表

ST表的定义

\(\text{ST}\) 表，全称是 \(\text{Sparse Table}\) 又叫稀疏表， 是一种基于倍增思想的数据结构。 这个数据结构主要用来解决一类 可重复贡献问题。 最经典的应用是 \(\text{RMQ}\) 问题。

可重复贡献问题

假设我们现在存在一个运算 \(\text{R}\)，若 \(x \text{R} x = x\)，同时这个运算满足交换律。 那么这个运算所对应的区间查询问题，就是一个可重复贡献问题。

之所以要满足交换律，是因为 \(\text{ST}\) 表在查询区间信息的时候，可能会对某个区间多次计算。 如果计算满足交换律，在产生形如 \(x\text{R}y\text{R}x\) 的运算时， 等价于 \(x\text{R}x\text{R}y\)，又因为满足 \(x \text{R} x = x\)， 因此实际上等价于 \(x \text{R} y\) 。如此一来便不会因为某个部分重复贡献而导致结果产生错误。

例如在查询区间和时，如果我们在查询某个区间的时候，某个被其包含的子区间重复贡献了答案， 那么答案大概率会发生改变，这是不可接受的。这也是区间和不是一个可重复贡献问题的原因， 自然无法使用 \(\text{ST}\) 表来解决。

RMQ问题

\(\text{RMQ}\) 的全称是 \(\text{Range Maximum/Minimum Query}\)，也就是区间最大/小值查询问题。 因为 \(\max(x,x) = x,\min(x,x)=x\)，因此 \(\text{RMQ}\) 问题就是一种可重复贡献问题。

例题

给定一个 \(n\) 个数字组成的序列，给定 \(q\) 次查询，每次查询给定 \(l,r\)， 要求对于每一个查询，回答出区间 \([l,r]\) 内的最大值。

朴素且暴力的想法无疑是对于每一个查询的区间都暴力计算一下，这是平凡的， 同时时间复杂度也是无法接受的 \(O(nq)\)。

后续内容待补充