資料結構
網路
關係型資料庫管理系統
作業系統
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)。
範圍求和查詢 - RSQ 是一個常見問題，對於給定的陣列，我們需要找到指定範圍內所有元素的總和。線段樹是解決此問題最有效的資料結構。
問題陳述
給定一個包含 N 個元素的整數陣列 arr[] 以及起始和結束索引。任務是找到範圍 [start, end] 內所有元素的總和。
示例 1
輸入
N = 8
arr[] = {1, 7, 8, 9, 5, 2, 3, 4}
start = 2
end = 6
輸出
27
解釋
Array within the specified range is: {8, 9, 5, 2, 3}
In the given range, the sum of elements = 8 + 9 + 5 + 2 + 3 = 27.
示例 2
輸入
N = 3
arr[] = {1, 3, 2}
start = 1
end = 1
輸出
3
解釋
Array within the specified range is: {3}
In the given range, the sum of elements = 3.
解決方案方法
範圍求和查詢問題可以透過以下步驟解決 -
為輸入陣列構建線段樹。
遞迴查詢樹中包含在查詢中的線段。每個線段可以歸類為以下之一 -
完全重疊 - 當前線段完全在查詢範圍內。
無重疊 - 當前線段完全在查詢範圍之外。
部分重疊 - 當前線段部分覆蓋查詢範圍。
構建線段樹的虛擬碼
function segmentTreeUtil(arr, seg_start, seg_end, tree, curr):
if seg_start == seg_end:
tree[curr] = arr[seg_start]
return arr[seg_start]
mid = getMid(seg_start, seg_end)
tree[curr] = segmentTreeUtil(arr, seg_start, mid, tree, curr * 2 + 1) + segmentTreeUtil(arr, mid + 1, seg_end, tree, curr * 2 + 2)
return tree[curr]
function segmentTree(arr, n):
x = ceil(log2(n))
max_size = 2 * pow(2, x) - 1
tree = new int[max_size]
segmentTreeUtil(arr, 0, n - 1, tree, 0)
return tree
RSQ 的虛擬碼
function RSQUtil(tree, seg_start, seg_end, start, end, curr):
if start <= seg_start AND end >= seg_end:
return tree[curr]
if seg_end < start OR seg_start > end:
return 0
mid = getMid(seg_start, seg_end)
return RSQUtil(tree, seg_start, mid, start, end, 2 * curr + 1) + RSQUtil(tree, mid + 1, seg_end, start, end, 2 * curr + 2)
function RSQ(tree, n, start, end):
if start < 0 OR end > n - 1 OR start > end:
print "Query Range Invalid"
return -1
return RSQUtil(tree, 0, n - 1, start, end, 0)
示例：C++ 實現
以下程式碼構建了一個線段樹來解決 RSQ 問題。
#include <bits/stdc++.h>
using namespace std;
int getMid(int x, int y){
return x + (y - x) / 2;
}
// Recursive function used to find the sum of elements in the query range
int RSQUtil(int *tree, int seg_start, int seg_end, int start, int end, int curr){
// Complete Overlap
if (start <= seg_start && end >= seg_end)
return tree[curr];
// No Overlap
if (seg_end < start || seg_start > end)
return 0;
// Partial Overlap
int mid = getMid(seg_start, seg_end);
return RSQUtil(tree, seg_start, mid, start, end, 2 * curr + 1) + RSQUtil(tree, mid + 1, seg_end, start, end, 2 * curr + 2);
}
// Calculates RSQ by calling RSQUtil(
int RSQ(int *tree, int n, int start, int end){
if (start < 0 || end > n - 1 || start > end){
cout << "Query Range Invalid";
return -1;
}
return RSQUtil(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] = 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 << "Sum = " << RSQ(tree, n, start, end) << endl;
return 0;
}
輸出
Sum = 27
時間複雜度 - 構建樹的時間複雜度為 O(N)，每個 RSQ 的時間複雜度為 O(logn)。因此，對於 Q 個查詢，時間複雜度為 O(Q*logN)。
空間複雜度 - O(N)
結論
總之，使用線段樹的範圍求和查詢 (RSQ) 是一種有效的資料結構和演算法，用於查詢陣列給定範圍內的最小元素。每個查詢的時間複雜度為 O(logN)，這優於具有 O(N) 複雜度的樸素迭代陣列方法。
更新於: 2023-11-03
569 次檢視
廣告