维基百科
線段樹 (儲存區間)
線段樹(英語:Segment tree)是一種二元樹形資料結構,1977年由Jon Louis Bentley發明[1],用以儲存區間或線段,並且允許快速查詢結構內包含某一點的所有區間。
一個包含個區間的線段樹,空間複雜度為,查詢的時間複雜度則為,其中是符合條件的區間數量。
此資料結構亦可推廣到高維度。
結構 编辑
線段樹是一個平衡的二叉树,它将每个长度不为1的区间划分成左右两个区间递归求解。令整個區間的長度為N,則其有N個葉節點,每個葉節點代表一個單位區間,每個內部結點代表的區間為其兩個兒子代表區間的聯集。这种数据结构可以方便的进行大部分的区间操作。
本處以一維的線段樹為例。
令S是一維線段的集合。將這些線段的端點坐標由小到大排序,令其為 。我們將被這些端點切分的每一個區間稱為「單位區間」(每個端點所在的位置會單獨成為一個單位區間),從左到右包含:
線段樹的結構為一個二元樹,每個節點都代表一個坐標區間,節點N所代表的區間記為Int(N),則其需符合以下條件:
- 其每一個葉節點,從左到右代表每個單位區間。
- 其內部節點代表的區間是其兩個兒子代表的區間之聯集。
- 每個節點(包含葉子)中有一個儲存線段的資料結構。若一個線段S的坐標區間包含Int(N)但不包含Int(parent(N)),則節點N中會儲存線段S。
實現 编辑
C++ 编辑
在此以求出範圍最小值作為範例
template <typename T> class SegMinTree { public: // 新建一个最小值线段树用于处理[0, n)的数据 SegMinTree(int n) : N(n), values_(4 * n), deltas_(4 * n) {} // 返回指定位置的数据 T Get(int index) const { return GetRangeMin(index, index + 1); } // 将数据写入指定位置 void Set(int index, T value) { IncrementRange(index, index + 1, value - Get(index)); } // 返回区间上的最小值 T GetRangeMin(int start, int end) const { return Query(FullSegment(), start, end); } // 对一段区间上的所有值加上同一个增量 void IncrementRange(int start, int end, T delta) { Increment(FullSegment(), start, end, delta); } private: struct Segment { int id; int start; int end; bool Overlaps(int start, int end) const { return this->start < end && this->end > start; } bool IsIn(int start, int end) const { return start <= this->start && this->end <= end; } Segment Left() const { return {.id = id * 2, .start = start, .end = (start + end + 1) / 2}; } Segment Right() const { return {.id = id * 2 + 1, .start = (start + end + 1) / 2, .end = end}; } }; Segment FullSegment() const { return {.id = 1, .start = 0, .end = N}; } T Query(const Segment& segment, int start, int end) const { if (!segment.Overlaps(start, end)) { return std::numeric_limits<T>::max(); } if (segment.IsIn(start, end)) { return values_[segment.id]; } // 处理部分重合的情况 T children_value = std::min(Query(segment.Left(), start, end), Query(segment.Right(), start, end)); return deltas_[segment.id] + children_value; } // 返回segment里面新的最小值(跟[start, end)无关). T Increment(const Segment& segment, int start, int end, T delta) { if (!segment.Overlaps(start, end)) { return values_[segment.id]; // 没有改变 } if (segment.IsIn(start, end)) { values_[segment.id] += delta; deltas_[segment.id] += delta; return values_[segment.id]; } // 处理部分重合的情况 T value = std::min(Increment(segment.Left(), start, end, delta), Increment(segment.Right(), start, end, delta)); value += deltas_[segment.id]; values_[segment.id] = value; return value; } const int N; std::vector<T> values_; std::vector<T> deltas_; // deltas_[id] 里的值只用于子结点。 };
C 编辑
在此以求出範圍最小值作為範例
#include <bits/stdc++.h> using namespace std; #define int long long int n , q , seg[800005] = {0} , x , a , b , arr[200005]; //初始化線段樹 void build(int id , int l , int r) { if(l == r){ seg[id] = arr[l]; return; } int mid = (l+r)>>1; build(2*id,l,mid); build(2*id+1,mid+1,r); seg[id] = min(seg[2*id],seg[2*id+1]); return; } //從線段樹中提取資訊 int query(int id , int l , int r , int ql , int qr) { if(qr < l || ql > r)return 1e9; if(ql <= l && r <= qr)return seg[id]; int mid = (l+r)>>1; return min(query(2*id,l,mid,ql,qr), query(2*id+1,mid+1,r,ql,qr)); } //更新線段樹 void update(int id , int l , int r , int k , int u) { if(l==r){ seg[id] = u; return; } int mid = (l+r)>>1; if(k <= mid)update(2*id,l,mid,k,u); else update(2*id+1,mid+1,r,k,u); seg[id] = min(seg[2*id] , seg[2*id+1]); return; } signed main() { //輸入陣列大小 提問數量 cin >> n >> q; for(int i = 1 ; i <= n ; i++)cin >> arr[i]; build(1,1,n); for(int i = 0 ; i < q ; i++) { //輸入 1 a b 代表將第a個數改為b //輸入 2 a b 代表求[a,b]中的最小值 cin >> x >> a >> b; if(x == 1)update(1,1,n,a,b); else if(x == 2)cout << query(1,1,n,a,b) << "\n"; } return 0; }
參考資料 编辑
- ^ (de Berg 等人 2000,p.229)
- de Berg, Mark; van Kreveld, Marc; Overmars, Mark; Schwarzkopf, Otfried. More Geometric Data Structures. Computational Geometry: algorithms and applications 2nd. Springer-Verlag Berlin Heidelberg New York. 20002000. ISBN 3-540-65620-0. doi:10.1007/978-3-540-77974-2.
- http://www.cs.nthu.edu.tw/~wkhon/ds/ds10/tutorial/tutorial6.pdf (页面存档备份,存于互联网档案馆)