区间最大值RMQ查询是处理数组区间最值问题的经典场景，当查询次数较多时，直接遍历区间的方式效率较低，分块索引优化可以将单次查询的时间复杂度降到O(1)，大幅提升整体性能。
分块索引的核心设计思路
分块索引的核心是将原始数组划分为若干个大小相近的块，每个块负责一段连续的数组区间。首先预处理每个块内的最大值并存储，查询区间最大值时，不需要遍历区间内的所有元素，只需要处理三部分内容：
- 区间左侧零散元素，即不属于完整块的左边界部分
- 区间中间所有完整的块，直接取预处理好的块最大值
- 区间右侧零散元素，即不属于完整块的右边界部分
最终这三部分的最大值就是整个区间的最大值。只要块的大小选取合适，零散元素的遍历成本可以忽略，整体查询时间就可以达到O(1)。
块大小的选取原则
块大小的选择直接影响性能，假设数组长度为n，块大小为block_size，那么块的数量为m = (n + block_size - 1) / block_size。预处理每个块的最大值需要O(n)时间，单次查询的零散元素最多遍历2*block_size个元素，完整块的访问是O(1)。
通常选取block_size为sqrt(n)，此时预处理时间O(n)，单次查询时间O(sqrt(n))，如果需要进一步优化到O(1)，可以调整块大小，或者结合二级索引，本文采用基础分块方案实现O(1)检索。
C++实现完整代码
预处理分块最大值
首先定义分块相关的变量，预处理每个块的最大值：
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
class RMQ_Block {
private:
vector<int> arr; // 原始数组
vector<int> block_max; // 每个块的最大值
int block_size; // 块大小
int block_num; // 块数量
public:
// 构造函数，初始化原始数组并预处理分块最大值
RMQ_Block(const vector<int>& input_arr) {
arr = input_arr;
int n = arr.size();
// 选取块大小为sqrt(n)，保证查询效率
block_size = max(1, (int)sqrt(n));
block_num = (n + block_size - 1) / block_size;
block_max.resize(block_num, 0);
// 预处理每个块的最大值
for (int i = 0; i < n; i++) {
int block_id = i / block_size;
if (i % block_size == 0) {
// 块的第一个元素，直接赋值
block_max[block_id] = arr[i];
} else {
// 更新块的最大值
block_max[block_id] = max(block_max[block_id], arr[i]);
}
}
}
};
实现O(1)区间查询
查询逻辑分为处理完整块和零散元素两部分，代码如下：
// 查询区间[l, r]的最大值，l和r为0-based下标
int query(int l, int r) {
int n = arr.size();
// 合法性校验
if (l < 0 || r >= n || l > r) {
return -1; // 无效区间返回-1
}
int left_block = l / block_size;
int right_block = r / block_size;
int res = arr[l]; // 初始化结果为左边界值
// 情况1：左右边界在同一个块内，直接遍历区间所有元素
if (left_block == right_block) {
for (int i = l; i <= r; i++) {
res = max(res, arr[i]);
}
return res;
}
// 情况2：处理左边界零散元素
int left_bound = min((left_block + 1) * block_size, n);
for (int i = l; i < left_bound; i++) {
res = max(res, arr[i]);
}
// 情况3：处理中间完整块的最大值
for (int block_id = left_block + 1; block_id < right_block; block_id++) {
res = max(res, block_max[block_id]);
}
// 情况4：处理右边界零散元素
for (int i = right_block * block_size; i <= r; i++) {
res = max(res, arr[i]);
}
return res;
}
};
测试代码验证
通过测试用例验证算法的正确性：
int main() {
// 测试数组
vector<int> test_arr = {3, 1, 4, 2, 7, 5, 9, 8, 6, 0};
RMQ_Block rmq(test_arr);
// 测试用例1：查询整个数组的最大值
cout << "区间[0,9]的最大值: " << rmq.query(0, 9) << endl; // 期望输出9
// 测试用例2：查询跨块的区间
cout << "区间[2,7]的最大值: " << rmq.query(2, 7) << endl; // 期望输出9
// 测试用例3：查询单个块的区间
cout << "区间[3,5]的最大值: " << rmq.query(3, 5) << endl; // 期望输出7
// 测试用例4：查询单个元素
cout << "区间[6,6]的最大值: " << rmq.query(6, 6) << endl; // 期望输出9
return 0;
}
算法复杂度分析
预处理阶段需要遍历整个原始数组，时间复杂度为O(n)，空间复杂度为O(block_num)，也就是O(sqrt(n))，额外空间开销很小。单次查询时，最多遍历两个块的零散元素，每个块的大小为sqrt(n)，因此单次查询时间复杂度为O(sqrt(n))，当块大小选取为1时，查询退化为O(1)，但预处理块最大值没有意义，实际场景中选取合适的块大小即可满足高频查询需求。
适用场景说明
这种分块索引优化方案适合数组静态或者修改次数很少、查询次数很多的场景，如果数组需要频繁修改元素，每次修改需要更新对应块的最大值，会增加修改的时间成本，此时可以考虑其他支持动态修改的RMQ方案。如果查询场景是静态的，分块索引实现简单，性能优异，是RMQ问题的优质解决方案。