RMQ(range minimum/maxmum query)问题：是指对于数组，每次给一个区间[l,r]，要求返回区间内的最大值或者最小值（的下标）------->就是区间最值问题！
         对于这种问题，很容易想到时间复杂度为o(n)的暴力枚举，就是直接遍历[l,r]区间，
 不断比较a[i]a与max的大小关系，然后不断更新maax，最后求得的就是最大值
         但是数据多了就会超时！！！！
         于是，可以利用 倍增和动态规划的思想，利用“st表”这个数据结构来帮助解决

         st表（稀疏表（Sparse Table））：是一种可以“静态求区间最值”，本质上是一种dp。
         假设我们要求区间最大值（最小值类似），设状态st[i][j]表示从i开始，大小为2^j(2的j次方)
 的长度区间的最大值，即区间[i,i+2^j-1]的最大值
 状态转移方程为：st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]); 
 i+1<<k==i+2^k  !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
 就是分成了两个区间：[i,i+2^j-1]----->[i,i+2^(j-1)-1],[i+2^(j-1),i+2^j-1]
 注意状态转移的方向和区间的合法！
 区间查询：
 为了查询[l,r]的最大值，它可以分解成为2个小区间的最大值，例如要求[2,7]的最大值，
 可以分解为：[2,2+2^2-1],[7-2^2+1,7]的最大值（两个区间长度均为4，为2的次方）
 也就是max(st[2][2],st[7-4+1][2])
 拓展：需要找出一个k，使得2^k<=r-l+1,即k=log2(r-1+1!),可以分解为
 max(st[l][k],st[r-2^k+1][k])就是分解为两个长度相同的并且为2的次方长度的区间！！！

例题：蓝桥杯官网：区间最大值

给定一个长度为 N 的数组 a，其值分别为 a1,a2,...,aN。现有 Q个询问，每个询问包含一个区间，请回答该区间的最大值为多少。

代码如下，附有详细解释以及注意事项和原理：

#include <iostream>
#include<cmath>
using namespace std;
const int N = 5e5 + 9;
int a[N], st[N][21];

int getmax(int l, int r)//用来计算想要区间的最大值
{
    //要将区间[l,r]均分为两个区间长度为2^k的区间
    //需满足：2^k<=r-l+1，即k<=log2(r-l+1)。
    //查询区间[l, r] 时，需要用两个长度为 2 ^ k 的区间覆盖它：
    //一个区间接在l，另一个区间接在r
    //相当于：1 2 3 4 5 6  
    //        |-----|
    //            |-----|
    int k = log(r - l + 1) / log(2);//以浮点形式运算，并向下取整,记得log加括号！
    return max(st[l][k], st[r - (1 << k) + 1][k]);
}


int main()
{
    int n, q; cin >> n >> q;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    //初始化
    for (int i = 1; i <= n; i++)
    {
        st[i][0] = a[i];
    }
    //逐个计算st数组
    //注意枚举方向和大小
    /*在稀疏表（Sparse Table）的构建中，循环顺序必须是先枚举 j（区间长度的指数），再枚举 i（区间起点），
    而不能反过来先枚举 i 再枚举 j。这是由稀疏表的动态规划依赖关系决定的*/
    //为什么不能先枚举 i 再枚举 j？
    //若先枚举i再枚举j：
    //会导致 递推依赖的子问题未被计算：
    //    计算 st[i][j] 时，需要用到 st[i][j - 1] 和 st[i + (1 << (j - 1))][j - 1]（即 j - 1 层的结果）。
    //    如果先固定 i，再从小到大枚举 j，对于某些 i + (1 << (j - 1))（另一个子区间的起点），
    //    其 j - 1 层的结果可能还未计算（因为 i 是按顺序遍历的，而 i + (1 << (j - 1)) 可能比当前 i 大，还没轮到它的 j - 1 层计算）。

    //总结（非常重要！！！）
    //稀疏表的构建依赖 “短区间结果推导长区间结果” 的逻辑，必须先完成所有短区间（j - 1 层）的计算，才能开始计算长区间（j 层）。
    //因此，循环顺序必须是 先 j 后 i，否则会因依赖未就绪而导致计算错误。
    for (int j = 1; j <= 20; j++)
    {
        for (int i = 1; i <= n; i++)
        {
            //判断区间合法[i,i+(1<<j)-1]
            if (i + (1 << j) - 1 <= n)
            {
                //就是将原本长度为2^j的区间分为两个长度均为2^(j-1)的区间！！！
                st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
            }
        }
    }
    while (q--)
    {
        int l, r; cin >> l >> r;
        cout << getmax(l, r) << '\n';
    }
    return 0;
}