每日算法 — 使用java实现RMQ：ST表预处理与O(1)区间最值查询

一、问题引入

RMQ（Range Minimum/Maximum Query，区间最值查询） 是算法竞赛和实际工程中极为常见的问题：给定一个长度为N的数组，回答多个询问——某个子区间的最大值或最小值是多少？

如果每次查询都遍历区间，时间复杂度为O(N) per query。当查询次数Q很大时，总复杂度将达到O(NQ)，效率极低。本文介绍的ST表（Sparse Table，稀疏表） 可以在O(N log N)的预处理之后，实现O(1)的查询效率。

二、算法原理

2.1 核心思想：倍增与重叠区间

ST表的核心是倍增思想：
– st[i][j] 表示从位置i开始、长度为2^j的区间的最值
– 长度为2^j的区间可以由两个长度为2^(j-1)的区间拼接而成

递推公式：

st[i][j] = max(st[i][j-1], st[i + 2^(j-1)][j-1])

2.2 为什么可以O(1)查询？

对于查询区间[l, r]，设长度len = r – l + 1。取k = log2(len)。

关键在于：区间[l, r]可以被两个长度为2^k的区间完全覆盖（允许重叠）：
– 第一个区间从l开始，长度为2^k
– 第二个区间从r-2^k+1开始，长度为2^k

由于最值查询具有重叠友好性（重叠不影响结果），所以答案是这两个区间最值的最大值。

三、Java代码实现

import java.util.*;

/**
 * RMQ区间最值查询 - ST表实现
 * 支持O(N log N)预处理和O(1)查询
 */
public class RMQ {

    private int[][] stMin;    // 最小值ST表
    private int[][] stMax;    // 最大值ST表
    private int[] logTable;   // 预处理log2值
    private int n;

    /**
     * 初始化ST表
     * 时间复杂度：O(N log N)
     *
     * @param arr 输入数组
     */
    public RMQ(int[] arr) {
        this.n = arr.length;
        int maxLog = 32 - Integer.numberOfLeadingZeros(n); // log2(n)向上取整

        // 预处理log2表
        logTable = new int[n + 1];
        logTable[1] = 0;
        for (int i = 2; i <= n; i++) {
            logTable[i] = logTable[i / 2] + 1;
        }

        // 初始化ST表
        stMin = new int[n][maxLog];
        stMax = new int[n][maxLog];

        // 第一层：长度为1的区间
        for (int i = 0; i < n; i++) {
            stMin[i][0] = arr[i];
            stMax[i][0] = arr[i];
        }

        // 倍增构建ST表
        for (int j = 1; j < maxLog; j++) {
            for (int i = 0; i + (1 << j) <= n; i++) {
                // 最小值ST表
                stMin[i][j] = Math.min(
                    stMin[i][j - 1],
                    stMin[i + (1 << (j - 1))][j - 1]
                );
                // 最大值ST表
                stMax[i][j] = Math.max(
                    stMax[i][j - 1],
                    stMax[i + (1 << (j - 1))][j - 1]
                );
            }
        }
    }

    /**
     * 查询区间[l, r]的最小值
     * 时间复杂度：O(1)
     *
     * @param l 左边界（0-based，包含）
     * @param r 右边界（0-based，包含）
     * @return 区间最小值
     */
    public int queryMin(int l, int r) {
        if (l > r) {
            throw new IllegalArgumentException("l should not be greater than r");
        }
        int len = r - l + 1;
        int k = logTable[len];
        return Math.min(
            stMin[l][k],
            stMin[r - (1 << k) + 1][k]
        );
    }

    /**
     * 查询区间[l, r]的最大值
     * 时间复杂度：O(1)
     *
     * @param l 左边界（0-based，包含）
     * @param r 右边界（0-based，包含）
     * @return 区间最大值
     */
    public int queryMax(int l, int r) {
        if (l > r) {
            throw new IllegalArgumentException("l should not be greater than r");
        }
        int len = r - l + 1;
        int k = logTable[len];
        return Math.max(
            stMax[l][k],
            stMax[r - (1 << k) + 1][k]
        );
    }

    /**
     * 查询区间[l, r]的最小值和最大值
     */
    public int[] queryMinMax(int l, int r) {
        return new int[]{queryMin(l, r), queryMax(l, r)};
    }

    /**
     * 批量查询接口
     * @param queries 查询数组，每个元素为[l, r]
     * @return 每个查询的最小值和最大值
     */
    public List<int[]> batchQuery(int[][] queries) {
        List<int[]> results = new ArrayList<>();
        for (int[] q : queries) {
            results.add(queryMinMax(q[0], q[1]));
        }
        return results;
    }

    /**
     * 打印ST表（调试用）
     */
    public void printSTTable() {
        System.out.println("=== 最小值ST表 ===");
        for (int j = 0; j < stMin[0].length && (1 << j) <= n; j++) {
            System.out.print("长度2^" + j + ": ");
            for (int i = 0; i + (1 << j) <= n; i++) {
                System.out.print(stMin[i][j] + " ");
            }
            System.out.println();
        }
    }

    /**
     * 静态方法：快速计算log2
     */
    public static int log2(int x) {
        return 31 - Integer.numberOfLeadingZeros(x);
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 1, 9, 3, 7, 4, 6, 10};

        System.out.println("原始数组: " + Arrays.toString(arr));
        System.out.println();

        RMQ rmq = new RMQ(arr);
        rmq.printSTTable();

        // 单次查询测试
        System.out.println("\n=== 单次查询 ===");
        int[][] testQueries = {
            {0, 9},  // 整个数组
            {0, 4},  // 前5个
            {5, 9},  // 后5个
            {2, 6},  // 中间5个
            {3, 3},  // 单个元素
        };

        for (int[] q : testQueries) {
            int[] result = rmq.queryMinMax(q[0], q[1]);
            System.out.printf("区间[%d, %d]: 最小值=%d, 最大值=%d%n",
                q[0], q[1], result[0], result[1]);
        }

        // 批量查询测试
        System.out.println("\n=== 批量查询 ===");
        List<int[]> batchResults = rmq.batchQuery(testQueries);
        for (int i = 0; i < testQueries.length; i++) {
            System.out.printf("查询%d: 最小值=%d, 最大值=%d%n",
                i + 1, batchResults.get(i)[0], batchResults.get(i)[1]);
        }

        // 性能对比
        System.out.println("\n=== 性能测试（100万次查询）===");
        int[] largeArr = new int[100000];
        Random rand = new Random(42);
        for (int i = 0; i < largeArr.length; i++) {
            largeArr[i] = rand.nextInt(1000000);
        }

        RMQ largeRMQ = new RMQ(largeArr);

        long start = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            int l = rand.nextInt(largeArr.length);
            int r = l + rand.nextInt(largeArr.length - l);
            largeRMQ.queryMin(l, r);
        }
        long end = System.currentTimeMillis();
        System.out.println("ST表查询100万次耗时: " + (end - start) + "ms");
    }
}

四、复杂度分析

五、ST表的局限与替代方案

ST表虽然查询极快，但它不支持修改操作。如果需要支持动态更新，可以考虑：
– 线段树：O(N)建树，O(log N)查询和修改
– 树状数组：适用于前缀查询场景
– 分块（Sqrt Decomposition）：平衡了修改和查询的效率

六、总结

ST表是静态区间查询问题的经典解法，它将倍增思想和区间重叠覆盖巧妙结合，实现了理论最优的查询复杂度。学习ST表不仅能掌握这一具体数据结构，更能深入理解倍增这一在算法设计中无处不在的核心思想——从二进制提升到LCA查询，从快速幂到RMQ，倍增思想贯穿始终。