數據結構教程：段樹（Segment Tree）
段樹是一種基於完全二叉樹的數據結構，專為解決數組區間查詢和修改問題而設計。它能將一個數組的所有連續子區間的信息高效地存儲在樹中，使得對任意區間的查詢或更新操作可以在O(log n)的時間復雜度內完成。
基本概念與結構
• 段樹的每個節點關聯著原數組的一個連續子區間。
• 根節點代表整個數組，其左右子節點分別表示左半部分和右半部分。
• 通過遞歸劃分數組區間直到長度為1，形成葉子節點，對應原數組單個元素。
基本操作
1. 構建段樹：
• 輸入給定數組arr和大小n，創建大小為4*n的數組模擬完全二叉樹，並自底向上計算每個節點對應的區間和或其他信息。
2. 查詢操作：
• 給定一個查詢區間[l, r]，從根節點開始自頂向下查找，合並沿途節點信息以獲取該區間的結果。
3. 更新操作：
• 當需要修改原數組某個位置值時，找到對應影響范圍的段樹節點進行更新，並回溯到根節點同步所有相關節點信息。
C 示例代碼片段（區間求和為例）
class SegmentTree {
private:
vector<int> tree; // 存儲段樹的數組
public:
// 構造函數，輸入為原數組arr和大小n
SegmentTree(vector<int>& arr, int n) {
tree.resize(4 * n);
build(arr, 0, 0, n - 1);
}
// 從下至上構建段樹
void build(vector<int>& arr, int node, int start, int end) {
if (start == end) {
tree[node] = arr[start];
return;
}
int mid = start (end - start) / 2;
build(arr, 2 * node 1, start, mid); // 左子樹
build(arr, 2 * node 2, mid 1, end); // 右子樹
tree[node] = tree[2 * node 1] tree[2 * node 2]; // 合並區間和
}
// 查詢區間[l, r]的和
int query(int l, int r) {
return query(0, 0, n - 1, l, r);
}
// 自頂向下查詢區間[l, r]的和
int query(int node, int start, int end, int l, int r) {
// 空區間或不在查詢范圍內返回0
if (l > end || r < start)
return 0;
// 區間完全包含在查詢范圍內，直接返回節點值
if (l <= start && end <= r)
return tree[node];
int mid = start (end - start) / 2;
// 分別查詢左右子區間和，然後相加
return query(2 * node 1, start, mid, l, r) query(2 * node 2, mid 1, end, l, r);
}
// 更新第pos位置的值為val（這裡僅展示框架）
void update(int pos, int val) {
update(0, 0, n - 1, pos, val);
}
// 自頂向下更新第pos位置的值為val
void update(int node, int start, int end, int pos, int val) {
// 更新到葉節點後，根據實際情況調整父節點信息
}
};總結來說，段樹通過構建一棵反映數組區間變化的完全二叉樹，極大地提高了涉及動態區間查詢、修改等問題的處理效率。盡管本例隻展示了區間求和的操作，但實際應用中，段樹還可以用於求區間最大/最小值、區間加法、區間翻轉等多種問題。