自己手写代码：

#include <bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,l,r;
    cin>>n>>m;
    vector<int> a(n+1);
    vector<int> lg2(n+1);
    vector<vector<int>> st(n+1,vector<int>(18));
    for(int i=1;i<=n;i++){
    	cin>>a[i];
    	st[i][0]=a[i];
	}
    //预处理 一张 lg2表
	lg2[1]=0;
	for(int i=2;i<=n;i++){
		//lg2[i]=floor(log2(i));
		lg2[i]=lg2[i>>1]+1;
	}
	//构建稀疏表,st[i][k]表示从下标i开始，长度为2^k的区间最大值
	for(int k=1;k<=18;k++){
		int len=1<<(k-1);//len=长度为2^k的一半 
		for(int i=1;i+(len*2)-1<=n;i++){
			st[i][k]=max(st[i][k-1],st[i+len][k-1]);
		}
	} 
	while(m--){
	  cin>>l>>r;
	  int kk=lg2[r-l+1];
	  int len2=1<<kk;
	  int cnt=max(st[l][kk],st[r-len2+1][kk]);
	  cout<<cnt<<'\n';
	}
	return 0;
}

下面我们重新用更直观的下标方式来说明稀疊表（Sparse Table），约定：

st[i][k] 表示从下标 i 开始、长度为 2ᵏ 的子段在原数组 a 中的最大值。

下标 i 和 k 的顺序与常见的 st[k][i] 颠倒，但含义等价，只是写法更符合“先给位置 i，再给长度 2ᵏ”这一语义。

---

1. 示例数组与问题

假设有一个长度为 16 的数组 a，下标从 1 到 16 （方便演示我们用 1-based）：

下标 ：  1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  16
a[i] ： 10  23   5  17   8  30  14   2  25   13  19   7   16  29   11   6

我们要回答“区间 [3,16] 的最大值是多少？”这种 RMQ（Range Maximum Query）类型问题。

---

2. 预处理：构造 log2 数组

首先，准备一个 log2[len] 数组，使得 log2[x] = ⎣log₂(x)⎦。对 1..16 得到：

len        1  2  3  4  5  6  7  8   9  10 11 12 13 14 15 16
log2[len]  0  1  1  2  2  2  2  3   3   3  3  3  3  3  3  4

• 比如，log2[5] = 2，因为 2²=4 ≤5 < 2³=8；log2[14] = 3，因为 2³=8 ≤14 < 16。

这个表的作用是：当我们要查询一个长度为 len 的区间时，能迅速知道“最大的 k 使得 2ᵏ ≤ len”。

---

3. 预处理：构建稀疏表 st[i][k]

我们按照以下方式填表：

• 层 k = 0（长度 2⁰ = 1） 对应 st[i][0] = a[i] 本身，表示“从 i 开始、长度 1 的子段最大值就是 a[i]”。

  具体：

  st[1][0] = a[1] = 10
  st[2][0] = a[2] = 23
  ...
  st[16][0] = a[16] = 6
  

• 层 k ≥ 1（长度 2ᵏ） 利用“长度为 2ᵏ 的子段可以拆为两个长度为 2^(k−1) 的子段拼接”这一事实：

  st[i][k] = max( st[i][k−1], st[i + 2^(k−1)][k−1] )
  

  前提是 i + 2ᵏ − 1 ≤ n，也就是保证这两个子段都在数组范围内。

下面一层层演示构建过程：

层 k = 0（长度 1）

下标 i 从 1 到 16：

st[1][0] = 10
st[2][0] = 23
st[3][0] =  5
st[4][0] = 17
st[5][0] =  8
st[6][0] = 30
st[7][0] = 14
st[8][0] =  2
st[9][0] = 25
st[10][0] = 13
st[11][0] = 19
st[12][0] =  7
st[13][0] = 16
st[14][0] = 29
st[15][0] = 11
st[16][0] =  6

层 k = 1（长度 2）

需要 i + (2¹ − 1) = i + 1 ≤ 16，因此 i 从 1 到 15：

st[i][1] = max( st[i][0], st[i+1][0] ) = max(a[i], a[i+1])

st[1][1]  = max(a[1], a[2]) = max(10, 23) = 23
st[2][1]  = max(a[2], a[3]) = max(23,  5) = 23
st[3][1]  = max(a[3], a[4]) = max( 5, 17) = 17
st[4][1]  = max(a[4], a[5]) = max(17,  8) = 17
st[5][1]  = max(a[5], a[6]) = max( 8, 30) = 30
st[6][1]  = max(a[6], a[7]) = max(30, 14) = 30
st[7][1]  = max(a[7], a[8]) = max(14,  2) = 14
st[8][1]  = max(a[8], a[9]) = max( 2, 25) = 25
st[9][1]  = max(a[9], a[10])= max(25, 13) = 25
st[10][1] = max(a[10],a[11])= max(13,19) = 19
st[11][1] = max(a[11],a[12])= max(19, 7) = 19
st[12][1] = max(a[12],a[13])= max( 7,16) = 16
st[13][1] = max(a[13],a[14])= max(16,29) = 29
st[14][1] = max(a[14],a[15])= max(29,11) = 29
st[15][1] = max(a[15],a[16])= max(11, 6) = 11

层 k = 2（长度 4）

需要 i + (2² − 1) = i + 3 ≤ 16，因此 i 从 1 到 13：

st[i][2] = max( st[i][1], st[i+2][1] ), 这里 2^(2−1) = 2

st[1][2]  = max(st[1][1],  st[3][1])  = max(23, 17) = 23  // 对应 a[1..4]
st[2][2]  = max(st[2][1],  st[4][1])  = max(23, 17) = 23  // a[2..5]
st[3][2]  = max(st[3][1],  st[5][1])  = max(17, 30) = 30  // a[3..6]
st[4][2]  = max(st[4][1],  st[6][1])  = max(17, 30) = 30  // a[4..7]
st[5][2]  = max(st[5][1],  st[7][1])  = max(30, 14) = 30  // a[5..8]
st[6][2]  = max(st[6][1],  st[8][1])  = max(30, 25) = 30  // a[6..9]
st[7][2]  = max(st[7][1],  st[9][1])  = max(14, 25) = 25  // a[7..10]
st[8][2]  = max(st[8][1], st[10][1])  = max(25, 19) = 25  // a[8..11]
st[9][2]  = max(st[9][1], st[11][1])  = max(25, 19) = 25  // a[9..12]
st[10][2] = max(st[10][1],st[12][1])  = max(19, 16) = 19  // a[10..13]
st[11][2] = max(st[11][1],st[13][1])  = max(19, 29) = 29  // a[11..14]
st[12][2] = max(st[12][1],st[14][1])  = max(16, 29) = 29  // a[12..15]
st[13][2] = max(st[13][1],st[15][1])  = max(29, 11) = 29  // a[13..16]

层 k = 3（长度 8）

需要 i + (2³ − 1) = i + 7 ≤ 16，因此 i 从 1 到 9：

st[i][3] = max( st[i][2], st[i+4][2] ), 这里 2^(3−1) = 4

st[1][3] = max(st[1][2],  st[5][2]) = max(23, 30) = 30  // a[1..8]
st[2][3] = max(st[2][2],  st[6][2]) = max(23, 30) = 30  // a[2..9]
st[3][3] = max(st[3][2],  st[7][2]) = max(30, 25) = 30  // a[3..10]
st[4][3] = max(st[4][2],  st[8][2]) = max(30, 25) = 30  // a[4..11]
st[5][3] = max(st[5][2],  st[9][2]) = max(30, 25) = 30  // a[5..12]
st[6][3] = max(st[6][2], st[10][2]) = max(30, 19) = 30  // a[6..13]
st[7][3] = max(st[7][2], st[11][2]) = max(25, 29) = 29  // a[7..14]
st[8][3] = max(st[8][2], st[12][2]) = max(25, 29) = 29  // a[8..15]
st[9][3] = max(st[9][2], st[13][2]) = max(25, 29) = 29  // a[9..16]

层 k = 4（长度 16）

需要 i + (2⁴ − 1) = i + 15 ≤ 16，因此 i 只有 1：

st[1][4] = max(st[1][3], st[1+8][3]) = max(30, 29) = 30  // a[1..16]

---

4. 查询区间 [3,16] 的最大值

我们要查询的范围是下标 L = 3 到 R = 16，总长度是 len = 16 − 3 + 1 = 14。

第一步：计算 len = R − L + 1 = 14。

第二步：找到 k = floor(log2(len))

len = 14 → log2[14] = 3  （因为 2³ = 8 ≤ 14 < 16 = 2⁴）

所以 k = 3，对应区间长度 = 2³ = 8。

第三步：将 [3,16] 用两个长度为 8 的子区间覆盖

• 第一个子区间从 L = 3 开始，长度 8 → 覆盖 [3, 3+8−1] = [3,10]。
• 第二个子区间从 R−2ᵏ+1 = 16−8+1 = 9 开始，长度 8 → 覆盖 [9,16]。

这两段 [3,10] 与 [9,16] 合起来“刚好”覆盖整个 [3,16]（中间 [9,10] 会重叠两次，但不会影响最终最大值计算）。

第四步：直接从稀疏表取值

• st[3][3] 就是“从 i=3 开始、长度 2³=8 的子段最大值” → 对应 a[3..10]。 查表我们得到：

  st[3][3] = 30
  

  （这等价于 max(a[3],a[4],…,a[10])）

• st[9][3] 就是“从 i=9 开始、长度 8 的子段最大值” → 对应 a[9..16]。 查表我们得到：

  st[9][3] = 29
  

  （这等价于 max(a[9],a[10],…,a[16])）

这两个值分别覆盖 [3,10] 与 [9,16] 两个子区间。它们的最大值就是整个 [3,16] 的最大值：

ans = max( st[3][3], st[9][3] ) = max(30, 29) = 30.

所以，区间 [3,16] 的最大值是 30。

---

5. 代码思路总结

下面给出完整示例代码框架（C++），其中 st[i][k] 即为上述定义，且支持 O(1) 的查询：

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

const int MAXN = 200000 + 5;
int N;                   // 数组长度
int log2_[MAXN];         // log2[len]

int st[MAXN][20];        // st[i][k]：从 i 开始、长度 2^k 的子段最大值（1-based）

void precompute_log2(int n) {
    log2_[1] = 0;
    for (int i = 2; i <= n; i++) {
        log2_[i] = log2_[i / 2] + 1;
    }
}

void buildSparseTable(int a[], int n) {
    // 层 k = 0：长度 1
    for (int i = 1; i <= n; i++) {
        st[i][0] = a[i];
    }
    // 对 k = 1..floor(log2(n)) 逐层构造
    for (int k = 1; (1 << k) <= n; k++) {
        int len = 1 << (k - 1);  // 上一层 (k-1) 对应长度 2^(k-1)
        for (int i = 1; i + (1 << k) - 1 <= n; i++) {
            // st[i][k] = max( st[i][k-1], st[i + 2^(k-1)][k-1] )
            st[i][k] = max(st[i][k - 1], st[i + len][k - 1]);
        }
    }
}

// 区间查询 [L,R] 的最大值，1-based，下标都在 1..N 范围内
int query_max(int L, int R) {
    int len = R - L + 1;
    int k = log2_[len];            // 找到最大的 k 使得 2^k <= len
    int segLen = 1 << k;           // segLen = 2^k
    // 两个子区间：[L, L+2^k-1] 以及 [R-2^k+1, R]
    int v1 = st[L][k];
    int v2 = st[R - segLen + 1][k];
    return max(v1, v2);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 读入 N, 数组 a[1..N]
    cin >> N;
    static int a[MAXN];
    for (int i = 1; i <= N; i++) {
        cin >> a[i];
    }

    // 预处理 log2 数组
    precompute_log2(N);

    // 构建 st[i][k]
    buildSparseTable(a, N);

    // 比如我们要查询 [L,R] 区间的最大值：
    // int L = 3, R = 16;
    // int ans = query_max(L, R);

    // ... 其余业务逻辑 ...

    return 0;
}

---

6. 关键要点回顾

1. 稀疏表定义（本例用 st[i][k]）： st[i][k] = max(a[i], a[i+1], …, a[i + 2ᵏ − 1]) (当 i + 2ᵏ − 1 ≤ N 时，该子段才有效)

2. 递推关系（从长度 2^(k−1) 推到长度 2ᵏ）：

   st[i][k] = max( st[i][k−1], st[i + 2^(k−1)][k−1] );
   

   • 这表示：长度为 2ᵏ 的子段可以拆成两个长度为 2^(k−1) 的子段拼接。

3. 查询区间 [L,R]：

   • 区间长度 = len = R − L + 1。

   • 寻找最大的 k = ⎣log₂(len)⎦，对应子段长度 segLen = 2ᵏ ≤ len。

   • 用两个覆盖子段：[L, L+segLen−1] 和 [R−segLen+1, R]，直接取它们的最大值：

     ans = max( st[L][k], st[R − (1<<k) + 1][k] );
     

   • 因为这两个长度为 segLen 的子段恰好覆盖整个 [L,R]，它们重叠部分不影响最大值结果。

4. 复杂度：

   • 预处理建表：O(N log N)。
   • 每次 RMQ 查询：O(1)。

---

如此，借助 st[i][k] 的定义和查询方式，就能够在静态数组上以 O(1) 时间回答任意区间的最大值（或最小值）。