设计支持O(1)时间复杂度的区间最大值查询数据结构

这是经典的静态区间最值查询（RMQ, Range Maximum Query）问题，最适配的解法就是稀疏表（Sparse Table）——完全满足你的需求：初始化仅需O(n log n)时间，每次区间最大值查询严格做到O(1)，而且实现起来门槛不高。

核心原理 #

稀疏表的核心思路是预处理所有长度为2的幂次的区间最大值，这样查询任意区间时，我们可以用两个长度为2^k的区间（它们的并集刚好覆盖目标区间）的最大值来推导结果，避免了每次查询都遍历区间。

预处理步骤 #

1. 先确定数组长度n，计算最大的幂次k_max：k_max = floor(log2(n))（比如n=8时，k_max=3，因为2^3=8）
2. 创建二维数组st，其中st[k][i]代表从索引i开始，长度为2^k的区间的最大值
3. 初始化基础层（k=0）：st[0][i] = A[i]，因为长度为1的区间最大值就是元素本身
4. 逐层填充稀疏表：
   • 对于每个k从1到k_max，遍历每个合法的起始索引i（保证i + 2^k -1 < n）
   • st[k][i] = max(st[k-1][i], st[k-1][i + 2^(k-1)])——把两个相邻的、长度为2^(k-1)的区间最大值合并

查询步骤 #

给定目标区间[i, j]（确保i ≤ j）：

1. 计算区间长度len = j - i + 1
2. 找到最大的k满足2^k ≤ len，即k = floor(log2(len))
3. 结果为max(st[k][i], st[k][j - 2^k + 1])——这两个区间的并集刚好覆盖[i,j]，取它们的最大值就是整个区间的最大值

代码示例（Python） #

import math

class SparseTable:
    def __init__(self, arr):
        self.n = len(arr)
        if self.n == 0:
            self.k_max = 0
            self.st = []
            return
        self.k_max = math.floor(math.log2(self.n))
        # 初始化稀疏表结构
        self.st = [[0] * self.n for _ in range(self.k_max + 1)]
        
        # 填充k=0的基础层
        for idx in range(self.n):
            self.st[0][idx] = arr[idx]
        
        # 逐层填充更高阶的区间最大值
        for k in range(1, self.k_max + 1):
            # 每个k对应的区间起始索引范围：i + 2^k -1 < n → i ≤ n - 2^k
            for i in range(self.n - (1 << k) + 1):
                prev_k = k - 1
                self.st[k][i] = max(
                    self.st[prev_k][i],
                    self.st[prev_k][i + (1 << prev_k)]
                )
    
    def query_max(self, i, j):
        # 处理非法输入
        if i < 0 or j >= self.n or i > j:
            raise ValueError("Invalid interval indices")
        length = j - i + 1
        k = math.floor(math.log2(length))
        # 计算第二个区间的起始索引
        second_start = j - (1 << k) + 1
        return max(self.st[k][i], self.st[k][second_start])

# 测试用例
if __name__ == "__main__":
    test_arr = [3, 1, 4, 1, 5, 9, 2, 6]
    st = SparseTable(test_arr)
    print(st.query_max(2, 5))  # 输出9，对应区间[4,1,5,9]的最大值
    print(st.query_max(0, 7))  # 输出9，整个数组的最大值

补充说明 #

• 稀疏表仅适用于静态数组（元素不会被修改），如果需要支持动态更新元素，那得换成线段树（查询和更新都是O(log n)时间），但题目里没提修改需求，所以稀疏表是最优选择。
• 预处理的时间复杂度是O(n log n)，因为k_max是log2(n)级别，每个k对应的循环是O(n)次。
• 查询时间是严格的O(1)，只需要两次数组取值和一次最大值计算，没有循环或递归。

内容的提问来源于stack exchange，提问作者Barak B