這一篇我們來看樹狀陣列的加強版線段樹，樹狀陣列能玩的線段樹一樣可以玩，而且能玩的更好，他們在區間求和，最大，平均
等經典的 RMQ 問題上有著對數時間的優越表現。
一：線段樹
線段樹又稱” 區間樹”，在每個節點上儲存一個區間，當然區間的劃分採用折半的思想，葉子節點只儲存一個值，也叫單元節點，所
以最終的構造就是一個平衡的二叉樹，擁有 CURD 的 O(lgN) 的時間。

從圖中我們可以清楚的看到 [0-10] 被劃分成線段的在樹中的分佈情況，針對區間 [0-N]，最多有 2N 個節點，由於是平衡二叉樹的形
式也可以像堆那樣用陣列來玩，不過更加耗費空間，為最多 4N 個節點，在針對 RMQ 的問題上，我們常常在每個節點上增加一些 sum，
max，min 等變數來記錄求得的累加值，當然你可以理解成動態規劃的思想，由於擁有 logN 的時間，所以在 RMQ 問題上比陣列更加優美。
 
二：程式碼
1: 在節點中定義一些附加值，方便我們處理 RMQ 問題。

1 #region 線段樹的節點
2 ///

3 /// 線段樹的節點
4 ///

5 public class Node
6 {
7 ///

8 /// 區間左端點
9 ///

10 public int left;
11
12 ///

13 /// 區間右端點
14 ///

15 public int right;
16
17 ///

18 /// 左孩子
19 ///

20 public Node leftchild;
21
22 ///

23 /// 右孩子
24 ///

25 public Node rightchild;
26
27 ///

28 /// 節點的 sum 值
29 ///

30 public int Sum;
31
32 ///

33 /// 節點的 Min 值
34 ///

35 public int Min;
36
37 ///

38 /// 節點的 Max 值
39 ///

40 public int Max;
41 }
42 #endregion

 
2：構建 (Build)
前面我也說了，構建有兩種方法，陣列的形式或者鏈的形式，各有特點，我就採用後者，時間為 O(N) 。

1 #region 根據陣列構建 “線段樹”
2 ///

3 /// 根據陣列構建 “線段樹”
4 ///

5 /// 6 public Node Build(int[] nums)
7 {
8 this.nums = nums;
9
10 return Build(nodeTree, 0, nums.Length – 1);
11 }
12 #endregion
13
14 #region 根據陣列構建 “線段樹”
15 ///

16 /// 根據陣列構建 “線段樹”
17 ///

18 /// 19 /// 20 public Node Build(Node node, int left, int right)
21 {
22 //說明已經到根了，當前當前節點的 max，sum，min 值（回溯時統計上一層節點區間的值）
23 if (left == right)
24 {
25 return new Node
26 {
27 left = left,
28 right = right,
29 Max = nums[left],
30 Min = nums[left],
31 Sum = nums[left]
32 };
33 }
34
35 if (node == null)
36 node = new Node();
37
38 node.left = left;
39
40 node.right = right;
41
42 node.leftchild = Build(node.leftchild, left, (left + right) / 2);
43
44 node.rightchild = Build(node.rightchild, (left + right) / 2 + 1, right);
45
46 //統計左右子樹的值 (min，max，sum)
47 node.Min = Math.Min(node.leftchild.Min, node.rightchild.Min);
48 node.Max = Math.Max(node.leftchild.Max, node.rightchild.Max);
49 node.Sum = node.leftchild.Sum + node.rightchild.Sum;
50
51 return node;
52 }
53 #endregion

 
3：區間查詢
線上段樹中，區間查詢還是有點小麻煩的，存在三種情況。
① 完全包含：也就是節點的線段範圍完全在查詢區間的範圍內，這說明我們要麼到了 “單元節點”, 要麼到了一個子區間，這種情況
就是我找到了查詢區間的某一個子區間，直接累積該區間值就可以了。
② 左交集：  這種情況我們需要到左子樹去遍歷。
③右交集：   這種情況我們需要到右子樹去遍歷。
比如說：我要查詢 Sum[4-8] 的值, 最終會成為:Sum 總=Sum[4-4]+Sum[5-5]+Sum[6-8]，時間為 log(N) 。

1 #region 區間查詢
2 ///

3 /// 區間查詢 (分解)
4 ///

5 ///
6 public int Query(int left, int right)
7 {
8 int sum = 0;
9
10 Query(nodeTree, left, right, ref sum);
11
12 return sum;
13 }
14
15 ///

16 /// 區間查詢
17 ///

18 /// 查詢左邊界 19 /// 查詢右邊界 20 /// 查詢的節點 21 ///
22 public void Query(Node node, int left, int right, ref int sum)
23 {
24 //說明當前節點完全包含在查詢範圍內，兩點：要麼是單元節點，要麼是子區間
25 if (left <= node.left && right >= node.right)
26 {
27 //獲取當前節點的 sum 值
28 sum += node.Sum;
29 return;
30 }
31 else
32 {
33 //如果當前的 left 和 right 和 node 的 left 和 right 無交集，此時可返回
34 if (node.left > right || node.right < left) 35 return; 36 37 //找到中間線 38 var middle = (node.left + node.right) / 2; 39 40 //左孩子有交集 41 if (left <= middle) 42 { 43 Query(node.leftchild, left, right, ref sum); 44 } 45 //右孩子有交集 46 if (right >= middle)
47 {
48 Query(node.rightchild, left, right, ref sum);
49 }
50
51 }
52 }
53 #endregion

 
4：更新操作
這個操作跟樹狀陣列中的更新操作一樣，當遞迴的找到待修改的節點後，改完其值然後在當前節點一路回溯，並且在回溯的過程中一
路修改父節點的附加值直到根節點，至此我們的操作就完成了，複雜度同樣為 logN 。

1 #region 更新操作
2 ///

3 /// 更新操作
4 ///

5 /// 6 /// 7 public void Update(int index, int key)
8 {
9 Update(nodeTree, index, key);
10 }
11
12 ///

13 /// 更新操作
14 ///

15 /// 16 /// 17 public void Update(Node node, int index, int key)
18 {
19 if (node == null)
20 return;
21
22 //取中間值
23 var middle = (node.left + node.right) / 2;
24
25 //遍歷左子樹
26 if (index >= node.left && index <= middle) 27 Update(node.leftchild, index, key); 28 29 //遍歷右子樹 30 if (index <= node.right && index >= middle + 1)
31 Update(node.rightchild, index, key);
32
33 //在回溯的路上一路更改，複雜度為 lgN
34 if (index >= node.left && index <= node.right) 35 { 36 //說明找到了節點 37 if (node.left == node.right) 38 { 39 nums[index] = key; 40 41 node.Sum = node.Max = node.Min = key; 42 } 43 else 44 { 45 //回溯時統計左右子樹的值 (min，max，sum) 46 node.Min = Math.Min(node.leftchild.Min, node.rightchild.Min); 47 node.Max = Math.Max(node.leftchild.Max, node.rightchild.Max); 48 node.Sum = node.leftchild.Sum + node.rightchild.Sum; 49 } 50 } 51 } 52 #endregion 最後我們做個例子，在 2000000 的陣列空間中，尋找 200-3000 區間段的 sum 值，看看他的表現如何。 using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Diagnostics; using System.Threading; using System.IO; namespace ConsoleApplication2 { public class Program { public static void Main() { int[] nums = new int[200 * 10000]; for (int i = 0; i < 10000 * 200; i++) { nums[i] = i; } Tree tree = new Tree(); //將當前陣列構建成 “線段樹” tree.Build(nums); var watch = Stopwatch.StartNew(); var sum = tree.Query(200, 3000); watch.Stop(); Console.WriteLine(“耗費時間:{0}ms,  當前陣列有:{1} 個數字, 求出 Sum=:{2}”, watch.ElapsedMilliseconds, nums.Length, sum); Console.Read(); } } public class Tree { #region 線段樹的節點 ///

/// 線段樹的節點
///

public class Node
{
///

/// 區間左端點
///

public int left;
///

/// 區間右端點
///

public int right;
///

/// 左孩子
///

public Node leftchild;
///

/// 右孩子
///

public Node rightchild;
///

/// 節點的 sum 值
///

public int Sum;
///

/// 節點的 Min 值
///

public int Min;
///

/// 節點的 Max 值
///

public int Max;
}
#endregion
Node nodeTree = new Node();
int[] nums;
#region 根據陣列構建 “線段樹”
///

/// 根據陣列構建 “線段樹”
///

/// public Node Build(int[] nums)
{
this.nums = nums;
return Build(nodeTree, 0, nums.Length – 1);
}
#endregion
#region 根據陣列構建 “線段樹”
///

/// 根據陣列構建 “線段樹”
///

/// /// public Node Build(Node node, int left, int right)
{
//說明已經到根了，當前當前節點的 max，sum，min 值（回溯時統計上一層節點區間的值）
if (left == right)
{
return new Node
{
left = left,
right = right,
Max = nums[left],
Min = nums[left],
Sum = nums[left]
};
}
if (node == null)
node = new Node();
node.left = left;
node.right = right;
node.leftchild = Build(node.leftchild, left, (left + right) / 2);
node.rightchild = Build(node.rightchild, (left + right) / 2 + 1, right);
//統計左右子樹的值 (min，max，sum)
node.Min = Math.Min(node.leftchild.Min, node.rightchild.Min);
node.Max = Math.Max(node.leftchild.Max, node.rightchild.Max);
node.Sum = node.leftchild.Sum + node.rightchild.Sum;
return node;
}
#endregion
#region 區間查詢
///

/// 區間查詢 (分解)
///

///
public int Query(int left, int right)
{
int sum = 0;
Query(nodeTree, left, right, ref sum);
return sum;
}
///

/// 區間查詢
///

/// 查詢左邊界 /// 查詢右邊界 /// 查詢的節點 ///
public void Query(Node node, int left, int right, ref int sum)
{
//說明當前節點完全包含在查詢範圍內，兩點：要麼是單元節點，要麼是子區間
if (left <= node.left && right >= node.right)
{
//獲取當前節點的 sum 值
sum += node.Sum;
return;
}
else
{
//如果當前的 left 和 right 和 node 的 left 和 right 無交集，此時可返回
if (node.left > right || node.right < left) return; //找到中間線 var middle = (node.left + node.right) / 2; //左孩子有交集 if (left <= middle) { Query(node.leftchild, left, right, ref sum); } //右孩子有交集 if (right >= middle)
{
Query(node.rightchild, left, right, ref sum);
}
}
}
#endregion
#region 更新操作
///

/// 更新操作
///

/// /// public void Update(int index, int key)
{
Update(nodeTree, index, key);
}
///

/// 更新操作
///

/// /// public void Update(Node node, int index, int key)
{
if (node == null)
return;
//取中間值
var middle = (node.left + node.right) / 2;
//遍歷左子樹
if (index >= node.left && index <= middle) Update(node.leftchild, index, key); //遍歷右子樹 if (index <= node.right && index >= middle + 1)
Update(node.rightchild, index, key);
//在回溯的路上一路更改，複雜度為 lgN
if (index >= node.left && index <= node.right) { //說明找到了節點 if (node.left == node.right) { nums[index] = key; node.Sum = node.Max = node.Min = key; } else { //回溯時統計左右子樹的值 (min，max，sum) node.Min = Math.Min(node.leftchild.Min, node.rightchild.Min); node.Max = Math.Max(node.leftchild.Max, node.rightchild.Max); node.Sum = node.leftchild.Sum + node.rightchild.Sum; } } } #endregion } }   文章來自網際網路部落格網站 http://www.cnblogs.com/huangxincheng/archive/2012/12/08/2808207.html