范圍最小查詢（平方根分解和稀疏表） · GeeksForGeeks 中文系列教程

# 范圍最小查詢（平方根分解和稀疏表） > 原文： [https://www.geeksforgeeks.org/range-minimum-query-for-static-array/](https://www.geeksforgeeks.org/range-minimum-query-for-static-array/) 我們有一個數組`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)`**時間來查詢。另一種方法是使用 [**段樹**](https://www.geeksforgeeks.org/segment-tree-set-1-range-minimum-query/) 。對于段樹，預處理時間為`O(n)`，到范圍最小查詢的時間為`O(log n)`。存儲段樹所需的額外空間為`O(n)`。段樹也允許在`O(log n)`時間進行更新。 ### 如果我們知道數組是靜態的，我們可以做得更好嗎？沒有更新操作且范圍最小查詢很多時，如何優化查詢時間？以下是不同的方法。 **方法 1（簡單解決方案）** 一個簡單解決方案是創建 2D 數組`lookup[][]`，其中條目`lookup[i][j]`將最小值存儲在`arr[i, j]`中。現在可以在`O(1)`時間中計算給定范圍的最小值。 ![rmqsimple](https://img.kancloud.cn/62/eb/62eb24537e1a77bf021fc2c39e6a0b0a_498x416.png) ## C++ ```cpp // C++ program to do range minimum query in O(1) time with O(n*n) // extra space and O(n*n) preprocessing time. #include<bits/stdc++.h> using namespace std; #define MAX 500 // lookup[i][j] is going to store index of minimum value in // arr[i..j] int lookup[MAX][MAX]; // Structure to represent a query range struct Query { ????int L, R; }; // Fills lookup array lookup[n][n] for all possible values of // query ranges 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] 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 L = q[i].L, R = q[i].R; ????????// Print sum of current query range ????????cout << "Minimum of [" << L << ", " ?????????????<< R << "] is "? << arr[lookup[L][R]] << endl; ????} } // Driver program int main() { ????int a[] = {7, 2, 3, 0, 5, 10, 3, 12, 18}; ????int n = sizeof(a)/sizeof(a[0]); ????Query q[] = {{0, 4}, {4, 7}, {7, 8}}; ????int m = sizeof(q)/sizeof(q[0]); ????RMQ(a, n, q, m); ????return 0; } ```