線段樹 | 給定範圍的和

---

線段樹

線段樹是一種用於儲存區間和線段的樹形資料結構。它是一種靜態結構，即一旦構建完成就無法修改。線段樹用於處理陣列或類似線性資料結構上的範圍查詢。

線上段樹中，我們將輸入陣列劃分為多個線段，並預先計算這些線段的值。線段樹中的每個節點都表示陣列的一個區間或線段。根節點表示整個陣列，每個子節點表示透過劃分父節點形成的線段。這種劃分導致葉子節點表示陣列的單個元素。

用於範圍求和查詢的線段樹 -

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) 複雜度的樸素迭代陣列方法。