数据结构与算法专题——第七题 线段树
16lz
2021-02-24
这一篇我们来看树状数组的加强版线段树，树状数组能玩的线段树一样可以玩，而且能玩的更好，他们在区间求和，最大，平均等经典的RMQ问题上有着对数时间的优越表现。
一：线段树
线段树又称 "区间树”，在每个节点上保存一个区间，当然区间的划分采用折半的思想，叶子节点只保存一个值，也叫单元节点，所以最终的构造就是一个平衡的二叉树，拥有CURD的O(logN)的时间。
从图中我们可以清楚的看到 [0-10] 被划分成线段在树中的分布情况，针对区间 [0-N]，最多有 2N 个节点，由于是平衡二叉树的形式也可以像堆那样用数组来玩，不过更加耗费空间，为最多4N个节点，在针对RMQ的问题上，你可以在每个节点上增加一些sum，max，min等变量来记录求得的累加值，当然你也可以理解成动态规划的思想，由于拥有logN的时间，所以在RMQ问题上比数组更加优美。
二：代码
1: 在节点中定义一些附加值，方便我们处理RMQ问题。
/// <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;
}
2：构建(Build)
通常构建的方式有两种，要么数组要么链式，各有特点，我就采用后者，时间为O(N)。
/// <summary>
/// 根据数组构建“线段树"
/// </summary>
/// <param name="length"></param>
public Node Build(int[] nums)
{
this.nums = nums;
return Build(nodeTree, 0, nums.Length - 1);
}
/// <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;
}
3：区间查询
在线段树中，区间查询还是有点小麻烦的，存在三种情况。
① 完全包含：也就是节点的线段范围完全在查询区间的范围内，这说明我们要么到了“单元节点",要么到了一个子区间，这种情况就是我找到了查询区间的某一个子区间，直接累积该区间值就可以了。
② 左交集：这种情况我们需要到左子树去遍历。
③ 右交集：这种情况我们需要到右子树去遍历。
比如说：我要查询Sum[4-8]的值,最终会成为:Sum总=Sum[4-4]+Sum[5-5]+Sum[6-8]，时间为log(N)。
/// <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);
}
}
}
4：更新操作
这个操作跟树状数组中的更新操作一样，当递归的找到待修改的节点后，改完其值然后在当前节点一路回溯，并且在回溯的过程中一路修改父节点的附加值直到根节点，至此我们的操作就完成了，复杂度同样为logN。
/// <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;
}
}
}
最后我们做个例子，在2000000的数组空间中，寻找200-3000区间段的sum值，看看他的表现如何。
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
{
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;
}
Node nodeTree = new Node();
int[] nums;
public Node Build(int[] nums)
{
this.nums = nums;
return Build(nodeTree, 0, nums.Length - 1);
}
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;
}
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);
}
}
}
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;
}
}
}
}
更多相关文章
- 数据结构与算法专题——第二题 优先队列
- 你没有看错，爬网页数据，C# 也可以像 Jquery 那样
- 数据结构与算法专题——第十题 输入法跳不过的坎-伸展树
- 数据结构与算法专题——第十一题 Treap树
- K8S 之 通过kubeadmin安装K8S集群
- 记录一次Postgresql的repmgr高可用集群切换故障
- Windows 遍历查找文件夹文件
- 二进制部署K8s集群第25节之k8s技术点整理
- Centos7安装GreenPlum6.14 集群