经典算法题每日演练——第十二题线段树-阿里云开发者社区

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

等经典的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
    }
}

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

热门文章

最新文章

相关课程

相关电子书

相关实验场景

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