ST 表是借用倍增思想的数据结构，它通过预处理每个数后面 \(2^k\) 个数的最大值来 \(O(1)\) 查询静态区间最大值。
设 \(f(i,j) = \max_{k = i}^{i + 2^j - 1}\{a_k\}\)，那么 \(f(i,j)\) 的最大值就是左半部分的最大值和右半部分的最大值取最大值，即 \(f(i,j)=\max\{f(i,j-1),f(i+2^{j-1}, j-1)\}\)
查询 \(\max_{i=l}^r a_i\) 的时候，可以取 \(k=\log_2(r-l+1)\)，那么答案就是 \(\max\{f(l,k),f(r-2^k+1,k)\}\)。
我们发现，ST 表能解决的区间问题需要满足：
- 有结合律
- 自己与自己运算的结果还是自己
满足这些条件的运算包括但不限于最大值、最小值、\(\gcd\)、\(\text{lcm}\)、按位与、按位或等等，但不包括按位异或。
OI 其实不怎么考 ST 表，它的应用也比较少，不掌握也没太大的关系。