投稿    登录
欢迎加入Nice Coder,与众多Coder分享经验,群号:530244901

【原创】史上最详细的线段树教程

设计之道 wjx@admin.cc 277浏览 1评论

线段树是一种树形的高级数据结构,因为noip不考这种数据结构,而且当时的代码实现能力比较差,编程水平比较低,所以高中的时候粗略的看了看,并没有真正的搞懂,虽然早已弃了算法竞赛的坑,但还是回过头去研究了一下这种高级数据结构并写下此教程,以纪念曾经奋斗在OI道路上的日子。

问题提出:

现有如下的问题,给定一个的序列,实现以下操作:

①更新序列的某个值。

②查询序列的某个区间的最小值(最大值、区间和)线段树常用于解决区间统计问题。求最值,区间和等操作均可使用该数据结构,本篇以求最小值为例。

③更新序列的某个区间内的所有值。

对于求最小值,我们很容易想到的算法就是。更新序列的某个值直接找到该值,更新,时间复杂度是O(1);区间查询直接遍历该区间,时间复杂度是O(n);区间修改的也是直接遍历该区间修改,时间复杂度是O(n),在数据量特别大,操作比较多的时候,效率是很低的。另一种解法是这样的。构建一个二维数组,a[i][j]表示区间[i,j]的最小值。这样查询操作的复杂度为O(1),但是这样的话,修改的复杂度也不低而且如果数据量特别大,O(n^2)的空间复杂度也是不容忽视的。这时候就需要我们是用线段树这种优秀的高级数据结构来解决了。

线段树:

我们以序列{5,9,7,4,6,1}为例子演示。这个序列构成的线段树是这样的。

从这颗树上我们可以了解线段树的这几个特点,线段树是一颗近似的完全二叉树,每个节点代表一个区间,节点的权值是该区间的最小值。根节点是整个区间。每个节点的左孩子是该节点所代表的的区间的左半部分,右孩子是右半部分。为方便起见,如果区间长度为奇数,则左孩子为较长的半部分。通过线段树,我们可以用O(logn)的时间复杂度完成查询和更新操作。当然,预处理的时间复杂度是O(n)。

  线段树的构建:

我们将每一个节点封装到Node类中。

class Node//节点
{
    int start;//区间的左端点
    int end;//区间的右端点
    int data;//该节点的值
    int mark = 0;//延迟更新的标记
    public Node(int start,int end)//构造方法中传入左端点和右端点
    {
        this.start = start;
        this.end = end;
    }
    void addMark(int value)//做标记
    {
        this.mark+=value;
    }
    void clearMark()
    {
        this.mark = 0;
    }
    public String toString()
    {
        return start+"-"+end;
    }
}

这个节点类有四个域,分别是区间左端点,区间右端点,节点的权值,延迟更新的标记(暂时用不到)构造方法中传入左右端点。构建线段树的时候,我们可以从根开始构建,我们注意到,这颗线段树的叶子节点区间中的元素只有一个,代表着序列的元素,所以n个元素的序列构成的线段树中的叶子节点有n个。这颗线段树虽然不是完全二叉树,但是可以通过移动变成一颗完全二叉树。n个叶子节点的完全二叉树的非叶子结点个数为n-1所以n个元素的序列构成的线段树的节点有2n-1个。这2n-1个只是有效的节点,因为我们用数组存储,所以需要给这颗近似的完全二叉树添加一些虚节点,让其变成一颗真正的完全二叉树。对于n个元素的序列构成的线段树,2x-1(x是大于等于n的最小的2的幂,比如n=6则x=8)个节点绝对够用,因为n个元素的序列构建的完全二叉树补全成为满二叉树,该满二叉树的节点个数必为2x-1。在本例中,我们为了方便起见,开了一个2*n+2长度的数组。对于完全二叉树。利用数组存储的时候,如果根节点的坐标是0,那么a[i]的左孩子的节点是a[(i<<1)+1],右孩子的节点是a[(i<<1)+2]i<<1是位运算,表示i*2。我们还注意到,线段树的节点i的权值等于i的左孩子的权值和右孩子的权值中较小的那个。我们可以通过递归来构造一颗线段树。对于一个节点,如果这个节点代表的区间的左右端点相等,说明这个节点是叶子节点,他的权值就是序列中下标为区间左端点的那个元素的值。如果这个节点不是叶子节点,那么就递归的构造这个节点的左右子树。这个节点的权值就是左右子树的权值中小的那个。代码如下:

 int[] base = {5,9,7,4,6,1};//基础数组中有六个点
    Node[] nodes = new Node[(base.length<<1)+2];//存储线段树的数组
    public void build(int index)//构造一颗线段树,传入下标
    {
        Node node = nodes[index];//取出该下标下的节点
        if(node == null)//根节点需要手动创建
        {
            nodes[index] = new Node(0,this.base.length-1);
            node = nodes[index];
        }
        if(node.start == node.end)//如果这个线段的左端点等于右端点则这个点是叶子节点
        node.data = base[node.start];else//否则递归构造左右子树
        {
            int mid = (node.start+node.end)>>1;//现在这个线段的中点
            nodes[(index<<1)+1] = new Node(node.start,mid);//左孩子线段
            nodes[(index<<1)+2] = new Node(mid+1,node.end);//右孩子线段
            build((index<<1)+1);//构造左孩子
            build((index<<1)+2);//构造右孩子
            node.data = Math.min(nodes[(index<<1)+1].data,nodes[(index<<1)+2].data);//这个节点的值等于左右孩子中较小的那个
        }
    }

线段树的区间查询:

我们知道。由2^0,2^1,2^2,2^3,2^4…..2^n 构成的序列,序列中的数字相加(每个数字只能用一次),必定可以组成从1到2^(n+1)-1内的所有的数字。所以对于一个区间的二分的子区间。子区间取交集必定可以构成原区间的任意子区间。区间查询的核心思想就是找到交集运算可以构成待查询区间的所有的子区间,并且使找到的子区间的大小尽量大。简单的说就是,找到一些区间,使其连接起来之后正好可以涵盖整个待查询的区间。我们只需要找到代表这些区间的节点的最小值即可。通过二分的思想,把查询的复杂度降到O(logn),我们在寻找这些子区间的时候,对于当前搜索到的子区间来说,有四种情况:当前区间和被查询区间无交集、待查询区间包含当前区间、当前区间包含待查询区间和当前区间和待查询区间有交集但互不包含,后两种情况可看成是同一种情况。

对于第一种情况:当前区间肯定不是待查询区间的子集,所以这时候应该返回一个极大值。表示取不到这个区间。

对于第二种情况:待查询区间包含当前区间,这时候当前区间肯定是待查询区间的子集,所以应当返回当前区间的权值。

对于第三种情况:当前区间包含待查询区间和当前区间和待查询区间有交集但互不包含,这时候当前区间的一部分是带查询区间的子集,另一部分不是,所以应当递归的去查询当前节点的左右子树,返回左右子树中较小的那个。

 /**
     *  查询某个区间的最小值
     * @param index 当前区间的下标
     * @param start 待查询的区间的左端点
     * @param end 待查询的区间的左端点
     * @return 返回当前区间在待查询区间中的部分的最小值
     */
    public int query(int index,int start,int end)
    {
        Node node = nodes[index];
        if(node.start>end||node.end<start)return Integer.MAX_VALUE;//当前区间和待查询区间没有交集,那么返回一个极大值
        if(node.start>=start&&node.end<=end)return node.data;//如果当前的区间被包含在待查询的区间内则返回当前区间的最小值
        return Math.min(query((index<<1)+1,start,end),query((index<<1)+2,start,end));//递归查询左子树和右子树
    }

举个例子,比如我们要查询区间[1,4]的最小值。先从第0个节点根节点开始。根节点包含待查询区间,属于第三种情况,需要返回根节点左右子树中较小的。也就是第1个节点和第2个节点,第1个节点是[0,2]也属于第三种情况,所以应当返回第3,4节点中较小的。第3个节点是[0,1]也属于第三种情况,所以返回第7,8个节点中较小的,第7个节点属于第一种情况,返回最大值,第8个节点属于第二种情况,返回9,第4个节点属于第2种情况,所以返回7,这时候第2个节点返回了7,第2个节点是[3,5]属于第3种情况,所以返回第5,6节点中较小的。第5个节点是[3,4]属于第2中情况,返回4,第6个节点为[5,5]属于第1种情况,所以返回无穷大,所以第2个节点返回4根节点返回4,最终的查询结果为4.

线段树的单点更新:

单点修改,需要找到该叶子节点,然后对其进行更新,叶子节点更新之后,他的父节点也需要更新,父节点仍然为左右子树中较小的那个。从根节点出发。找到当前区间的中点,判断中点和待更新的节点的大小,以此来判断是在当前节点的左子树还是右子树。然后递归更新,如果找到了叶子节点,说明当前的这个叶子节点就是我们需要改的点,直接对其更新即可。最后不要忘了更新父节点的权值。代码如下:

/**
     *
     * @param index 当前节点的下标
     * @param update 需要被更新的节点下标
     * @param date 更新增量
     */
    public void updateOne(int index,int update,int date)//更新一个节点
    {
        Node node = nodes[index];//获取这个下标所对应的的节点
        if(node.start == node.end)//
        {
            if(node.start == update)
            {
                node.data+=date;
                return;
            }
        }
        int mid = (node.start+node.end)>>1;
        if(update<=mid)updateOne((index<<1)+1,update,date);//待更新节点在左子树
        else updateOne((index<<1)+2,update,date);//待更新节点在右子树
        node.data = Math.min(nodes[(index<<1)+1].data,nodes[(index<<1)+2].data);//更新当前节点的值。
    }

线段树的区间更新:

区间修改,假设修改的值有m个,直接想到的一个办法就是执行m次单点更新,这时候的复杂度为O(mlogn)这不是我们所想看到的,假设所有的元素都更新,那么还不如直接重新构建整颗线段树。我们在这里用了一个伟大的思想,就是延迟更新,延迟更新就是,更新的时候,我不进行操作,只是标记一下这个点需要更新,在我真正使用的时候我才去更新,这在我们进行一些数据库的业务的时候,也是很重要的一个思想。我们在封装节点的时候,有一个成员变量我们前面一直没有使用,那就是mark,现在就是使用这个成员变量的时候了。我们在进行区间修改的时候,我们把这个组成这个待修改区间的所有子区间都标记上。查找组成当前待修改区间的所有子区间的方法和查询方法是一样的,也是分三种情况。在此不再赘述,代码如下:

 /**
     *
     * @param index 当前节点的下标
     * @param start 待更新的区间的左端点
     * @param end 待更新的区间的右端点
     * @param data 增量值
     */
    public void update(int index,int start,int end,int data)
    {
        Node node = nodes[index];//获取当前的节点
        if(node.start>end||node.end<start)return;//如果当前的节点代表的区间和待更新的区间毫无交集,则返回不处理。
        if(node.start>=start&&node.end<=end)//如果当前的区间被包含在待查询的区间之内,则当前区间需要被标记上
        {
            node.data+=data;
            node.addMark(data);
            return;
        }
        update((index<<1)+1,start,end,data);//更新左子树
        update((index<<1)+2,start,end,data);//更新右子树
        node.data = Math.min(nodes[(index<<1)+1].data,nodes[(index<<1)+2].data);//更新当前节点的值
    }

这样就可以了吗?显然不行,还少东西。当前这个代码,对于一次区间修改是可以的。但是如果是多次区间修改,而且修改之后没有查询,并且两次修改的区间有交集,那么会怎么样呢。比如第一次修改是把[1,4]增加2第二次修改是把[1,3]增加3,这样的话,整棵树就变成这样的。

大家注意看。[3,4]点被标记为mark为2而[3,3]点被标记为5这样的话,被标记的所有的线段,区间就有了重合。在我们进行查询的时候,比如我们查找[2,4]区间的最小值,这时候我们对第五个节点进行更新,由于第五个节点被标记为2,也就意味着他代表的区间内的所有的元素都增加了2,那么最终的最小值就是在原来的基础上增加了2,这时候我们就忽略掉了他的左子树,被标记为5的这个节点,这时候结果就可能不正确了。所以我们必须保证每时每刻被标记的节点都组成一个或多个无重叠的区间,这时候就需要在添加一个操作,就是在对某个节点的子节点进行标记的时候,把本节点的已经被标记过的部分扩展到子节点中,并把本节点的权值更新为子节点的权值的最小值。然后去除本节点的标记。下面是这个方法的代码。

 private void pushDown(int index)//把当前节点的标志值传给子节点
    {
        Node node = nodes[index];//获取该下标的节点
        if(node.mark!=0)
        {
            nodes[(index << 1) + 1].addMark(node.mark);//更新左子树的标志
            nodes[(index << 1) + 2].addMark(node.mark);//更新右子树的标志
            nodes[(index << 1) + 1].data += node.mark;//左子树的值加上标志值
            nodes[(index << 1) + 2].data += node.mark;//右子树的值加上标志值
            node.clearMark();//清除当前节点的标志值
        }
    }

然后我们的更新操作的代码也要改

 public void update(int index,int start,int end,int data)
    {
        Node node = nodes[index];//获取当前的节点
        if(node.start>end||node.end<start)return;//如果当前的节点代表的区间和待更新的区间毫无交集,则返回不处理。
        if(node.start>=start&&node.end<=end)//如果当前的区间被包含在待查询的区间之内,则当前区间需要被标记上
        {
            node.data+=data;
            node.addMark(data);
            return;
        }
        pushDown(index);///////////////////注意这里加了一句!!!在更新左右子树之前进行扩展操作!
        update((index<<1)+1,start,end,data);
        update((index<<1)+2,start,end,data);
        node.data = Math.min(nodes[(index<<1)+1].data,nodes[(index<<1)+2].data);
    }

我们说延迟更新,那么具体什么时候更新呢,就是在查询的时候。我们的查询代码也要改一下。

 public int query(int index,int start,int end)
    {
        Node node = nodes[index];
        if(node.start>end||node.end<start)return Integer.MAX_VALUE;//当前区间和待查询区间没有交集,那么返回一个极大值
        if(node.start>=start&&node.end<=end)return node.data;//如果当前的区间被包含在待查询的区间内则返回当前区间的最小值
        pushDown(index);///////////////////注意加了这一句!!!在返回左右子树的最小值之前,进行扩展操作!
        return Math.min(query((index<<1)+1,start,end),query((index<<1)+2,start,end));//递归查询左子树和右子树
    }

这样在查询的时候更新,查询操作用到什么就更新什么,这就是延迟更新,很重要的一个思想!
以上就是线段树的教程,如有疏漏,恳请指正!

转载请注明:王镜鑫的个人博客 » 【原创】史上最详细的线段树教程

喜欢 (6)or分享 (0)

您的支持是博主写作最大的动力,如果您喜欢我的文章,感觉我的文章对您有帮助,请狠狠点击下面的

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
(1)个小伙伴在吐槽
  1. 666
    2017-03-08 00:43 回复