山东安康建设项目管理有限公司网站,金泉网推广怎么样,什么叫展示型网站,网站建设专家怎么样一、线段树
线段树又称区间树”#xff0c;在每个节点上保存一个区间#xff0c;当然区间的划分采用折半的思想#xff0c;叶子节点只保存一个值#xff0c;也叫单元节点#xff0c;所以最终的构造就是一个平衡的二叉树#xff0c;拥有 CURD 的 O(lgN)的时间。 从…一、线段树
线段树又称区间树”在每个节点上保存一个区间当然区间的划分采用折半的思想叶子节点只保存一个值也叫单元节点所以最终的构造就是一个平衡的二叉树拥有 CURD 的 O(lgN)的时间。 从图中我们可以清楚的看到[0-10]被划分成线段的在树中的分布情况针对区间[0-N]最多有 2N 个节点由于是平衡二叉树的形式也可以像堆那样用数组来玩不过更加耗费空间为最多 4N 个节点在针对 RMQ 的问题上我们常常在每个节点上增加一些 summaxmin 等变量来记录求得的累加值当然你可以理解成动态规划的思想由于拥有 logN 的时间所以在 RMQ 问题上比数组更加优美。
二、代码
1、在节点中定义一些附加值方便我们处理 RMQ 问题。 #region 线段树的节点/// summary/// 线段树的节点/// /summarypublic class Node{/// summary/// 区间左端点/// /summarypublic int left;/// summary/// 区间右端点/// /summarypublic int right;/// summary/// 左孩子/// /summarypublic Node leftchild;/// summary/// 右孩子/// /summarypublic Node rightchild;/// summary/// 节点的sum值/// /summarypublic int Sum;/// summary/// 节点的Min值/// /summarypublic int Min;/// summary/// 节点的Max值/// /summarypublic int Max;}#endregion2、构建(Build) 前面我也说了构建有两种方法数组的形式或者链的形式各有特点我就采用后者时间为 O(N)。 #region 根据数组构建“线段树/// summary/// 根据数组构建“线段树/// /summary/// param namelength/parampublic Node Build(int[] nums){this.nums nums;return Build(nodeTree, 0, nums.Length - 1);}#endregion#region 根据数组构建“线段树/// summary/// 根据数组构建“线段树/// /summary/// param nameleft/param/// param nameright/parampublic Node Build(Node node, int left, int right){//说明已经到根了当前当前节点的maxsummin值回溯时统计上一层节点区间的值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);//统计左右子树的值(minmaxsum)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;}#endregion3、区间查询 在线段树中区间查询还是有点小麻烦的存在三种情况。 ① 完全包含也就是节点的线段范围完全在查询区间的范围内这说明我们要么到了“单元节点,要么到了一个子区间这种情况就是我找到了查询区间的某一个子区间直接累积该区间值就可以了。 ② 左交集 这种情况我们需要到左子树去遍历。 ③ 右交集 这种情况我们需要到右子树去遍历。 比如说我要查询 Sum[4-8]的值,最终会成为:Sum 总Sum[4-4]Sum[5-5]Sum[6-8]时间为 log(N)。 #region 区间查询/// summary/// 区间查询(分解)/// /summary/// returns/returnspublic int Query(int left, int right){int sum 0;Query(nodeTree, left, right, ref sum);return sum;}/// summary/// 区间查询/// /summary/// param nameleft查询左边界/param/// param nameright查询右边界/param/// param namenode查询的节点/param/// returns/returnspublic 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);}}}#endregion4、更新操作 这个操作跟树状数组中的更新操作一样当递归的找到待修改的节点后改完其值然后在当前节点一路回溯并且在回溯的过程中一路修改父节点的附加值直到根节点至此我们的操作就完成了复杂度同样为 logN。 #region 更新操作/// summary/// 更新操作/// /summary/// param nameindex/param/// param namekey/parampublic void Update(int index, int key){Update(nodeTree, index, key);}/// summary/// 更新操作/// /summary/// param nameindex/param/// param namekey/parampublic 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);//在回溯的路上一路更改复杂度为lgNif (index node.left index node.right){//说明找到了节点if (node.left node.right){nums[index] key;node.Sum node.Max node.Min key;}else{//回溯时统计左右子树的值(minmaxsum)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/// 线段树的节点/// /summarypublic class Node{/// summary/// 区间左端点/// /summarypublic int left;/// summary/// 区间右端点/// /summarypublic int right;/// summary/// 左孩子/// /summarypublic Node leftchild;/// summary/// 右孩子/// /summarypublic Node rightchild;/// summary/// 节点的sum值/// /summarypublic int Sum;/// summary/// 节点的Min值/// /summarypublic int Min;/// summary/// 节点的Max值/// /summarypublic int Max;}#endregionNode nodeTree new Node();int[] nums;#region 根据数组构建“线段树/// summary/// 根据数组构建“线段树/// /summary/// param namelength/parampublic Node Build(int[] nums){this.nums nums;return Build(nodeTree, 0, nums.Length - 1);}#endregion#region 根据数组构建“线段树/// summary/// 根据数组构建“线段树/// /summary/// param nameleft/param/// param nameright/parampublic Node Build(Node node, int left, int right){//说明已经到根了当前当前节点的maxsummin值回溯时统计上一层节点区间的值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);//统计左右子树的值(minmaxsum)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/returnspublic int Query(int left, int right){int sum 0;Query(nodeTree, left, right, ref sum);return sum;}/// summary/// 区间查询/// /summary/// param nameleft查询左边界/param/// param nameright查询右边界/param/// param namenode查询的节点/param/// returns/returnspublic 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 nameindex/param/// param namekey/parampublic void Update(int index, int key){Update(nodeTree, index, key);}/// summary/// 更新操作/// /summary/// param nameindex/param/// param namekey/parampublic 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);//在回溯的路上一路更改复杂度为lgNif (index node.left index node.right){//说明找到了节点if (node.left node.right){nums[index] key;node.Sum node.Max node.Min key;}else{//回溯时统计左右子树的值(minmaxsum)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}}
