數組中的最小-最大范圍查詢 · GeeksForGeeks 中文系列教程

# 數組中的最小-最大范圍查詢 > 原文： [https://www.geeksforgeeks.org/min-max-range-queries-array/](https://www.geeksforgeeks.org/min-max-range-queries-array/) 給定數組 arr [0。。。 n-1]。我們需要有效地找到從索引 qs（查詢開始）到 qe（查詢結束）的最小值和最大值，其中 0 < = qs < = qe < = n-1。我們有多個查詢。例子： ``` Input : arr[] = {1, 8, 5, 9, 6, 14, 2, 4, 3, 7} queries = 5 qs = 0 qe = 4 qs = 3 qe = 7 qs = 1 qe = 6 qs = 2 qe = 5 qs = 0 qe = 8 Output: Minimum = 1 and Maximum = 9 Minimum = 2 and Maximum = 14 Minimum = 2 and Maximum = 14 Minimum = 5 and Maximum = 14 Minimum = 1 and Maximum = 14 ``` **簡單解決方案**：我們為每個查詢使用[競賽方法](https://www.geeksforgeeks.org/maximum-and-minimum-in-an-array/)解決了此問題。此方法的復雜度將為 O（查詢* n）。 **有效解決方案**：通過使用[分段樹](https://www.geeksforgeeks.org/segment-tree-set-1-range-minimum-query/)可以更有效地解決此問題。首先閱讀給定的段樹鏈接，然后開始解決此問題。 ``` // C++ program to find minimum and maximum using segment tree #include<bits/stdc++.h> using namespace std; // Node for storing minimum nd maximum value of given range struct node { ???int minimum; ???int maximum; }; // A utility function to get the middle index from corner indexes. int getMid(int s, int e) {? return s + (e -s)/2;? } /*? A recursive function to get the minimum and maximum value in ?????a given range of array indexes. The following are parameters ?????for this function. ????st??? --> Pointer to segment tree ????index --> Index of current node in the segment tree. Initially ??????????????0 is passed as root is always at index 0 ????ss & se? --> Starting and ending indexes of the segment ??????????????????represented? by current node, i.e., st[index] ????qs & qe? --> Starting and ending indexes of query range */ struct node MaxMinUntill(struct node *st, int ss, int se, int qs, ?????????????????????????int qe, int index) { ????// If segment of this node is a part of given range, then return ????//? the minimum and maximum node of the segment ????struct node tmp,left,right; ????if (qs <= ss && qe >= se) ????????return st[index]; ????// If segment of this node is outside the given range ????if (se < qs || ss > qe) ????{ ???????tmp.minimum = INT_MAX; ???????tmp.maximum = INT_MIN; ???????return tmp; ?????} ????// If a part of this segment overlaps with the given range ????int mid = getMid(ss, se); ????left = MaxMinUntill(st, ss, mid, qs, qe, 2*index+1); ????right = MaxMinUntill(st, mid+1, se, qs, qe, 2*index+2); ????tmp.minimum = min(left.minimum, right.minimum); ????tmp.maximum = max(left.maximum, right.maximum); ????return tmp; } // Return minimum and maximum of elements in range from index // qs (quey start) to qe (query end).? It mainly uses // MaxMinUtill() struct node MaxMin(struct node *st, int n, int qs, int qe) { ????struct node tmp; ????// Check for erroneous input values ????if (qs < 0 || qe > n-1 || qs > qe) ????{ ????????printf("Invalid Input"); ????????tmp.minimum = INT_MIN; ????????tmp.minimum = INT_MAX; ????????return tmp; ????} ????return MaxMinUntill(st, 0, n-1, qs, qe, 0); } // A recursive function that constructs Segment Tree for array[ss..se]. // si is index of current node in segment tree st void constructSTUtil(int arr[], int ss, int se, struct node *st, ?????????????????????int si) { ????// If there is one element in array, store it in current node of ????// segment tree and return ????if (ss == se) ????{ ????????st[si].minimum = arr[ss]; ????????st[si].maximum = arr[ss]; ????????return ; ????} ????// If there are more than one elements, then recur for left and ????// right subtrees and store the minimum and maximum of two values ????// in this node ????int mid = getMid(ss, se); ????constructSTUtil(arr, ss, mid, st, si*2+1); ????constructSTUtil(arr, mid+1, se, st, si*2+2); ????st[si].minimum = min(st[si*2+1].minimum, st[si*2+2].minimum); ????st[si].maximum = max(st[si*2+1].maximum, st[si*2+2].maximum); } /* Function to construct segment tree from given array. This function ???allocates memory for segment tree and calls constructSTUtil() to ???fill the allocated memory */ struct node *constructST(int arr[], int n) { ????// Allocate memory for segment tree ????// Height of segment tree ????int x = (int)(ceil(log2(n))); ????// Maximum size of segment tree ????int max_size = 2*(int)pow(2, x) - 1; ????struct node *st = new struct node[max_size]; ????// Fill the allocated memory st ????constructSTUtil(arr, 0, n-1, st, 0); ????// Return the constructed segment tree ????return st; } // Driver program to test above functions int main() { ????int arr[] = {1, 8, 5, 9, 6, 14, 2, 4, 3, 7}; ????int n = sizeof(arr)/sizeof(arr[0]); ????// Build segment tree from given array ????struct node *st = constructST(arr, n); ????int qs = 0;? // Starting index of query range ????int qe = 8;? // Ending index of query range ????struct node result=MaxMin(st, n, qs, qe); ????// Print minimum and maximum value in arr[qs..qe] ????printf("Minimum = %d and Maximum = %d ", ?????????????????????result.minimum, result.maximum); ????return 0; } ``` 輸出： ``` Minimum = 1 and Maximum = 14 ``` **時間復雜度**： O（查詢*登錄） **如果數組上沒有更新，我們可以做得更好嗎？** 上述基于分段樹的解決方案還允許在`O(log n)`時間內進行數組更新。假設沒有更新（或數組是靜態的）的情況。實際上，我們可以通過一些預處理在`O(1)`時間內處理所有查詢。一種簡單的解決方案是制作一個二維表節點，該表存儲所有范圍的最小值和最大值。此解決方案需要`O(1)`查詢時間，但需要 `O(n^2)`預處理時間和 `O(n^2)`額外空間，這對于大 n 來說可能是個問題。我們可以使用[稀疏表](https://www.geeksforgeeks.org/range-minimum-query-for-static-array/)在`O(1)`查詢時間，`O(N log N)`空間和`O(N log N)`預處理時間中解決此問題。本文由 [**Shashank Mishra**](https://practice.geeksforgeeks.org/user-profile.php?user=Shashank%20Mishra) 提供。本文由 GeeksForGeeks 小組審閱。如果發現任何不正確的內容，或者想分享有關上述主題的更多信息，請發表評論。