RMQ算法

RMQ（Range Minimum Query）算法用于解决在一个数组中查询指定范围内最小元素的问题。以下是一种常见的RMQ算法实现，使用稀疏表（Sparse Table）的方法来解决RMQ问题的Java代码示例：

public class RMQAlgorithm {

    static int[][] sparseTable;

    public static void buildSparseTable(int[] arr) {
        int n = arr.length;
        int logN = (int) (Math.log(n) / Math.log(2)) + 1;
        sparseTable = new int[n][logN];

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

        for (int j = 1; (1 << j) <= n; j++) {
            for (int i = 0; i + (1 << j) - 1 < n; i++) {
                sparseTable[i][j] = Math.min(sparseTable[i][j - 1], sparseTable[i + (1 << (j - 1))][j - 1]);
            }
        }
    }

    public static int queryRMQ(int left, int right) {
        int j = (int) (Math.log(right - left + 1) / Math.log(2));
        return Math.min(sparseTable[left][j], sparseTable[right - (1 << j) + 1][j]);
    }

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

        int left = 1;
        int right = 4;
        int minInRange = queryRMQ(left, right);

        System.out.println("Minimum element in range [" + left + ", " + right + "]: " + minInRange);
    }
}

在这个示例中，buildSparseTable 方法构建了一个稀疏表，用于在数组中查询最小元素。queryRMQ 方法用于查询指定范围内的最小元素。这种方法的时间复杂度为O(1)查询，但需要O(n log n)的预处理时间和O(n log n)的空间。

请注意，稀疏表只适用于不会频繁修改数组内容的情况，因为构建稀疏表的开销较大。在实际应用中，如果需要频繁修改数组，可以考虑其他数据结构如线段树。