1305: 老管家的忠诚(ST表）

解题思路:

ST 表原理：利用动态规划预处理出所有长度为2^j的区间最小值，查询时通过两个覆盖目标区间的预处理区间的最小值得到结果，实现O(1)查询。

预处理：时间复杂度O(n log n)，通过递推关系将长区间拆分为两个短区间的组合。

查询优化：通过计算区间长度的对数k，确保两个长度为2^k的区间能完整覆盖查询区间[l, r]，从而快速得到最小值。

注意事项:

参考代码:

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;  // 数组最大长度，根据题目需求设置
int n, m;  // n: 元素个数；m: 查询次数
int f[N][20];  // ST表核心数组，f[i][j]表示从i开始，长度为2^j的区间的最小值
int l, r;  // 每次查询的区间左右端点

int main()
{
    cin >> n >> m;  // 输入元素个数和查询次数
    
    // 初始化ST表的第0层（区间长度为2^0=1，即单个元素）
    for(int i = 1; i <= n; ++ i){
        cin >> f[i][0];  // f[i][0]就是元素a[i]本身
    }
    
    // 计算最大需要预处理的幂次（确保覆盖所有可能的区间长度）
    int max_k = log2(n);  // 2^max_k 不超过n的最大k值
    
    // 预处理ST表：从短区间向长区间扩展（动态规划思想）
    // j表示区间长度为2^j，从1开始递增（j=1对应长度2，j=2对应长度4，以此类推）
    for(int j = 1; j <= max_k + 1; ++ j){
        // i表示区间起点，需保证[i, i + 2^j - 1]不超出数组范围
        for(int i = 1; i + (1 << j) - 1 <= n; ++ i){
            // 状态转移：长度为2^j的区间最小值 = 两个长度为2^(j-1)的子区间最小值的较小值
            // 第一个子区间：[i, i + 2^(j-1) - 1]
            // 第二个子区间：[i + 2^(j-1), i + 2^j - 1]
            f[i][j] = min(f[i][j-1], f[i + (1 << (j-1))][j-1]);
        }        
    }
    
    // 处理m次区间最小值查询
    while(m --){
        scanf("%d %d", &l ,&r);  // 输入查询区间[l, r]（1-based）
        int len = r - l + 1;  // 计算区间长度
        int k = log2(len);  // 找到最大的k，使得2^k <= len（保证两个子区间能覆盖整个查询区间）
        // 查询结果：两个覆盖区间的最小值
        // 第一个区间：[l, l + 2^k - 1]
        // 第二个区间：[r - 2^k + 1, r]
        printf("%d ", min(f[l][k], f[r - (1 << k) + 1][k]));
    }
    
    return 0;
}