資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學線段樹 | 區間最小值查詢
線段樹 - 線段樹是一種用於儲存區間和線段的樹形資料結構。它是一種靜態結構，即一旦構建就無法修改。線段樹用於處理陣列或類似線性資料結構上的區間查詢。
線上段樹中，我們將輸入陣列劃分為多個線段，並預計算這些線段的值。線段樹中的每個節點都表示陣列的一個區間或線段。根節點表示整個陣列，每個子節點表示由父節點劃分形成的線段。這種劃分最終導致葉節點表示陣列的單個元素。
用於區間和查詢的線段樹 -
Original Array: [7, 1, 2, 3, 6, 5, 0, 4]
Segment Tree:
38
/ \
13 25
/ \ / \
8 5 11 4
/ \ / \ / \ / \
7 1 2 3 6 5 0 4
線段樹的每個區間查詢和更新操作的複雜度為 O(logN)。
區間最小值查詢 - RMQ 是一種常見問題，對於給定的陣列，我們需要找到指定區間內的最小元素。線段樹是解決此問題的最高效的資料結構。
問題陳述
給定一個包含 N 個元素的整數陣列 arr[] 以及起始和結束索引。任務是找到位於 [start, end] 範圍內的元素中的最小元素。
示例 1
輸入
N = 8
arr[] = {1, 7, 8, 9, 5, 2, 3, 4}
start = 2
end = 6
輸出
2
解釋
Array within the specified range is: {8, 9, 5, 2, 3}
在給定範圍內，2 是最小元素。
示例 2
輸入
N = 3
arr[] = {1, 3, 2}
start = 1
end = 1
輸出
3
解釋
Array within the specified range is: {3}
在給定範圍內，3 是最小元素。
解決方案
區間最小值查詢問題可以透過以下步驟解決：
為輸入陣列構建線段樹。
遞迴查詢樹中包含在查詢中的線段。每個線段可以歸類為以下幾種情況之一：
完全重疊 - 當前線段完全在查詢範圍內。
無重疊 - 當前線段完全在查詢範圍之外。
部分重疊 - 當前線段部分覆蓋查詢範圍。
構建線段樹的虛擬碼
function segmentTreeUtil(arr, seg_start, seg_end, tree, curr)
if seg_start == seg_end then
tree[curr] = arr[seg_start]
return arr[seg_start]
mid = getMid(seg_start, seg_end)
tree[curr] = minVal(segmentTreeUtil(arr, seg_start, mid, tree, curr * 2 + 1), segmentTreeUtil(arr, mid + 1, seg_end, tree, curr * 2 + 2))
return tree[curr]
end function
function segmentTree(arr, n)
x = ceil(log2(n))
max_size = 2 * (2^x) - 1
tree = new int[max_size]
segmentTreeUtil(arr, 0, n - 1, tree, 0)
return tree
end function
RMQ 的虛擬碼
function RMQUtil(tree, seg_start, seg_end, start, end, index)
if start <= seg_start and end >= seg_end then
return tree[index]
if seg_end < start or seg_start > end then
return INT_MAX
end function
mid = getMid(seg_start, seg_end)
return minVal(RMQUtil(tree, seg_start, mid, start, end, 2 * index + 1), RMQUtil(tree, mid + 1, seg_end, start, end, 2 * index + 2))
function RMQ(tree, n, start, end)
if start < 0 or end > n - 1 or start > end then
print "Query Range Invalid"
return -1
return RMQUtil(tree, 0, n - 1, start, end, 0)
end function
示例：C++ 實現
以下程式碼構建一個線段樹來解決 RMQ 問題。
#include <bits/stdc++.h>
using namespace std;
int minVal(int x, int y){
return (x < y) ? x : y;
}
int getMid(int x, int y){
return x + (y - x) / 2;
}
// Recursive function used to find the minimum element in the query range
int RMQUtil(int *tree, int seg_start, int seg_end, int start, int end, int index){
// Complete Overlap
if (start <= seg_start && end >= seg_end)
return tree[index];
// No Overlap
if (seg_end < start || seg_start > end)
return INT_MAX;
// Partial Overlap
int mid = getMid(seg_start, seg_end);
return minVal(RMQUtil(tree, seg_start, mid, start, end, 2 * index + 1), RMQUtil(tree, mid + 1, seg_end, start, end, 2 * index + 2));
}
// Calculates RMQ by calling RMQUtil()
int RMQ(int *tree, int n, int start, int end){
if (start < 0 || end > n - 1 || start > end){
cout << "Query Range Invalid";
return -1;
}
return RMQUtil(tree, 0, n - 1, start, end, 0);
}
// Creates Segment Tree for input array
int segmentTreeUtil(int arr[], int seg_start, int seg_end, int *tree, int curr){
// Base Case of only one element in array
if (seg_start == seg_end) {
tree[curr] = arr[seg_start];
return arr[seg_start];
}
// Dividing array into segments
int mid = getMid(seg_start, seg_end);
tree[curr] = minVal(segmentTreeUtil(arr, seg_start, mid, tree, curr * 2 + 1), segmentTreeUtil(arr, mid + 1, seg_end, tree, curr * 2 + 2));
return tree[curr];
}
// Creates Segment Tree by allocating memmory and calling segmentTreeUtil()
int *segmentTree(int arr[], int n){
int x = (int)(ceil(log2(n)));
int max_size = 2 * (int)pow(2, x) - 1;
int *tree = new int[max_size];
segmentTreeUtil(arr, 0, n - 1, tree, 0);
return tree;
}
int main(){
int arr[] = {1, 7, 8, 9, 5, 2, 3, 4};
int n = 8;
int *tree = segmentTree(arr, n);
int start = 2;
int end = 6;
cout << "Minimum value = " << RMQ(tree, n, start, end) << endl;
return 0;
}
輸出
Minimum value = 2
時間複雜度 - 構建樹的時間複雜度為 O(N)，每個 RMQ 的時間複雜度為 O(logn)。因此，對於 Q 個查詢，時間複雜度為 O(Q*logN)。
空間複雜度 - O(N)
結論
總之，使用線段樹的區間最小值查詢 (RMQ) 是一種高效的資料結構和演算法，用於查詢陣列給定範圍內的最小元素。每個查詢的時間複雜度為 O(logN)，優於具有 O(N) 複雜度的樸素遍歷陣列的方法。
更新於：2023-11-03
780 次瀏覽
廣告