[数据结构]二维ST表

类比一维 ST 表，我们可以用 表示左上角坐标为 ，右下角坐标为 的矩形区域的最大值，分情况将矩形区域分割为横向或纵向两部分，不难想到状态转移方程：

预处理复杂度 。查询也很简单，只要分成四块区域就可以了：

其中 表示原二维矩阵， 为左上角坐标， 为右下角坐标，，，，。查询复杂度 。

一点小优化：

用库函数来计算 效率比较低，我们可以使用下面的代码实现 计算：

const auto lb = [](const int x) -> const int { return x ? 31 - __builtin_clz(x) : 0; };

原理是利用了 __builtin_clz 内置函数来计算最高有效位的位置。具体来说，__builtin_clz(x) 返回 x 的前导零的数量，31 - __builtin_clz(x) 则计算出 x 的最高有效位的位置，从而得到 floor(log2(x)) 的值。

题目推荐

CF846D Monitor (Luogu Mirror)