線段樹 (儲存區間)

線段樹是一種二元樹形資料結構，1977年由Jon Louis Bentley發明，用以儲存區間或線段，並且允許快速查詢結構內包含某一點的所有區間。一個包含formula_1個區間的線段樹，空間複雜度為formula_2，查詢的時間複雜度則為formula_3，其中formula_4是符合條件的區間數量。此資料結構亦可推廣到高維度。結構.線段樹是一個平衡的二叉樹，它將每個長度不為1的區間劃分成左右兩個區間遞迴求解。令整個區間的長度為N，則其有N個葉節點，每個葉節點代表一個單位區間，每個內部結點代表的區間為其兩個兒子代表區間的聯集。這種資料結構可以方便的進行大部分的區間操作。本處以一維的線段樹為例。令S是一維線段的集合。將這些線段的端點坐標由小到大排序，令其為formula_5。我們將被這些端點切分的每一個區間稱為「單位區間」，從左到右包含：formula_6線段樹的結構為一個二元樹，每個節點都代表一個坐標區間，節點N所代表的區間記為Int(N)，則其需符合以下條件：實現.C++.在此以求出範圍最小值作為範例templateclass SegMinTree {public:// 新建一個最小值線段樹用於處理[0, 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-&gt;start  start;bool IsIn(int start, int end) const {return start end &lt;= 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&amp; segment, int start, int end) const {if (!segment.Overlaps(start, end)) {return std::numeric_limits::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&amp; 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 values_;std::vector deltas_; // deltas_[id] 裡的值只用於子結點。C.在此以求出範圍最小值作為範例using namespace std;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  r)return 1e9;if(ql &lt;= l &amp;&amp; r &lt;= 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 &lt;= 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 &lt;= n ; i++)cin » arr[i];build(1,1,n);for(int i = 0 ; i &lt; 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;