ST表的为什么

关于构建

层数与管辖长度的对应关系

ST表的一个关键设计在于每一层对应着该层元素掌管的区间长度. 这种对应关系直接影响了ST表的构建方式和查询效率.

线性增长 (1×层数) 的构建方式

如果采用1×层数的方式构建ST表, 对于一个数组[1, 2, 3, 4, 5, 6, 7, 8], 构建结果如下:

1 2 3 4 5 6 7 8
2 3 4 5 6 7 8
3 4 5 6 7 8
4 5 6 7 8
5 6 7 8
6 7 8
7 8
8

这种构建方式的问题在于:

1. 预处理时间复杂度为$O(n^2)$
2. 没有利用问题的可重复贡献性质

指数增长 (2^层数) 的构建方式

更优的方案是采用2^层数的方式构建ST表, 同样的数组构建结果如下:

第0层：1 2 3 4 5 6 7 8  (每个元素负责2^0=1个元素)
第1层：2 3 4 5 6 7 8    (每个元素负责2^1=2个元素)
第2层：4 5 6 7 8        (每个元素负责2^2=4个元素)
第3层：8                (每个元素负责2^3=8个元素)

这种设计带来了显著优势：

1. 预处理时间复杂度降低到$O(n \log n)$
2. 查询时可以通过$O(1)$时间组合两个区间得到任意区间答案

为什么选择2作为基数？

1. 区间覆盖的完备性

$2^j$ 的设计保证了任何区间都能被恰好两个子区间完全覆盖. 例如，查询区间$[2,8]$可以通过:

• 从第2层选择$[2,5]$ (长度为$4$)
• 从第2层选择$[5,8]$ (长度为$4$)

两个区间组合而成, 恰好覆盖$[2,8]$且没有遗漏或过多重叠.

相比之下, 如果使用$3^j$作为基数, 以数组[1,2,3,4,5,6,7,8,9]为例：

第0层：1 2 3 4 5 6 7 8 9
第1层：3 4 5 6 7 8 9
第2层：9

查询$[2,8]$时, 无法找到两个长度为$1$/$3$/$9$的区间来完全覆盖, 至少需要三个区间才能完成, 这大大增加了查询逻辑的复杂性.

2. 计算效率优势

$2^j$的计算可以通过位移操作高效实现, 不浪费性能.

3. 对数级别的层数

以$2$为底的对数增长使得层数控制在$\log_{2} n$, 比使用更大的基数 (如$3$) 能更好地平衡预处理和查询的开销.