经典算法题每日演练——第十二题 线段树

       这一篇我们来看树状数组的加强版线段树，树状数组能玩的线段树一样可以玩，而且能玩的更好，他们在区间求和，最大，平均

等经典的RMQ问题上有着对数时间的优越表现。

一：线段树

     线段树又称"区间树”，在每个节点上保存一个区间，当然区间的划分采用折半的思想，叶子节点只保存一个值，也叫单元节点，所

以最终的构造就是一个平衡的二叉树，拥有CURD的O(lgN)的时间。

从图中我们可以清楚的看到[0-10]被划分成线段的在树中的分布情况，针对区间[0-N]，最多有2N个节点，由于是平衡二叉树的形

式也可以像堆那样用数组来玩，不过更加耗费空间，为最多4N个节点，在针对RMQ的问题上，我们常常在每个节点上增加一些sum，

max，min等变量来记录求得的累加值，当然你可以理解成动态规划的思想，由于拥有logN的时间，所以在RMQ问题上比数组更加优美。

 

二：代码

1:在节点中定义一些附加值，方便我们处理RMQ问题。

#region 线段树的节点

 /// summary 

 /// 线段树的节点

 /// /summary 

 public class Node

 /// summary 

 /// 区间左端点

 /// /summary 

 public int left;

 /// summary 

 /// 区间右端点

 /// /summary 

 public int right;

 /// summary 

 /// 左孩子

 /// /summary 

 public Node leftchild;

 /// summary 

 /// 右孩子

 /// /summary 

 public Node rightchild;

 /// summary 

 /// 节点的sum值

 /// /summary 

 public int Sum;

 /// summary 

 /// 节点的Min值

 /// /summary 

 public int Min;

 /// summary 

 /// 节点的Max值

 /// /summary 

 public int Max;

 #endregion

 

 2：构建(Build)

前面我也说了，构建有两种方法，数组的形式或者链的形式，各有特点，我就采用后者，时间为O(N)。

#region 根据数组构建“线段树"

 /// summary 

 /// 根据数组构建“线段树"

 /// /summary 

 /// param name="length" /param 

 public Node Build(int[] nums)

 this.nums = nums;

 return Build(nodeTree, 0, nums.Length - 1);

 #endregion

 #region 根据数组构建“线段树"

 /// summary 

 /// 根据数组构建“线段树"

 /// /summary 

 /// param name="left" /param 

 /// param name="right" /param 

 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

3：区间查询

在线段树中，区间查询还是有点小麻烦的，存在三种情况。

① 完全包含：也就是节点的线段范围完全在查询区间的范围内，这说明我们要么到了“单元节点",要么到了一个子区间，这种情况

                  就是我找到了查询区间的某一个子区间，直接累积该区间值就可以了。

② 左交集：  这种情况我们需要到左子树去遍历。

③右交集：   这种情况我们需要到右子树去遍历。

比如说：我要查询Sum[4-8]的值,最终会成为:Sum总=Sum[4-4]+Sum[5-5]+Sum[6-8]，时间为log(N)。

#region 区间查询

 /// summary 

 /// 区间查询(分解)

 /// /summary 

 /// returns /returns 

 public int Query(int left, int right)

 int sum = 0;

 Query(nodeTree, left, right, ref sum);

 return sum;

 /// summary 

 /// 区间查询

 /// /summary 

 /// param name="left" 查询左边界 /param 

 /// param name="right" 查询右边界 /param 

 /// param name="node" 查询的节点 /param 

 /// returns /returns 

 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

 

4：更新操作

这个操作跟树状数组中的更新操作一样，当递归的找到待修改的节点后，改完其值然后在当前节点一路回溯，并且在回溯的过程中一

路修改父节点的附加值直到根节点，至此我们的操作就完成了，复杂度同样为logN。

#region 更新操作

 /// summary 

 /// 更新操作

 /// /summary 

 /// param name="index" /param 

 /// param name="key" /param 

 public void Update(int index, int key)

 Update(nodeTree, index, key);

 /// summary 

 /// 更新操作

 /// /summary 

 /// param name="index" /param 

 /// param name="key" /param 

 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

最后我们做个例子，在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 线段树的节点

 /// summary 

 /// 线段树的节点

 /// /summary 

 public class Node

 /// summary 

 /// 区间左端点

 /// /summary 

 public int left;

 /// summary 

 /// 区间右端点

 /// /summary 

 public int right;

 /// summary 

 /// 左孩子

 /// /summary 

 public Node leftchild;

 /// summary 

 /// 右孩子

 /// /summary 

 public Node rightchild;

 /// summary 

 /// 节点的sum值

 /// /summary 

 public int Sum;

 /// summary 

 /// 节点的Min值

 /// /summary 

 public int Min;

 /// summary 

 /// 节点的Max值

 /// /summary 

 public int Max;

 #endregion

 Node nodeTree = new Node();

 int[] nums;

 #region 根据数组构建“线段树"

 /// summary 

 /// 根据数组构建“线段树"

 /// /summary 

 /// param name="length" /param 

 public Node Build(int[] nums)

 this.nums = nums;

 return Build(nodeTree, 0, nums.Length - 1);

 #endregion

 #region 根据数组构建“线段树"

 /// summary 

 /// 根据数组构建“线段树"

 /// /summary 

 /// param name="left" /param 

 /// param name="right" /param 

 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 区间查询

 /// summary 

 /// 区间查询(分解)

 /// /summary 

 /// returns /returns 

 public int Query(int left, int right)

 int sum = 0;

 Query(nodeTree, left, right, ref sum);

 return sum;

 /// summary 

 /// 区间查询

 /// /summary 

 /// param name="left" 查询左边界 /param 

 /// param name="right" 查询右边界 /param 

 /// param name="node" 查询的节点 /param 

 /// returns /returns 

 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 更新操作

 /// summary 

 /// 更新操作

 /// /summary 

 /// param name="index" /param 

 /// param name="key" /param 

 public void Update(int index, int key)

 Update(nodeTree, index, key);

 /// summary 

 /// 更新操作

 /// /summary 

 /// param name="index" /param 

 /// param name="key" /param 

 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

}

 

 

经典算法题每日演练——第十二题 线段树 原文:经典算法题每日演练——第十二题 线段树        这一篇我们来看树状数组的加强版线段树，树状数组能玩的线段树一样可以玩，而且能玩的更好，他们在区间求和，最大，平均 等经典的RMQ问题上有着对数时间的优越表现。
经典算法题每日演练——第十五题 并查集 原文:经典算法题每日演练——第十五题 并查集     这一篇我们看看经典又神奇的并查集，顾名思义就是并起来查，可用于处理一些不相交集合的秒杀。 一：场景     有时候我们会遇到这样的场景，比如:M={1,4,6,8},N={2,4,5,7}，我的需求就是判断{1,2}是否属于同一个集合，当然实现方法 有很多，一般情况下，普通青年会做出O(MN)的复杂度，那么有没有更轻量级的复杂度呢？嘿嘿，并查集就是用来解决这个问题的。
经典算法题每日演练——第十六题 Kruskal算法 原文:经典算法题每日演练——第十六题 Kruskal算法      这篇我们看看第二种生成树的Kruskal算法，这个算法的魅力在于我们可以打一下算法和数据结构的组合拳，很有意思的。     若存在M={0,1,2,3,4,5}这样6个节点，我们知道Prim算法构建生成树是从”顶点”这个角度来思考的，然后采用“贪心思想” 来一步步扩大化，最后形成整体最优解，而Kruskal算法有点意思，它是站在”边“这个角度在思考的，首先我有两个集合。
经典算法题每日演练——第十四题 Prim算法 原文:经典算法题每日演练——第十四题 Prim算法         图论在数据结构中是非常有趣而复杂的，作为web码农的我，在实际开发中一直没有找到它的使用场景，不像树那样的频繁使用，不过还是准备 仔细的把图论全部过一遍。
经典算法题每日演练——第十七题 Dijkstra算法 原文:经典算法题每日演练——第十七题 Dijkstra算法       或许在生活中，经常会碰到针对某一个问题，在众多的限制条件下，如何去寻找一个最优解？可能大家想到了很多诸如“线性规划”，“动态规划” 这些经典策略，当然有的问题我们可以用贪心来寻求整体最优解，在图论中一个典型的贪心法求最优解的例子就莫过于“最短路径”的问题。
经典算法题每日演练——第十题 树状数组 原文:经典算法题每日演练——第十题 树状数组         有一种数据结构是神奇的，神秘的，它展现了位运算与数组结合的神奇魅力，太牛逼的，它就是树状数组，这种数据结构不是神人是发现不了的。      假如我现在有个需求，就是要频繁的求数组的前n项和，并且存在着数组中某些数字的频繁修改，那么我们该如何实现这样的需求？当然大家可以往 真实项目上靠一靠。