查看“︁線段樹 (儲存區間)”︁的源代码

{{Copy edit|time=2021-10-30T05:50:11+00:00}}

{{Otheruses|other=用于查询数列信息的数据结构|线段树 (区间查询)}}
{{NoteTA
|G1= IT
}}
'''線段樹'''（{{lang-en|Segment tree}}）是一種[[二元樹]]形資料結構，1977年由[[喬恩·本特利 (計算機科學家)|喬恩·本特利]]發明<ref name="Schwarzkopf4">{{Harv |de Berg|van Kreveld|Overmars|Schwarzkopf|2000|p=229}}</ref>，用以儲存[[區間]]或[[線段]]，並且允許快速查詢結構內包含某一點的所有區間。

一個包含<math>n</math>個區間的線段樹，空間複雜度為<math>O(n)</math>，查詢的時間複雜度則為<math>O(\log n+k)</math>，其中<math>k</math>是符合條件的區間數量。

此資料結構亦可推廣到高維度。

==結構==
線段樹是一個平衡的二叉树，它将每个长度不为1的区间划分成左右两个区间递归求解。令整個區間的長度為N，則其有N個葉節點，每個葉節點代表一個單位區間，每個內部結點代表的區間為其兩個兒子代表區間的聯集。这种数据结构可以方便的进行大部分的区间操作。

本處以一維的線段樹為例。
[[File:Segment tree.svg|thumb|upright=1.9|線段樹結構示意，其儲存的線段顯示在圖片的下方。]]
令S是一維線段的集合。將這些線段的端點坐標由小到大排序，令其為<math>x_1, x_2, \cdots , x_m</math>。我們將被這些端點切分的每一個區間稱為「單位區間」（每個端點所在的位置會單獨成為一個單位區間），從左到右包含：

:<math>(-\infty, x_1), [x_1,x_1], (x_1, x_2), [x_2, x_2], ..., (x_{m-1}, x_m), [x_m, x_m], (x_m, +\infty)</math>

線段樹的結構為一個[[二元樹]]，每個節點都代表一個坐標區間，節點N所代表的區間記為Int(N)，則其需符合以下條件：
*其每一個葉節點，從左到右代表每個單位區間。
*其內部節點代表的區間是其兩個兒子代表的區間之聯集。
*每個節點（包含葉子）中有一個儲存線段的資料結構。若一個線段S的坐標區間包含Int(N)但不包含Int(parent(N))，則節點N中會儲存線段S。

==實現==

===[[C++]]===
在此以求出範圍最小值作為範例

<syntaxhighlight lang=cpp>

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] 里的值只用于子结点。
};

</syntaxhighlight>

===[[C语言|C]]===
在此以求出範圍最小值作為範例

<syntaxhighlight lang=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;
}
</syntaxhighlight>

==參考資料==
{{reflist}}

* {{cite book |last1=de Berg |first1=Mark |last2=van Kreveld |first2=Marc |last3=Overmars |first3=Mark |last4=Schwarzkopf |first4=Otfried |publication-date=2000 |year=2000 |title=Computational Geometry: algorithms and applications |edition=2nd |publisher=Springer-Verlag Berlin Heidelberg New York |isbn=978-3-540-77973-5 |chapter=More Geometric Data Structures |doi=10.1007/978-3-540-77974-2 |ref=harv |url=http://link.springer.com/10.1007/978-3-540-77974-2}}
* [http://www.cs.nthu.edu.tw/~wkhon/ds/ds10/tutorial/tutorial6.pdf Stabbing Problem] {{Wayback|url=http://www.cs.nthu.edu.tw/~wkhon/ds/ds10/tutorial/tutorial6.pdf |date=20101105230058 }}

{{计算机科学中的树}}
[[Category:数据结构|X]]
[[Category:树结构]]
[[Category:二叉树]]
[[Category:搜索树]]