第63章 倍增法

long long fastPower (long long a, long long n, long long m) {
    long long result=1;
    a %= m;
    while (n>0){
        if(n & 1){
            result = (result * a) % m;
        }
        a = (a * a) % m;
        n >>= 1;
    }
    return result;
}

## 63.3 真题示例（ST 表：区间最值 RMQ）

> **【GESP 八级风格·编程题】**
> **题目描述**：给定一个长度为 $$n$$ 的数列，之后有 $$q$$ 次询问，每次询问区间 $$[l, r]$$ 中的最大值。$$n, q \le 10^5$$。
> **输入格式**：第一行 $$n$$；第二行 $$n$$ 个整数；第三行 $$q$$；之后 $$q$$ 行每行 $$l, r$$（下标从 0 开始）。
> **输出格式**：每个询问输出一个最大值。

**思路**：用倍增预处理出"长度为 $$2^j$$ 的区间最值"，查询时把 $$[l,r]$$ 拆成两段已预处理的长度 $$2^k$$ 区间，取 max 即可，单次查询 $$O(1)$$。

```cpp
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

const int MAXN = 100005;
int a[MAXN];
int st[MAXN][20];      // st[i][j] = 区间 [i, i + 2^j - 1] 的最大值
int n;

void build() {
    for (int i = 0; i < n; ++i) st[i][0] = a[i];           // 长度 1 = 本身
    for (int j = 1; (1 << j) <= n; ++j)                    // 长度 2^j
        for (int i = 0; i + (1 << j) - 1 < n; ++i)
            st[i][j] = max(st[i][j - 1],
                           st[i + (1 << (j - 1))][j - 1]); // 左右两半合并
}

int query(int l, int r) {
    int k = (int)log2(r - l + 1);                          // 最大的 2^k ≤ 区间长度
    return max(st[l][k], st[r - (1 << k) + 1][k]);          // 两段覆盖整个区间
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> a[i];
    build();
    int q; cin >> q;
    while (q--) {
        int l, r; cin >> l >> r;
        cout << query(l, r) << "\n";
    }
    return 0;
}