/// <summary>
/// 線段樹:線段樹是二叉樹的一種,常常被用于求區間和與區間最大值等操作
/// </summary>
public class SegmentTree
{
List<int> _orignalData = new List<int>();
List<int?> _tree = new List<int?>();
public SegmentTree()
{
for (int i = 0; i < 1000; i++)
{
_tree.Add(null);
}
}
public void Print()
{
for (int i = 0; i < _tree.Count; i++)
{
if (_tree[i] == null)
{
continue;
}
Console.WriteLine($"第{i}:{_tree[i]}");
}
}
public void Fill(List<int> data)
{
_orignalData = data;
Fill(0, 0, _orignalData.Count - 1);
}
private void Fill(int node, int start, int end)
{
if (start == end)
{
_tree[node] = _orignalData[start];
}
else
{
int mid = (start + end) / 2;
int leftNode = 2 * node + 1;
int rightNode = 2 * node + 2;
Fill(leftNode, start, mid);
Fill(rightNode, mid + 1, end);
_tree[node] = _tree[leftNode] + _tree[rightNode];
}
}
public void Set(int index, int val)
{
SetValue(0, 0, _orignalData.Count - 1, index, val);
}
private void SetValue(int node, int start, int end, int index, int val)
{
if (start == end)
{
_orignalData[index] = val;
_tree[node] = val;
}
else
{
int mid = (start + end) / 2;
int leftNode = 2 * node + 1;
int rightNode = 2 * node + 2;
if (index >= start && index <= mid)
{
SetValue(leftNode, start, mid, index, val);
}
else
{
SetValue(rightNode, mid + 1, end, index, val);
}
_tree[node] = _tree[leftNode] + _tree[rightNode];
}
}
public int? GetSum(int left, int right)
{
return Query(0, 0, _orignalData.Count - 1, left, right);
}
private int? Query(int node, int start, int end, int left, int right)
{
if (right < start || left > end)
{
return 0;
}
else if (left <= start && end <= right)
{
return _tree[node];
}
else if (start == end)
{
return _tree[node];
}
else
{
int mid = (start + end) / 2;
int leftNode = 2 * node + 1;
int rightNode = 2 * node + 2;
int? sumLeft = Query(leftNode, start, mid, left, right);
int? sumRight = Query(rightNode, mid + 1, end, left, right);
return sumLeft + sumRight;
}
}
}
原理
（注：由于線段樹的每個節點代表一個區間，以下叙述中不區分節點和區間，隻是根據語境需要，選擇合适的詞）
線段樹本質上是維護下标為1,2,…,n的n個按順序排列的數的資訊，是以，其實是“點樹”，是維護n的點的資訊，至于每個點的資料的含義可以有很多，
在對線段操作的線段樹中，每個點代表一條線段，在用線段樹維護數列資訊的時候，每個點代表一個數，但本質上都是每個點代表一個數。以下，在讨論線段樹的時候，區間[L,R]指的是下标從L到R的這(R-L+1)個數，而不是指一條連續的線段。隻是有時候這些數代表實際上一條線段的統計結果而已。
線段樹是将每個區間[L,R]分解成[L,M]和[M+1,R] (其中M=(L+R)/2 這裡的除法是整數除法，即對結果下取整)直到 L==R 為止。
開始時是區間[1,n] ,通過遞歸來逐漸分解，假設根的高度為1的話，樹的最大高度為（n>1）。
線段樹對于每個n的分解是唯一的，是以n相同的線段樹結構相同，這也是實作可持久化線段樹的基礎。
下圖展示了區間[1,13]的分解過程：
上圖中，每個區間都是一個節點，每個節點存自己對應的區間的統計資訊。
(1)線段樹的點修改：
假設要修改[5]的值，可以發現，每層隻有一個節點包含[5],是以修改了[5]之後，隻需要每層更新一個節點就可以線段樹每個節點的資訊都是正确的，是以修改次數的最大值為層數。
複雜度O(log2(n))
(2)線段樹的區間查詢：
線段樹能快速進行區間查詢的基礎是下面的定理：
定理：n>=3時，一個[1,n]的線段樹可以将[1,n]的任意子區間[L,R]分解為不超過個子區間。
這樣，在查詢[L,R]的統計值的時候，隻需要通路不超過個節點，就可以獲得[L,R]的統計資訊，實作了O(log2(n))的區間查詢。
下面給出證明：
(2.1)先給出一個粗略的證明（結合下圖）：
先考慮樹的最下層，将所有在區間[L,R]内的點選中，然後，若相鄰的點的直接父節點是同一個，那麼就用這個父節點代替這兩個節點（父節點在上一層）。這樣操作之後，本層最多剩下兩個節點。若最左側被選中的節點是它父節點的右子樹，那麼這個節點會被剩下。若最右側被選中的節點是它的父節點的左子樹，那麼這個節點會被剩下。中間的所有節點都被父節點取代。
對最下層處理完之後，考慮它的上一層，繼續進行同樣的處理，可以發現，每一層最多留下2個節點，其餘的節點升往上一層，這樣可以說明分割成的區間（節點）個數是大概是樹高的兩倍左右。
下圖為n=13的線段樹，區間[2,12]，按照上面的叙述進行操作的過程圖：
由圖可以看出：在n=13的線段樹中，[2,12]=[2] + [3,4] + [5,7] + [8,10] + [11,12] 。
(2.2)然後給出正式一點的證明：
用數學歸納法，證明上面的定理：
首先,n=3,4,5時，用窮舉法不難證明定理成立。
假設對于n= 3,4,5,…,k-1上式都成立，下面來證明對于n=k ( k>=6 )成立：
分為4種情況來證明：
情況一：[L,R]包含根節點(L=1且R=n)，此時，[L,R]被分解為了一個節點，定理成立。
情況二：[L,R]包含根節點的左子節點，此時[L,R]一定不包含根的右子節點（因為如果包含，就可以合并左右子節點，
用根節點替代，此時就是情況一）。這時，以右子節點為根的這個樹的元素個數為。
[L,R]分成的子區間由兩部分組成：
一：根的左子結點，區間數為1
二：以根的右子節點為根的樹中，進行區間查詢，這個可以遞歸使用本定理。
由歸納假設可得，[L,R]一共被分成了個區間。
情況三：跟情況二對稱，不一樣的是，以根的左子節點為根的樹的元素個數為。
[L,R]一共被分成了個區間。
從公式可以看出，情況二的區間數小于等于情況三的區間數，于是隻需要證明情況三的區間數符合條件就行了。
于是，情況二和情況三定理成立。
情況四：[L,R]不包括根節點以及根節點的左右子節點。
于是，剩下的層，每層最多兩個節點（參考粗略證明中的内容）。
于是[L,R]最多被分解成了個區間，定理成立。
上面隻證明了是上界，但是，其實它是最小上界。
n=3,4時，有很多組區間的分解可以達到最小上界。
當n>4時，當且僅當n=2^t (t>=3),L=2,R=2^t -1 時，區間[L,R]的分解可以達到最小上界。
就不證明了，有興趣可以自己去證明。
下圖是n=16 , L=2 , R=15 時的操作圖，此圖展示了達到最小上界的樹的結構。
3)線段樹的區間修改：
線段樹的區間修改也是将區間分成子區間，但是要加一個标記，稱作懶惰标記。
标記的含義：
本節點的統計資訊已經根據标記更新過了，但是本節點的子節點仍需要進行更新。
即，如果要給一個區間的所有值都加上1，那麼，實際上并沒有給這個區間的所有值都加上1，而是打個标記，記下來，這個節點所包含的區間需要加1.打上标記後，要根據标記更新本節點的統計資訊，比如，如果本節點維護的是區間和，而本節點包含5個數，那麼，打上+1的标記之後，要給本節點維護的和+5。這是向下延遲修改，但是向上顯示的資訊是修改以後的資訊，是以查詢的時候可以得到正确的結果。有的标記之間會互相影響，是以比較簡單的做法是，每遞歸到一個區間，首先下推标記（若本節點有标記，就下推标記），然後再打上新的标記，這樣仍然每個區間操作的複雜度是O(log2(n))。
标記有相對标記和絕對标記之分：
相對标記是将區間的所有數+a之類的操作，标記之間可以共存，跟打标記的順序無關（跟順序無關才是重點）。
是以，可以在區間修改的時候不下推标記，留到查詢的時候再下推。
注意：如果區間修改時不下推标記，那麼PushUp函數中，必須考慮本節點的标記。
而如果所有操作都下推标記，那麼PushUp函數可以不考慮本節點的标記，因為本節點的标記一定已經被下推了（也就是對本節點無效了）
絕對标記是将區間的所有數變成a之類的操作，打标記的順序直接影響結果，
是以這種标記在區間修改的時候必須下推舊标記，不然會出錯。
注意，有多個标記的時候，标記下推的順序也很重要，錯誤的下推順序可能會導緻錯誤。
之是以要區分兩種标記，是因為非遞歸線段樹隻能維護相對标記。
因為非遞歸線段樹是自底向上直接修改分成的每個子區間，是以根本做不到在區間修改的時候下推标記。
非遞歸線段樹一般不下推标記，而是自下而上求答案的過程中，根據标記更新答案。
(4)線段樹的存儲結構：
線段樹是用數組來模拟樹形結構，對于每一個節點R ,左子節點為 2R (一般寫作R<<1)右子節點為 2R+1（一般寫作R<<1|1）
然後以1為根節點，是以，整體的統計資訊是存在節點1中的。
這麼表示的原因看下圖就很明白了，左子樹的節點标号都是根節點的兩倍，右子樹的節點标号都是左子樹+1：
線段樹需要的數組元素個數是：,一般都開4倍空間，比如： int A[n<<2];