思路与算法

这是静态区间最大值查询。令 st[k][i] 表示从 i 开始、长度为2^k的区间最大值，由相邻两个长度2^(k-1)的块合并得到。查询 [L,R] 时取 k=floor(log2(R-L+1))，分别读取从L开始和以R结尾的两个长度2^k块，再取最大值。

正确性说明

建表时两个子块恰好覆盖父块，取max得到正确的区间最大值。查询的两个块都在原区间内，并且它们的并集覆盖整个查询区间。虽然中间可能重叠，max是幂等运算，同一元素多参与一次不会改变答案，所以两块的最大值就是查询答案。

复杂度

预处理 O(N log N)，每次查询 O(1)，总时间 O(N log N+M)，空间 O(N log N)。

易错点

数组元素允许是int范围内的负数，不能用0当作最大值的初始答案。对数取整要正确，查询长度是R-L+1。重叠块的方法适用于max，不可直接照搬到求和。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> lg(n + 1);
    for (int i = 2; i <= n; i++)
        lg[i] = lg[i / 2] + 1;
    vector<vector<int>> st(lg[n] + 1, vector<int>(n));
    for (int &v : st[0])
        cin >> v;
    for (int k = 1; k <= lg[n]; k++)
        for (int i = 0; i + (1 << k) <= n; i++)
            st[k][i] = max(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
    while (m--) {
        int l, r;
        cin >> l >> r;
        --l;
        --r;
        int k = lg[r - l + 1];
        cout << max(st[k][l], st[k][r - (1 << k) + 1]) << '\n';
    }
}