范围最小值查询（平方根分解与稀疏表）

我们有一个数组 arr[0 . . . n-1]。我们需要能够高效地找到从索引 L（查询起点）到 R（查询终点）范围内的最小值，其中 0 <= L <= R <= n-1。考虑一下当有很多范围查询时的情况。

示例：

Input:  arr[]   = {7, 2, 3, 0, 5, 10, 3, 12, 18};
        query[] = [0, 4], [4, 7], [7, 8]
Output: Minimum of [0, 4] is 0
        Minimum of [4, 7] is 3
        Minimum of [7, 8] is 12

一个简单的解决方案是运行一个从 L 到 R 的循环来查找给定范围内的最小元素。在最坏情况下，该解决方案查询需要花费 O(n) 的时间。

另一种方法是使用 线段树。使用线段树，预处理时间为 O(n)，而范围最小值查询的时间为 O(Logn)。所需的额外空间为 O(n) 用于存储线段树。线段树还允许在 O(Log n) 的时间内进行更新。

如果我们知道数组是静态的，我们能做得更好吗？

当没有更新操作且有许多范围最小值查询时，如何优化查询时间？

以下是不同的方法。

方法 1（简单解决方案）

一个简单的解决方案是创建一个 2D 数组 lookup[][]，其中条目 lookup[i][j] 存储范围 arr[i..j] 中的最小值。现在可以在 O(1) 时间内计算给定范围的最小值。

!rmqsimple

C++


CODEBLOCK_95fbadb4


Java


“

// Java program to do range minimum query

// in O(1) time with O(n*n) extra space

// and O(n*n) preprocessing time.

import java.util.*;

class GFG {

static int MAX = 500;

// lookup[i][j] is going to store index of

// minimum value in arr[i..j]

static int[][] lookup = new int[MAX][MAX];

// Structure to represent a query range

static class Query {

int L, R;

public Query(int L, int R)

{

this.L = L;

this.R = R;

}

};

// Fills lookup array lookup[n][n] for

// all possible values of query ranges

static void preprocess(int arr[], int n)

{

// Initialize lookup[][] for

// the intervals with length 1

for (int i = 0; i < n; i++)

lookup[i][i] = i;

// Fill rest of the entries in bottom up manner

for (int i = 0; i < n; i++) {

for (int j = i + 1; j < n; j++)

// To find minimum of [0,4],

// we compare minimum of

// arr[lookup[0][3]] with arr[4].

if (arr[lookup[i][j – 1]] < arr[j])

lookup[i][j] = lookup[i][j – 1];

else

lookup[i][j] = j;

}

}

// Prints minimum of given m query

// ranges in arr[0..n-1]

static void RMQ(int arr[], int n, Query q[], int m)

{

// Fill lookup table for

// all possible input queries

preprocess(arr, n);

// One by one compute sum of all queries

for (int i = 0; i < m; i++) {

// Left and right boundaries

// of current range

int