【稀疏表】Static Range Minimum Queries

题目描述

给定一个包含 n 个整数的数组，你的任务是处理 q 个查询，每个查询的形式为：计算区间 [a, b] 内所有数值的最小值是多少？

 

输入

第一行输入两个整数 n 和 q：分别表示数值的数量和查询的数量。
第二行包含 n 个整数 x₁, x₂, ..., xₙ：即数组的元素。
接下来有 q 行，每行描述一个查询，包含两个整数 a 和 b：表示需要计算区间 [a, b] 内的数值最小值。

 

约束条件

1 ≤ n, q ≤ 2×10⁵
1 ≤ xᵢ ≤ 10⁹
1 ≤ a ≤ b ≤ n

 

输出

输出每个查询的结果

样例输入

复制

8 4
3 2 4 5 1 1 5 3
2 4
5 6
1 8
3 3

样例输出

复制

2
1
1
4

要解决这个区间最小值查询问题，我们需要一种高效的方法来处理大量查询。由于数据规模较大（n 和 q 都可能达到 2×10⁵），使用朴素的 O (n) 查询方法会超时，因此我们可以采用线段树或稀疏表等数据结构。

稀疏表的核心思想是：

1. 预处理出所有区间长度为 2^k 的区间最小值

2. 对于任意查询区间 [a,b]，找到最大的 k 使得 2^k ≤ 区间长度

3. 用两个长度为 2^k 的区间覆盖 [a,b]，取这两个区间的最小值

预处理：构建稀疏表

我们用一个二维数组 st[k][i] 来存储预处理结果，其中：

• k 表示 “区间长度为 2^k”（如 k=0 对应长度 1，k=1 对应长度 2，k=2 对应长度 4）。

• i 表示 “区间的起始位置”。

因此，st[k][i] 的含义是：从位置 i 开始，长度为 2^k 的区间（即 [i, i+2^k-1]）的最小值。

预处理步骤：

• 基础情况（k=0）：区间长度为 2^0=1，此时 st[0][i] 就是数组中第 i 个元素本身（因为单个元素的最小值就是自己）。

• 递推计算（k>0）：对于更长的区间（2^k），可以拆成两个长度为 2^(k-1) 的区间

查询：覆盖区间求结果

对于任意查询区间 [a, b]（0-based 索引）：

• 计算区间长度：len = b - a + 1。

• 找最大的 k：使得 2^k ≤ len（即 k = log2(len)，向下取整）。

• 用两个区间覆盖：

  • 第一个区间：从 a 开始，长度 2^k，即 [a, a+2^k-1]，对应 st[k][a]。

  • 第二个区间：以 b 结束，长度 2^k，即 [b-2^k+1, b]，对应 st[k][b-2^k+1]。

• 结果：这两个区间的最小值，即 min(st[k][a], st[k][b-2^k+1])。

为什么这样可行？因为 2^k 是不超过 len 的最大幂次，所以两个长度为 2^k 的区间一定能完全覆盖 [a, b]（重叠部分不影响结果）。

查询的时间复杂度是 O(1)，因为只需一次计算和两次取值。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;

int n,q,x[N];
vector<int>l(N,INT_MAX),r(N,INT_MAX);

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>q;
	for(int i=1;i<=n;++i)cin>>x[i];
	
	int up=log2(n)+1;
	vector<vector<int>>book(up,vector<int>(n+1));
	
	for(int i=1;i<=n;++i)book[0][i]=x[i];
	
	for(int k=1;k<up;++k)
		for(int i=1;i+(1<<k)-1<=n;++i)
			book[k][i]=min(book[k-1][i],book[k-1][i+(1<<(k-1))]);
			
	while(q--)
	{
		int a,b;
		cin>>a>>b;
		int k=log2(b-a+1);
		cout<<min(book[k][a],book[k][b-(1<<(k))+1])<<'\n';
	}	
		
	return 0;
}

举个具体例子：
假设我们要计算长度为 4（2²）的区间 [1,4] 的最小值（1-based 索引），按照稀疏表的逻辑：

• 这个长区间可以拆成两个长度为 2（2¹）的短区间：
  1. 左区间：[1,2]（从起点 1 开始，长度 2）
  2. 右区间：[3,4]（紧接着左区间，长度也是 2）

这两个区间合起来刚好覆盖整个长区间 [1,4]，没有重叠也没有空隙。

长区间的最小值 = 左区间的最小值 和 右区间的最小值 中更小的那个。

这里的 “左” 和 “右” 只是相对位置：左区间在左边，右区间在右边，两者拼接后就是完整的长区间。

所以预处理时，我们只需要用左区间的结果（st[k-1][i]）和右区间的结果（st[k-1][i + 2^(k-1)]），就能算出长区间的结果，不需要额外减 1，因为右区间的起点刚好是左区间终点的下一个位置，天然衔接。