每日算法 — 使用java实现ST表：静态区间最值查询的O(1)解法

引言

在算法竞赛和实际工程中，区间最值查询（Range Minimum/Maximum Query，RMQ）是一类非常常见的问题：给定一个静态数组，回答大量形如”区间[l, r]中的最大值/最小值是多少”的查询。线段树可以在O(n)预处理后每次查询O(log n)，而ST表（Sparse Table，稀疏表）则通过巧妙的倍增预处理，将查询时间进一步优化到O(1)，在数组不发生修改的场景下成为最优选择。

核心原理

倍增思想

ST表的核心是倍增法：预先计算所有长度为2^k的区间的最值。

定义st[i][k]表示从位置i开始、长度为2^k的区间的最值：

st[i][k] = max/min( st[i][k-1], st[i + 2^(k-1)][k-1] )

即将一个长度为2^k的区间拆成两个长度为2^(k-1)的区间，取二者的最值。

O(1)查询的关键

对于查询区间[l, r]，其长度为len = r - l + 1。找到最大的k使得2^k ≤ len。

关键观察：两个长度为2^k的区间可以覆盖[l, r]，即使它们有重叠也不影响最值结果：

query(l, r) = max/min( st[l][k], st[r - 2^k + 1][k] )

• 第一个区间从l开始，向右2^k个元素
• 第二个区间从r - 2^k + 1开始，向右2^k个元素
• 两个区间的并集恰好覆盖[l, r]（允许重叠）

Java实现

/**
 * ST表（Sparse Table）实现
 * 静态区间最值查询：O(n log n)预处理，O(1)查询
 * 适用于数组不发生变化、查询量大的场景
 */
public class SparseTable {

    private int n;                    // 数组长度
    private int[][] st;               // ST表，st[i][k]表示从i开始长度为2^k的区间最值
    private int[] logTable;           // 预计算对数，logTable[i] = floor(log2(i))
    private boolean isMax;            // true表示查询最大值，false表示最小值

    /**
     * 构造函数
     * @param arr 原始数组（不会发生修改）
     * @param isMax true查询最大值，false查询最小值
     */
    public SparseTable(int[] arr, boolean isMax) {
        this.n = arr.length;
        this.isMax = isMax;

        // 预计算log2表
        buildLogTable();

        // 构建ST表
        buildSparseTable(arr);
    }

    /**
     * 预计算log2值，logTable[i] = floor(log2(i))
     * 时间复杂度O(n)
     */
    private void buildLogTable() {
        logTable = new int[n + 1];
        logTable[1] = 0;
        for (int i = 2; i <= n; i++) {
            logTable[i] = logTable[i / 2] + 1;
        }
    }

    /**
     * 构建ST表
     * 时间复杂度O(n log n)
     */
    private void buildSparseTable(int[] arr) {
        int maxLog = logTable[n] + 1;
        st = new int[n][maxLog];

        // 初始化：长度为1的区间
        for (int i = 0; i < n; i++) {
            st[i][0] = arr[i];
        }

        // 倍增构建：st[i][k]覆盖[i, i + 2^k - 1]
        for (int k = 1; (1 << k) <= n; k++) {
            for (int i = 0; i + (1 << k) <= n; i++) {
                if (isMax) {
                    st[i][k] = Math.max(st[i][k - 1], st[i + (1 << (k - 1))][k - 1]);
                } else {
                    st[i][k] = Math.min(st[i][k - 1], st[i + (1 << (k - 1))][k - 1]);
                }
            }
        }
    }

    /**
     * 查询区间[l, r]的最值，0-based索引，O(1)
     * @param l 左边界（包含）
     * @param r 右边界（包含）
     * @return 区间最值
     */
    public int query(int l, int r) {
        if (l > r || l < 0 || r >= n) {
            throw new IllegalArgumentException("Invalid query range");
        }

        int len = r - l + 1;
        int k = logTable[len];  // 最大的k使得2^k <= len

        // 两个长度为2^k的区间覆盖[l, r]
        if (isMax) {
            return Math.max(st[l][k], st[r - (1 << k) + 1][k]);
        } else {
            return Math.min(st[l][k], st[r - (1 << k) + 1][k]);
        }
    }

    /**
     * 查询区间最大值的索引位置（用于需要知道最值位置的场景）
     * 需要额外维护索引ST表
     */
    public static class SparseTableWithIndex {
        private int n;
        private int[][] st;       // 存储的是索引而非值
        private int[] logTable;
        private int[] arr;        // 原始数组引用
        private boolean isMax;

        public SparseTableWithIndex(int[] arr, boolean isMax) {
            this.n = arr.length;
            this.arr = arr;
            this.isMax = isMax;

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

            int maxLog = logTable[n] + 1;
            st = new int[n][maxLog];

            for (int i = 0; i < n; i++) {
                st[i][0] = i;  // 长度为1时，索引就是自身
            }

            for (int k = 1; (1 << k) <= n; k++) {
                for (int i = 0; i + (1 << k) <= n; i++) {
                    int leftIdx = st[i][k - 1];
                    int rightIdx = st[i + (1 << (k - 1))][k - 1];

                    if (isMax) {
                        st[i][k] = arr[leftIdx] >= arr[rightIdx] ? leftIdx : rightIdx;
                    } else {
                        st[i][k] = arr[leftIdx] <= arr[rightIdx] ? leftIdx : rightIdx;
                    }
                }
            }
        }

        /**
         * 返回区间最值的索引位置
         */
        public int queryIndex(int l, int r) {
            int len = r - l + 1;
            int k = logTable[len];

            int leftIdx = st[l][k];
            int rightIdx = st[r - (1 << k) + 1][k];

            if (isMax) {
                return arr[leftIdx] >= arr[rightIdx] ? leftIdx : rightIdx;
            } else {
                return arr[leftIdx] <= arr[rightIdx] ? leftIdx : rightIdx;
            }
        }

        /**
         * 返回区间最值
         */
        public int queryValue(int l, int r) {
            return arr[queryIndex(l, r)];
        }
    }

    /**
     * 支持GCD查询的ST表（GCD也满足重叠区间性质）
     */
    public static class STGCD {
        private int n;
        private int[][] st;
        private int[] logTable;

        public STGCD(int[] arr) {
            this.n = arr.length;
            logTable = new int[n + 1];
            logTable[1] = 0;
            for (int i = 2; i <= n; i++) {
                logTable[i] = logTable[i / 2] + 1;
            }

            int maxLog = logTable[n] + 1;
            st = new int[n][maxLog];

            for (int i = 0; i < n; i++) {
                st[i][0] = arr[i];
            }

            for (int k = 1; (1 << k) <= n; k++) {
                for (int i = 0; i + (1 << k) <= n; i++) {
                    st[i][k] = gcd(st[i][k - 1], st[i + (1 << (k - 1))][k - 1]);
                }
            }
        }

        private int gcd(int a, int b) {
            return b == 0 ? a : gcd(b, a % b);
        }

        public int query(int l, int r) {
            int len = r - l + 1;
            int k = logTable[len];
            return gcd(st[l][k], st[r - (1 << k) + 1][k]);
        }
    }

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

        System.out.println("原始数组:");
        for (int x : arr) System.out.print(x + " ");
        System.out.println("\n");

        // 最大值ST表
        SparseTable maxSt = new SparseTable(arr, true);
        System.out.println("区间[0, 5]最大值: " + maxSt.query(0, 5));  // 9
        System.out.println("区间[3, 8]最大值: " + maxSt.query(3, 8));  // 9
        System.out.println("区间[6, 10]最大值: " + maxSt.query(6, 10)); // 6

        // 最小值ST表
        SparseTable minSt = new SparseTable(arr, false);
        System.out.println("\n区间[0, 5]最小值: " + minSt.query(0, 5));  // 1
        System.out.println("区间[3, 8]最小值: " + minSt.query(3, 8));  // 1
        System.out.println("区间[6, 10]最小值: " + minSt.query(6, 10)); // 2

        // 带索引的ST表
        SparseTableWithIndex maxIdxSt = new SparseTableWithIndex(arr, true);
        System.out.println("\n区间[0, 5]最大值索引: " + maxIdxSt.queryIndex(0, 5)); // 5
        System.out.println("区间[0, 5]最大值: " + maxIdxSt.queryValue(0, 5)); // 9

        // GCD ST表
        int[] arr2 = {12, 18, 6, 24, 30};
        STGCD gcdSt = new STGCD(arr2);
        System.out.println("\nGCD区间[0, 4]: " + gcdSt.query(0, 4)); // 6
        System.out.println("GCD区间[1, 3]: " + gcdSt.query(1, 3)); // 6
    }
}

复杂度分析

为什么查询是O(1)？

关键在于log表预计算。logTable[len]通过一次数组查表即可获得，不需要实时计算对数。随后的两次st数组访问和一次max/min操作都是常数时间。

与线段树的对比

可扩展性

ST表不仅适用于最大/最小值查询，任何满足幂等性（f(f(a,b), f(b,c)) = f(a, b, c)）的运算都可以使用ST表：

• GCD：gcd(gcd(a,b), gcd(b,c)) = gcd(a,b,c) ✓
• 按位与/或：同样满足重叠性质 ✓
• 最大值/最小值：✓
• 求和：不满足幂等性（重叠部分会被重复计算）✗

应用场景

1. 静态数组的频繁区间查询：如股票价格区间最高/最低点查询
2. LCA问题转换：利用欧拉序+RMQ求解树上最近公共祖先
3. 滑动窗口最值：配合双指针或单调队列的预处理
4. 算法竞赛：时间要求严格的RMQ问题

总结

ST表是静态区间查询问题的经典解法，通过倍增预处理和重叠区间覆盖两大技巧，将查询复杂度降到了理论下界O(1)。理解ST表的关键在于把握其适用的前提——数组不发生修改。在正确场景下使用ST表，可以显著提升大量区间查询的效率，是每位算法学习者应当掌握的实用工具。