这一篇我们来看树状阵列的加强版线段树，树状阵列能玩的线段树一样可以玩，而且能玩的更好，他们在区间求和，最大，平均
等经典的 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