精华内容
下载资源
问答
  • 线段

    2017-08-10 20:26:24
    线段树 目录 零、前言 一、引例   1、区间最值  2、区间求和 二、线段树的基本概念  1、二叉搜索树  2、数据域  3、指针表示  4、数组表示 三、线段树的基本操作  1、构造 ...
    线段树
    目录  

    零、前言
    一、引例
          1、区间最值
          2、区间求和
    二、线段树的基本概念
         1、二叉搜索树
         2、数据域
         3、指针表示
         4、数组表示
    三、线段树的基本操作
          1、构造
          2、更新
          3、询问
    四、线段树的经典案例
           1、区间最值
           2、区间求和
           3、区间染色
           4、矩形面积并
           5、区间K大数
    五、线段树的常用技巧
           1、离散化
           2、lazy-tag
           3、子树收缩
    六、线段树的多维推广
           1、二维线段树 - 矩形树
           2、三维线段树 - 空间树
    七、线段树相关题集整理

    零、前言
        最近工作比较忙,好久没更新了,只能在过年期间抽时间写上一篇,美其名曰贺岁版,很享受写文章的过程,不想就这么断了连载,但是接下来可能会更忙,虽然很想一直坚持下去,但是臣妾做不到啊……
    一、引例
        1、区间最值
        【例题1】给定一个n(n <= 100000)个元素的数组A,有m(m <= 100000)个操作,共两种操作:
        1、Q a b         询问:表示询问区间[a, b]的最大值;
        2、C a c         更新:表示将第a个元素变成c;
        静态的区间最值可以利用RMQ来解决,但是RMQ的ST算法是在元素值给定的情况下进行的预处理,然后在O(1)时间内进行询问,这里第二种操作需要实时修改某个元素的值,所以无法进行预处理。
        由于每次操作都是独立事件,所以m次操作都无法互相影响,于是时间复杂度的改善只能在单次操作上进行优化了,我们可以试想能否将任何的区间[a, b](a < b)都拆成log(b-a+1)个小区间,然后只对这些拆散的区间进行询问,这样每次操作的最坏时间复杂度就变成log(n)了。
        2、区间求和
        【例题2】给定一个n(n <= 100000)个元素的数组A,有m(m <= 100000)个操作,共两种操作:
        1、Q a b         询问:表示询问区间[a, b]的元素和;
        2、A a b c       更新:表示将区间[a, b]的每个元素加上一个值c;
        先来看朴素算法,两个操作都用遍历来完成,单次时间复杂度在最坏情况下都是O(n)的,所以m次操作下来总的时间复杂度就是O(nm)了,复杂度太高。
        再来看看树状数组,对于第一类操作,树状数组可以在log(n)的时间内出解;然而第二类操作,还是需要遍历每个元素执行add操作,复杂度为nlog(n),所以也不可行。这个问题同样也需要利用区间拆分的思想。
        线段树就是利用了区间拆分的思想,完美解决了上述问题。
    二、线段树的基本概念
        1、二叉搜索树

        线段树是一种二叉搜索树,即每个结点最多有两棵子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。线段树的每个结点存储了一个区间(线段),故而得名。

     
    图二-1-1
        如图二-1-1所示,表示的是一个[1, 6]的区间的线段树结构,每个结点存储一个区间(注意这里的存储区间并不是指存储这个区间里面所有的元素,而是只需要存储区间的左右端点即可),所有叶子结点表示的是单位区间(即左右端点相等的区间),所有非叶子结点(内部结点)都有左右两棵子树,对于所有非叶子结点,它表示的区间为[l, r],那么令mid为(l + r)/2的下整,则它的左儿子表示的区间为[l, mid],右儿子表示的区间为[mid+1, r]。基于这个特性,这种二叉树的内部结点,一定有两个儿子结点,不会存在有左儿子但是没有右儿子的情况。
        基于这种结构,叶子结点保存一个对应原始数组下标的值,由于树是一个递归结构,两个子结点的区间并正好是父结点的区间,可以通过自底向上的计算在每个结点都计算出当前区间的最大值。
        需要注意的是,基于线段树的二分性质,所以它是一棵平衡树,树的高度为log(n)。
        2、数据域
        了解线段树的基本结构以后,看看每个结点的数据域,即需要存储哪些信息。
        首先,既然线段树的每个结点表示的是一个区间,那么必须知道这个结点管辖的是哪个区间,所以其中最重要的数据域就是区间左右端点[l, r]。然而有时候为了节省全局空间,往往不会将区间端点存储在结点中,而是通过递归的传参进行传递,实时获取。
        再者,以区间最大值为例,每个结点除了需要知道所管辖的区间范围[l, r]以外,还需要存储一个当前区间内的最大值max。
     
    图二-2-1
        以数组A[1:6] = [1 7 2 5 6 3]为例,建立如图二-2-1的线段树,叶子结点的max域为数组对应下标的元素值,非叶子结点的max域则通过自底向上的计算由两个儿子结点的max域比较得出。这是一棵初始的线段树,接下来讨论下线段树的询问和更新操作。
        在询问某个区间的最大值时,我们一定可以将这个区间拆分成log(n)个子区间,并且这些子区间一定都能在线段树的结点上找到(这一点下文会着重讲解),然后只要比较这些结点的max域,就能得出原区间的最大值了,因为子区间数量为log(n),所以时间复杂度是O( log(n) )。
        更新数组某个元素的值时我们首先修改对应的叶子结点的max域,然后修改它的父结点的max域,以及祖先结点的max域,换言之,修改的只是线段树的叶子结点到根结点的某一条路径上的max域,又因为树高是log(n),所以这一步操作的时间复杂度也是log(n)的。
        3、指针表示
        接下来讨论一下结点的表示法,每个结点可以看成是一个结构体指针,由数据域和指针域组成,其中指针域有两个,分别为左儿子指针和右儿子指针,分别指向左右子树;数据域存储对应数据,根据情况而定(如果是求区间最值,就存最值max;求区间和就存和sum),这样就可以利用指针从根结点进行深度优先遍历了。
        以下是简单的线段树结点的C++结构体:    
        struct treeNode {
            Data data;                 // 数据域
            treeNode *lson, *rson;     // 指针域
        }*root;

        4、数组表示
        实际计算过程中,还有一种更加方便的表示方法,就是基于数组的静态表示法,需要一个全局的结构体数组,每个结点对应数组中的一个元素,利用下标索引。
        例如,假设某个结点在数组中下标为p,那么它的左儿子结点的下标就是2*p,右儿子结点的下标就是2*p+1(类似于一般数据结构书上说的堆在数组中的编号方式),这样可以将所有的线段树结点存储在相对连续的空间内。之所以说是相对连续的空间,是因为有些下标可能永远用不到。
        还是以长度为6的数组为例,如图二-4-1所示,红色数字表示结点对应的数组下标,由于树的结构和编号方式,导致数组的第10、11位置空缺。
     
    图二-4-1
        这种存储方式可以不用存子结点指针,取而代之的是当前结点的数组下标索引,以下是数组存储方式的线段树结点的C++结构体: 
        struct treeNode {        
            Data data;                         // 数据域
            int pid;                           // 数组下标索引
            int lson() { return pid << 1; }        
            int rson() { return pid<<1|1; }    // 利用位运算加速获取子结点编号
        }nodes[ MAXNODES ];
        接下来我们关心的就是MAXNODES的取值了,由于线段树是一种二叉树,所以当区间长度为2的幂时,它正好是一棵满二叉树,数组存储的利用率达到最高(即100%),根据等比数列求和可以得出,满二叉树的结点个数为2*n-1,其中n为区间长度(由于C++中数组长度从0计数,编号从1开始,所以MAXNODES要取2*n)。那么是否对于所有的区间长度n都满足这个公式呢?答案是否定的,当区间长度为6时,最大的结点编号为13,而公式算出来的是12(2*6)。
        那么 MAXNODES 取多少合适呢?
        为了保险起见,我们可以先找到比n大的最小的二次幂,然后再套用等比数列求和公式,这样就万无一失了。举个例子,当区间长度为6时,MAXNODES = 2 * 8;当区间长度为1000,则MAXNODES = 2 * 1024;当区间长度为10000,MAXNODES = 2 * 16384。至于为什么可以这样,明眼人一看便知。
    三、线段树的基本操作
        线段树的基本操作包括构造、更新、询问,都是深度优先搜索的过程。
        1、构造
        线段树的构造是一个二分递归的过程,封装好了之后代码非常简洁,总体思路就是从区间[1, n]开始拆分,拆分方式为二分的形式,将左半区间分配给左子树,右半区间分配给右子树,继续递归构造左右子树。
        当区间拆分到单位区间时(即遍历到了线段树的叶子结点),则执行回溯。回溯时对于任何一个非叶子结点需要根据两棵子树的情况进行统计,计算当前结点的数据域,详见注释4。
        void segtree_build(int p, int l, int r) {
            nodes[p].reset(p, l, r);                  // 注释1
            if (l < r) {
                int mid = (l + r) >> 1;
                segtree_build(p<<1, l, mid);          // 注释2
                segtree_build(p<<1|1, mid+1, r);      // 注释3
                nodes[p].updateFromSon();             // 注释4
            }
        }
        注释1:初始化第p个结点的数据域,根据实际情况实现reset函数
        注释2:递归构造左子树
        注释3:递归构造右子树
        注释4:回溯,利用左右子树的信息来更新当前结点,updateFromSon这个函数的实现需要根据实际情况进行求解,在第四节会详细讨论
        构造线段树的调用如下:segtree_build(1, 1, n);
        2、更新
        线段树的更新是指更新数组在[x, y]区间的值,具体更新这件事情是做了什么要根据具体情况而定,可以是将[x, y]区间的值都变成val(覆盖),也可以是将[x, y]区间的值都加上val(累加)。
        更新过程采用二分,将[1, n]区间不断拆分成一个个子区间[l, r],当更新区间[x, y]完全覆盖被拆分的区间[l, r]时,则更新管辖[l, r]区间的结点的数据域,详见注释2和注释3。
        void segtree_insert(int p, int l, int r, int x, int y, ValueType val) {
            if!is_intersect(l, r, x, y) ) {              // 注释1
                return ;
            } 
            if( is_contain(l, r, x, y) ) {                 // 注释2
                nodes[p].updateByValue(val);               // 注释3
                return ;
            } 
            nodes[p].giveLazyToSon();                      // 注释4
                        int mid = (l + r) >> 1
            segtree_insert(p<<1, l, mid, x, y, val);       // 注释5
            segtree_insert(p<<1|1, mid+1, r, x, y, val);   // 注释6
            nodes[p].updateFromSon();                      // 注释7
        }
        注释1:区间[l, r]和区间[x, y]无交集,直接返回 
        注释2:区间[x, y]完全覆盖[l, r]
        注释3:更新第p个结点的数据域,updateByValue这个函数的实现需要根据具体情况而定,会在第四节进行详细讨论
        注释4:这里先卖个关子,参见第五节的lazy-tag
        注释5:递归更新左子树
        注释6:递归更新右子树
        注释7:回溯,利用左右子树的信息来更新当前结点
        更新区间[x, y]的值为val的调用如下:segtree_insert(1, 1, n, x, y, val);
        3、询问
        线段树的询问和更新类似,大部分代码都是一样的,只有红色部分是不同的,同样是将大区间[1, n]拆分成一个个小区间[l, r],这里需要存储一个询问得到的结果ans,当询问区间[x, y]完全覆盖被拆分的区间[l, r]时,则用管辖[l, r]区间的结点的数据域来更新ans,详见注释1的mergeQuery接口
        void segtree_query (int p, int l, int r, int x, int y, treeNode& ans) {
            if!is_intersect(l, r, x, y) ) {
                      return ;
            }
            if( is_contain(l, r, x, y) ) {
                ans.mergeQuery(p);                          // 注释1
                return;
            }
            nodes[p].giveLazyToSon();
                        int mid = (l + r) >> 1
            segtree_query(p<<1, l, mid, x, y, ans);
            segtree_query(p<<1|1, mid+1, r, x, y, ans);
            nodes[p].updateFromSon();                       // 注释2
        }
        注释1:更新当前解ans,会在第四节进行详细讨论
        注释2:和更新一样的代码,不再累述
    四、线段树的经典案例
        线段树的用法千奇百怪,接下来介绍几个线段树的经典案例,加深对线段树的理解。
        1、区间最值
        区间最值是最常见的线段树问题,引例中已经提到。接下来从几个方面来讨论下区间最值是如何运作的。
        数据域:
            int pid;               // 数组索引
            int l, r;              // 结点区间(一般不需要存储)       
            ValyeType max;         // 区间最大值
        初始化:
            void treeNode::reset(int p, int l, int r) {
                pid = p;
                max = srcArray[l]; // 初始化只对叶子结点有效
            }
       单点更新:
            void treeNode::updateByValue(ValyeType val) {
                max = val;
            }
        合并结点:
            void treeNode::mergeQuery(int p) {
                max = getmax( max, nodes[p].max );
            }
        回溯统计:
            void treeNode::updateFromSon() {
                max = nodes[ lson() ].max;
                mergeQuery( rson() );
            }
        结合上一节线段树的基本操作,在构造线段树的时候,对每个结点执行了一次初始化,初始化同时也是单点更新的过程,然后在回溯的时候统计,统计实质上是合并左右结点的过程,合并结点做的事情就是更新最大值;询问就是将给定区间拆成一个个能够在线段树结点上找到的区间,然后合并这些结点的过程,合并的结果ans一般通过引用进行传参,或者作为全局变量,不过尽量避免使用全局变量
        2、区间求和
        区间求和问题一般比区间最值稍稍复杂一点,因为涉及到区间更新和区间询问,如果更新和询问都只遍历到询问(更新)区间完全覆盖结点区间的话,会导致计算遗留,举个例子来说明。
        用一个数据域sum来记录线段树结点区间上所有元素的和,初始化所有结点的sum值都为0,然后在区间[1, 4]上给每个元素加上4,如图四-2-1所示:
     
    图四-2-1
        图中[1, 4]区间完全覆盖[1, 3]和[4, 4]两个子区间,然后分别将值累加到对应结点的数据域sum上,再通过回溯统计sum和,最后得到[1, 6]区间的sum和为16,看上去貌似天衣无缝,但是实际上操作一多就能看出这样做是有缺陷的。例如当我们要询问[3, 4]区间的元素和时,在线段树结点上得到被完全覆盖的两个子区间[3, 3]和[4, 4],累加区间和为0 + 4 = 4,如图四-2-2所示。
      
    图四-2-2
        这是因为在进行区间更新的时候,由于[1, 4]区间完全覆盖[1, 3]区间,所以我们并没有继续往下遍历,而是直接在[1, 3]这个结点进行sum值的计算,计算完直接回溯。等到下一次访问[3, 3]的时候,它并不知道之前在3号位置上其实是有一个累加值4的,但是如果每次更新都更新到叶子结点,就会使得更新的复杂度变成O(n),违背了使用线段树的初衷,所以这里需要引入一个lazy-tag的概念。
        所谓lazy-tag,就是在某个结点打上一个“懒惰标记”,每次更新的时候只要更新区间完全覆盖结点区间,就在这个结点打上一个lazy标记,这个标记的值就是更新的值,表示这个区间上每个元素都有一个待累加值lazy,然后计算这个结点的sum,回溯统计sum。
        当下次访问到有lazy标记的结点时,如果还需要往下访问它的子结点,则将它的lazy标记传递给两个子结点,自己的lazy标记置空。
        这就是为什么在之前在讲线段树的更新和询问的时候有一个函数叫giveLazyToSon了。接下来看看一些函数的实现。
        数据域:
            int pid;               // 数组索引
            int len;               // 结点区间长度
            ValyeType sum;         // 区间元素和 
            ValyeType lazy;        // lazy tag
        初始化:
            void treeNode::reset(int p, int l, int r) {
                pid = p;
                len = r - l + 1;
                sum = lazy = 0;
            }
        单点更新:
            void treeNode::updateByValue(ValyeType val) {
                lazy += val;
                sum += val * len;
            }
        lazy标记继承:
            void treeNode::giveLazyToSon() {
                if( lazy ) {
                   nodes[ lson() ].updateByValue(lazy);
                   nodes[ rson() ].updateByValue(lazy);
                   lazy = 0;
                }
            }
        合并结点:
            void treeNode::mergeQuery(int p) {
                sum += nodes[p].sum;
            }
        回溯统计
            void treeNode::updateFromSon() {
                sum = nodes[ lson() ].sum;
                mergeQuery( rson() );
            }
        对比区间最值,区间求和的几个函数的实现主旨是一致的,因为引入了lazy-tag,所以需要多实现一个函数用于lazy标记的继承,在进行区间求和的时候还需要记录一个区间的长度len,用于更新的时候计算累加的sum值。
        3、区间染色
        【例题3】给定一个长度为n(n <= 100000)的木板,支持两种操作:
        1、P a b c       将[a, b]区间段染色成c;
        2、Q a b         询问[a, b]区间内有多少种颜色;
        保证染色的颜色数少于30种。
        对比区间求和,不同点在于区间求和的更新是对区间和进行累加;而这类染色问题则是对区间的值进行替换(或者叫覆盖),有一个比较特殊的条件是颜色数目小于30。
        我们是不是要将30种颜色的有无与否都存在线段树的结点上呢?答案是肯定的,但是这样一来每个结点都要存储30个bool值,空间太浪费,而且在计算合并操作的时候有一步30个元素的遍历,大大降低效率。然而30个bool值正好可以压缩在一个int32中,利用二进制压缩可以用一个32位的整型完美的存储30种颜色的有无情况。
        因为任何一个整数都可以分解成二进制整数,二进制整数的每一位要么是0,要么是1。二进制整数的第i位是1表示存在第i种颜色;反之不存在。
        数据域需要存一个颜色种类的位或和colorBit,一个颜色的lazy标记表示这个结点被完全染成了lazy,基本操作的几个函数和区间求和非常像,这里就不出示代码了。
        和区间求和不同的是回溯统计的时候,对于两个子结点的数据域不再是加和,而是位或和。
        4、矩形面积并
        【例题4】给定n(n <= 100000)个平行于XY轴的矩形,求它们的面积并。如图四-4-1所示。
     
    图四-4-1
        这类二维的问题同样也可以用线段树求解,核心思想是降维,将某一维套用线段树,另外一维则用来枚举。具体过程如下:
        第一步:将所有矩形拆成两条垂直于x轴的线段,平行x轴的边可以舍去,如图四-4-2所示。
     
    图四-4-2
        第二步:定义矩形的两条垂直于x轴的边中x坐标较小的为入边,x坐标较大的为出边,入边权值为+1,出边权值为-1,并将所有的线段按照x坐标递增排序,第i条线段的x坐标记为X[i],如图四-4-3所示。
     
    图四-4-3
        第三步:将所有矩形端点的y坐标进行重映射(也可以叫离散化),原因是坐标有可能很大而且不一定是整数,将原坐标映射成小范围的整数可以作为数组下标,更方便计算,映射可以将所有y坐标进行排序去重,然后二分查找确定映射后的值,离散化的具体步骤下文会详细讲解。如图四-4-4所示,蓝色数字表示的是离散后的坐标,即1、2、3、4分别对应原先的5、10、23、25(需支持正查和反查)。假设离散后的y方向的坐标个数为m,则y方向被分割成m-1个独立单元,下文称这些独立单元为“单位线段”,分别记为<1-2>、<2-3>、<3-4>。
     
    图四-4-4
        第四步:以x坐标递增的方式枚举每条垂直线段,y方向用一个长度为m-1的数组来维护“单位线段”的权值,如图四-4-5所示,展示了每条线段按x递增方式插入之后每个“单位线段”的权值。
        当枚举到第i条线段时,检查所有“单位线段”的权值,所有权值大于零的“单位线段”的实际长度之和(离散化前的长度)被称为“合法长度”,记为L,那么(X[i] - X[i-1]) * L,就是第i条线段和第i-1条线段之间的矩形面积和,计算完第i条垂直线段后将它插入,所谓"插入"就是利用该线段的权值更新该线段对应的“单位线段”的权值和(这里的更新就是累加)。
     
    图四-4-5
        如图四-4-6所示:红色、黄色、蓝色三个矩形分别是3对相邻线段间的矩形面积和,其中红色部分的y方向由<1-2>、<2-3>两个“单位线段”组成,黄色部分的y方向由<1-2>、<2-3>、<3-4>三个“单位线段”组成,蓝色部分的y方向由<2-3>、<3-4>两个“单位线段”组成。特殊的,在计算蓝色部分的时候,<1-2>部分的权值由于第3条线段的插入(第3条线段权值为-1)而变为零,所以不能计入“合法长度”。
        以上所有相邻线段之间的面积和就是最后要求的矩形面积并。
     
    图四-4-6
        那么这里带来几个问题:
        1、是否任意相邻两条垂直x轴的线段之间组成的封闭图形都是矩形呢?答案是否定的,如图四-4-7所示,其中绿色部分为四个矩形的面积并中的某块有效部分,它们同处于两条相邻线段之间,但是中间有空隙,所以它并不是一个完整的矩形。
        2、每次枚举一条垂直线段的时候,需要检查所有“单位线段”的权值,如果用数组维护权值,那么这一步检查操作是O(m)的,所以总的时间复杂度为O(nm),其中n表示垂直线段的个数,复杂度太大需要优化。
     
    图四-4-7
        优化自然就是用线段树了,之前提到了降维的思想,x方向我们继续采用枚举,而y方向的“单位线段”则可以采用线段树来维护,和一般问题一样,首先讨论数据域。
        数据域:
            int pid;        // 数组索引
            int l, r;       // 结点代表的“单位线段”区间[l, r] (注意,l和r均为离散后的下标)
            int cover;      // [l, r]区间被完全覆盖的次数 
            int len;        // 该结点表示的区间内的合法长度
        注意,这次的线段树和之前的线段树稍微有点区别,就是叶子结点的区间端点不再相等,而是相差1,即l+1 == r。因为一个点对于计算面积来说是没有意义的。
        算法采用深度优先搜索的后序遍历,记插入线段为[a, b, v],其中[a, b]为线段的两个端点,是离散化后的坐标;v是+1或-1,代表是入边还是出边,每次插入操作二分枚举区间,当线段树的结点代表的区间被插入区间完全覆盖时,将权值v累加到结点的cover域上。由于是后续遍历,在子树全部遍历完毕后需要进行统计。插入过程修改cover,同时更新len。
        回溯统计过程对cover域分情况讨论:
            当cover > 0时,表示该结点代表的区间至少有一条入边没有被出边抵消,换言之,这块区间都应该在“合法长度”之内,则 len = Y[r] - Y[l](Y[i]代表离散前第i大的点的y坐标);更加通俗的理解是至少存在一个矩形的入边被扫描到了,而出边还未被扫描到,所以这块面积需要被计算进来。
            当cover等于0时,如果该区间是一个单位区间(即上文所说的“单位线段”,l+1 == r,也是线段树的叶子结点),则 len = 0;否则,len需要由左子树和右子树的计算结果得出,又因为是后序遍历,所以左右子树的len都已经计算完毕,从而不需要再进行递归求解,直接将左右儿子的len加和就是答案,即len = lson.len + rson.len。
     
    图四-4-8
        图四-4-8所示为上述例子的初始线段树,其中根结点管辖的区间为[1, 4],代表"单位线段”的两个端点。对于线段树上任何一棵子树而言,根结点管辖区间为[l, r],并且mid = (l + r) / 2,那么如果它不是叶子结点,则它的左子树管辖的区间就是[l, mid],右子树管辖的区间就是[mid, r]。叶子结点管辖区间的左右端点之差为1(和之前的线段树的区间分配方式稍有不同)。
        这样就可以利用二分,在O(n)的时间内递归构造初始的线段树。
     
    图四-4-9
        图四-4-9所示为插入第一条垂直线段[1, 3, 1](插入区间[1, 3],权值为1)后的情况,插入过程类似建树过程,二分递归执行插入操作,当插入区间完全覆盖线段树结点区间时,将权值累加到对应结点(图中绿色箭头指向的结点)的cover域上;否则,继续递归左右子树。然后进行自底向上的统计,统计的是len的值。
        [2, 4]这个结点的cover域为0,所以它的len等于两棵子树的len之和,[1, 4]亦然。
     
    图四-4-10
        图四-4-10所示为插入第二条垂直线段[2, 4, 1](插入区间[2, 4],权值为1)后的情况,只需要修改一个结点(图中绿色箭头指向的结点)的cover域,该结点的两棵子树不需要再进行递归计算,回溯的时候,计算根结点len值时,由于根结点的cover域为0,所以它的len等于左右子树的len之和。
     
    图四-4-11
        图四-4-11所示为插入第三条垂直线段[1, 3, -1](插入区间[1, 3],权值为-1)后的情况,直观的看,现在Y方向只有[2, 4]一条线段了,所以根结点的len就是Y[4] - Y[2] = 15。
           
        讲完插入,就要谈谈询问。在每次插入之前,需要询问之前插入的线段中,在y方向的“合法长度”L,根据线段树结点的定义,y方向“合法长度”总和其实就是根结点的len,所以这一步询问操作其实是O(1)的,在插入过程中已经实时计算出来,再加上插入的O(log n)的时间复杂度,已经完美解决了上述复杂度太大的问题了。
        5、区间K大数
        【例题5】给定n(n <= 100000)个数的数组,然后m(m <= 100000)条询问,询问格式如下:
             1、l r k                       询问[l, r]的第K大的数的值       
        这是一个经典的面试题,利用了线段树划分区间的思想,线段树的每个结点存的不只是区间端点,而是这个区间内所有的数,并且是按照递增顺序有序排列的,建树过程是一个归并排序的过程,从叶子结点自底向上进行归并,对于一个长度为6的数组[4, 3, 2, 1, 5, 6],建立线段树如图四-5-1所示。
     
    图四-5-1
        从图中可以看出,线段树的任何一个结点存储了对应区间的数,并且进行有序排列,所以根结点存储的一定是一个长度为数组总长的有序数组,叶子结点存储的递增序列为原数组元素。
        每次询问,我们将给定区间拆分成一个个线段树上的子区间,然后二分枚举答案T,再利用二分查找统计这些子区间中大于等于T的数的个数,从而确定T是否是第K大的。
        对于区间K大数的问题,还有很多数据结构都能解决,这里仅作简单介绍。
    五、线段树的常用技巧
        1、离散化
        在讲解矩形面积并的时候曾经提了一下离散化,现在再详细的说明一下,所谓离散化就是将无限的个体映射到有限的个体中,从而提高算法效率。
        举个简单的例子,一个实数数组,我想很快的得到某个数在整个数组里是第几大的,并且询问数很多,不允许每次都遍历数组进行比较。
        那么,最直观的想法就是对原数组先进行一个排序,询问的时候只需要通过二分查找就能在O( log(n) )的时间内得出这个数是第几大的了,离散化就是做了这一步映射。
        对于一个数组[1.6, 7.8, 5.5, 11.1111, 99999, 5.5],离散化就是将原来的实数映射成整数(下标),如图五-1-1所示:
     
    图五-1-1
        这样就可以将原来的实数保存在一个有序数组中,询问第K大的是什么称为正查,可以利用下标索引在O(1)的时间内得到答案;询问某个数是第几大的称为反查,可以利用二分查找或者Hash得到答案,复杂度取决于具体算法,一般为O(log(n))。
        2、lazy-tag
        这个标记一般用于处理线段树的区间更新。
        线段树在进行区间更新的时候,为了提高更新的效率,所以每次更新只更新到更新区间完全覆盖线段树结点区间为止,这样就会导致被更新结点的子孙结点的区间得不到需要更新的信息,所以在被更新结点上打上一个标记,称为lazy-tag,等到下次访问这个结点的子结点时再将这个标记传递给子结点,所以也可以叫延迟标记。
        3、子树收缩
        子树收缩是子树继承的逆过程,子树继承是为了两棵子树获得父结点的信息;而子树收缩则是在回溯的时候,如果两棵子树拥有相同数据的时候在将数据传递给父结点,子树的数据清空,这样下次在访问的时候就可以减少访问的结点数。
    六、线段树的多维推广
           1、二维线段树 - 矩形树
        线段树是处理区间问题的,二维线段树就是处理平面问题的了,曾经写过一篇二维线段树的文章,就不贴过来了,直接给出传送门:二维线段树
           2、三维线段树 - 空间树
        线段树-二叉树,二维线段树-四叉树,三维线段树自然就是八叉树了,分割的是空间,一般用于三维计算几何,当然也不一定用在实质的空间内的问题。
        比如需要找出身高、体重、年龄在一定范围内并且颜值最高的女子,就可以用三维线段树(三维空间最值问题),嘿嘿嘿!!!
    七、线段树相关题集整理
    区间最值
    I Hate It                           ★☆☆☆☆   最值-单点更新,批量查询
    Sticks Problem                      ★★☆☆☆   最值-二分枚举 + 批量查询
    Balanced Lineup                     ★★☆☆☆   最值-批量查询
    Frequent values                     ★★☆☆☆   最值-批量查询
    Billboard                           ★★☆☆☆   最值-单点更新、批量查询
    Huge Mission                        ★★☆☆☆   最值-区间更新,单点询问
    Gcd & Lcm game                      ★★★☆☆   利用LCM和GCD的素拆表示
    Another LIS                         ★★★★☆   最值(线段树)+ 树状数组
    WorstWeather Ever                   ★★★★☆   很好的逻辑题,线段树维护最值
    Special Subsequence                 ★★★★☆   动态规划 + 区间最值
    Minimizing maximizer                ★★★★☆   动态规划 + 区间最值
    区间求和
    A Simple Problem with Integers      ★☆☆☆☆   求和-区间更新,区间求和
    Thermal Death of the Universe       ★☆☆☆☆   求和-区间更新,区间求和
    Buy Tickets                         ★★☆☆☆   求和-单点更新,区间求和
    Turing Tree                         ★★★☆☆   求和-离线区间求和
    Help with Intervals                 ★★★☆☆   求和-异或的应用
    Sequence operation                  ★★★☆☆   求和-异或的应用
    Coder                               ★★★☆☆   求和-线段树 + 树状数组
    区间染色
    Just a Hook                         ★☆☆☆☆   染色-批量染色,单次统计
    Mayor's posters                     ★☆☆☆☆   染色-批量染色,单次统计(离散化)
    Count Color                         ★★☆☆☆   染色-批量染色,批量查询
    A Corrupt Mayor's Performance Art   ★★☆☆☆   染色-批量染色,批量查询
    Horizontally Visible Segments       ★★★☆☆   染色-批量染色,子树收缩
    Can you answer these queries?       ★★★☆☆   染色-批量染色,子树收缩
    Color the Ball                      ★★★☆☆   染色-最长连续区间
    LCIS                                ★★★☆☆   染色-最长连续递增子序列
    Memory Control                      ★★★★☆   染色-内存分配
    Man Down                            ★★★☆☆   动态规划 + 区间染色
    矩形问题
    Atlantis                            ★☆☆☆☆   离散化 + 矩形面积并
    City Horizon                        ★☆☆☆☆   矩形面积并
    Paint the Wall                      ★☆☆☆☆   矩形面积并
    Posters                             ★★☆☆☆   中空矩形面积并
    Covered Area                        ★★☆☆☆   矩形面积并
    Picture                             ★★★☆☆   矩形周长
    Colourful Rectangle                 ★★★☆☆   多色矩形面积并
    End of Windless Days                ★★★☆☆   投影三角换算 + 矩形面积并
    区间K大数
    K-th Number                         ★★★☆☆   区间K大数
    Kth number                          ★★★☆☆   区间K小数
    Feed the dogs                       ★★★☆☆   区间K大数
    二维线段树
    Luck and Love                       ★★☆☆☆   二维最值
    Mosaic                              ★★☆☆☆   二维最值
    Matrix Searching                    ★★☆☆☆   二维最值
    人一我百!人十我万!永不放弃~~~怀着自信的心,去追逐梦想。

    展开全文
  • 线段树入门

    2018-08-01 11:23:58
     最近学了一下线段树,在网上看到两篇写的特别好的博,讲解的很透彻,分别是《线段树从零开始》和《线段树详解》,By 岩之痕,应该是目前看到的最好的线段树总结了,放在一起合了一下,也分...

    欢迎访问https://blog.csdn.net/lxt_Lucia~~

    宇宙第一小仙女\(^o^)/~~萌量爆表求带飞=≡Σ((( つ^o^)つ~ dalao们点个关注呗~~

     

     

    摘要

           最近学了一下线段树,在网上看到两篇写的特别好的博,讲解的很透彻,分别是《线段树从零开始》《线段树详解》By 岩之痕,应该是目前看到的最好的线段树总结了,放在一起合了一下,也分享给大家。

     

     

    原文如下:

     


    线段树从零开始

     

    一. 为什么需要线段树?

    题目一:
    10000个正整数,编号1到10000,用A[1],A[2],A[10000]表示。
    修改:无
    统计:1.编号从L到R的所有数之和为多少? 其中1<= L <= R <= 10000.

     

    方法一:对于统计L,R ,需要求下标从L到R的所有数的和,从L到R的所有下标记做[L..R],问题就是对A[L..R]进行求和。

    这样求和,对于每个询问,需要将(R-L+1)个数相加。

     

    方法二:更快的方法是求前缀和,令 S[0]=0, S[k]=A[1..k] ,那么,A[L..R]的和就等于S[R]-S[L-1],

    这样,对于每个询问,就只需要做一次减法,大大提高效率。

     

     

    题目二:
    10000个正整数,编号从1到10000,用A[1],A[2],A[10000]表示。
    修改:1.将第L个数增加C (1 <= L <= 10000)
    统计:1.编号从L到R的所有数之和为多少? 其中1<= L <= R <= 10000.


    再使用方法二的话,假如A[L]+=C之后,S[L],S[L+1],,S[R]都需要增加C,全部都要修改,见下表。

     

      方法一 方法二
    A[L]+=C 修改1个元素 修改R-L+1个元素
    求和A[L..R] 计算R-L+1个元素之和 计算两个元素之差

     

    从上表可以看出,方法一修改快,求和慢。 方法二求和快,修改慢。

    那有没有一种结构,修改和求和都比较快呢?答案当然是线段树。

     

    二. 线段树的点修改

     

    上面的问题二就是典型的线段树点修改。

    线段树先将区间[1..10000]分成不超过4*10000个子区间,对于每个子区间,记录一段连续数字的和。

    之后,任意给定区间[L,R],线段树在上述子区间中选择约2*log2(R-L+1)个拼成区间[L,R]。

    如果A[L]+=C ,线段树的子区间中,约有log2(10000)个包含了L,所以需要修改log2(10000)个。

     

    于是,使用线段树的话,

    A[L]+=C 需要修改log2(10000) 个元素

    求和A[L...R]需要修改2*log2(R-L+1) <= 2 * log2(10000) 个元素。

    log2(10000) < 14 所以相对来说线段树的修改和求和都比较快。

     

    问题一:开始的子区间是怎么分的?

    首先是讲原始子区间的分解,假定给定区间[L,R],只要L < R ,线段树就会把它继续分裂成两个区间。

    首先计算 M = (L+R)/2,左子区间为[L,M],右子区间为[M+1,R],然后如果子区间不满足条件就递归分解。

    以区间[1..13]的分解为例,分解结果见下图:

     

     

    问题二:给定区间【L,R】,如何分解成上述给定的区间?

    对于给定区间[2,12]要如何分解成上述区间呢?

     

    分解方法一:自下而上合并——利于理解

    先考虑树的最下层,将所有在区间[2,12]内的点选中,然后,若相邻的点的直接父节点是同一个,那么就用这个父节点代替这两个节点(父节点在上一层)。这样操作之后,本层最多剩下两个节点。若最左侧被选中的节点是它父节点的右子树,那么这个节点会被剩下。若最右侧被选中的节点是它的父节点的左子树,那么这个节点会被剩下。中间的所有节点都被父节点取代。对最下层处理完之后,考虑它的上一层,继续进行同样的处理。

     

    下图为n=13的线段树,区间[2,12],按照上面的叙述进行操作的过程图:

    由图可以看出:在n=13的线段树中,[2,12]=[2] + [3,4] + [5,7] + [8,10] + [11,12] 。

     

    分解方法二:自上而下分解——利于计算

    首先对于区间[1,13],计算(1+13)/2 = 7,于是将区间[2,12]“切割”成了[2,7]和[8,12]。

    其中[2,7]处于节点[1,7]的位置,[2,7] < [1,7] 所以继续分解,计算(1+7)/2 = 4, 于是将[2,7] 切割成[2,4]和[5,7]。

    [5,7]处于节点[5,7]的位置,所以不用继续分解,[2,4]处于区间[1,4]的位置,所以继续分解成[2]和[3,4]。

    最后【2】 < 【1,2】,所以计算(1+2)/2=1 ,将【2】用1切割,左侧为空,右侧为【2】

    当然程序是递归计算的,不是一层一层计算的,上图只表示计算方法,不代表计算顺序。

     

     

    问题三:如何进行区间统计?

    假设这13个数为1,2,3,4,1,2,3,4,1,2,3,4,1. 在区间之后标上该区间的数字之和:

    如果要计算[2,12]的和,按照之前的算法:

    [2,12]=[2] + [3,4] + [5,7] + [8,10] + [11,12]

      29  = 2 + 7 + 6 + 7 + 7

    计算5个数的和就可以算出[2,12]的值。

     

    问题四:如何进行点修改?

    假设把A[6]+=7 ,看看哪些区间需要修改?[6],[5,6],[5,7],[1,7],[1,13]这些区间全部都需要+7.其余所有区间都不用动。

    于是,这颗线段树中,点修改最多修改5个线段树元素(每层一个)。

    下图中,修改后的元素用蓝色表示。

    问题五:存储结构是怎样的?

     

    线段树是一种二叉树,当然可以像一般的树那样写成结构体,指针什么的。

    但是它的优点是,它也可以用数组来实现树形结构,可以大大简化代码。

    数组形式适合在编程竞赛中使用,在已经知道线段树的最大规模的情况下,直接开足够空间的数组,然后在上面建立线段树。
    简单的记法: 足够的空间 = 数组大小n的四倍。 
    实际上足够的空间 =  (n向上扩充到最近的2的某个次方)的两倍。
    举例子:假设数组长度为5,就需要5先扩充成8,8*2=16.线段树需要16个元素。如果数组元素为8,那么也需要16个元素。
    所以线段树需要的空间是n的两倍到四倍之间的某个数,一般就开4*n的空间就好,如果空间不够,可以自己算好最大值来省点空间。
     

    怎么用数组来表示一颗二叉树呢?假设某个节点的编号为v,那么它的左子节点编号为2*v,右子节点编号为2*v+1。

    然后规定根节点为1.这样一颗二叉树就构造完成了。通常2*v在代码中写成 v<<1 。 2*v+1写成 v<<1|1 。

     

    问题六:代码中如何实现?

    (0)定义:

    #define maxn 100007  //元素总个数  
    int Sum[maxn<<2];//Sum求和,开四倍空间
    int A[maxn],n;//存原数组下标[1,n]

    (1)建树:

    //PushUp函数更新节点信息,这里是求和
    void PushUp(int rt){Sum[rt]=Sum[rt<<1]+Sum[rt<<1|1];}  
    //Build函数建立线段树
    void Build(int l,int r,int rt){ //[l,r]表示当前节点区间,rt表示当前节点的实际存储位置 
        if(l==r) {//若到达叶节点 
            Sum[rt]=A[l];//存储A数组的值
            return;  
        }  
        int m=(l+r)>>1;  
       //左右递归
        Build(l,m,rt<<1);  
        Build(m+1,r,rt<<1|1);  
        //更新信息
        PushUp(rt);  
    }  

    (2)点修改:

    假设A[L]+=C:

    void Update(int L,int C,int l,int r,int rt){//[l,r]表示当前区间,rt是当前节点编号//l,r表示当前节点区间,rt表示当前节点编号  
        if(l==r){//到达叶节点,修改叶节点的值
            Sum[rt]+=C;  
            return;  
        }  
        int m=(l+r)>>1;  
       //根据条件判断往左子树调用还是往右
        if(L <= m) Update(L,C,l,m,rt<<1);  
        else       Update(L,C,m+1,r,rt<<1|1);  
        PushUp(rt);//子节点的信息更新了,所以本节点也要更新信息
    }   

    点修改其实可以写的更简单,只需要把一路经过的Sum都+=C就行了,不过上面的代码更加规范,在题目更加复杂的时候,按照格式写更不容易错。

     

    (3)区间查询(本题为求和):

    询问A[L..R]的和

    注意到,整个函数的递归过程中,L,R是不变的。

    首先如果当前区间[l,r]在[L,R]内部,就直接累加答案

    如果左子区间与[L,R]有重叠,就递归左子树,右子树同理。

    int Query(int L,int R,int l,int r,int rt){//[L,R]表示操作区间,[l,r]表示当前区间,rt:当前节点编号
        if(L <= l && r <= R){  
           //在区间内直接返回
            return Sum[rt];  
        }  
        int m=(l+r)>>1;  
        //左子区间:[l,m] 右子区间:[m+1,r]  求和区间:[L,R]
       //累加答案
        int ANS=0;  
        if(L <= m) ANS+=Query(L,R,l,m,rt<<1);//左子区间与[L,R]有重叠,递归
        if(R >  m) ANS+=Query(L,R,m+1,r,rt<<1|1); //右子区间与[L,R]有重叠,递归
        return ANS;  
    }   
    

     

     


    线段树详解

    目录:

    一:综述

    二:原理

    三:递归实现

    四:非递归原理

    五:非递归实现

    六:线段树解题模型

    七:扫描线

    八:可持久化 (主席树)

    九:练习题

     

     

    一:综述

    假设有编号从1到n的n个点,每个点都存了一些信息,用[L,R]表示下标从L到R的这些点。

    线段树的用处就是,对编号连续的一些点进行修改或者统计操作,修改和统计的复杂度都是O(log2(n)).

     

    线段树的原理,就是,将[1,n]分解成若干特定的子区间(数量不超过4*n),然后,将每个区间[L,R]都分解为

    少量特定的子区间,通过对这些少量子区间的修改或者统计,来实现快速对[L,R]的修改或者统计。

     

    由此看出,用线段树统计的东西,必须符合区间加法,否则,不可能通过分成的子区间来得到[L,R]的统计结果。

     

    符合区间加法的例子:

    数字之和——总数字之和 = 左区间数字之和 + 右区间数字之和

    最大公因数(GCD)——总GCD = gcd( 左区间GCD , 右区间GCD );

    最大值——总最大值=max(左区间最大值,右区间最大值)

    不符合区间加法的例子:

    众数——只知道左右区间的众数,没法求总区间的众数

    01序列的最长连续零——只知道左右区间的最长连续零,没法知道总的最长连续零

     

    一个问题,只要能化成对一些连续点的修改和统计问题,基本就可以用线段树来解决了,具体怎么转化在第六节会讲。

    由于点的信息可以千变万化,所以线段树是一种非常灵活的数据结构,可以做的题的类型特别多,只要会转化。

    线段树当然是可以维护线段信息的,因为线段信息也是可以转换成用点来表达的(每个点代表一条线段)。

    所以在以下对结构的讨论中,都是对点的讨论,线段和点的对应关系在第七节扫描线中会讲。

     

    本文二到五节是讲对线段树操作的原理和实现。

    六到八节介绍了线段树解题模型,以及一些例题。

     

    初学者可以先看这篇文章: 线段树从零开始

     

    二:原理

    (注:由于线段树的每个节点代表一个区间,以下叙述中不区分节点和区间,只是根据语境需要,选择合适的词)

    线段树本质上是维护下标为1,2,..,n的n个按顺序排列的数的信息,所以,其实是“点树”,是维护n的点的信息,至于每个点的数据的含义可以有很多,

    在对线段操作的线段树中,每个点代表一条线段,在用线段树维护数列信息的时候,每个点代表一个数,但本质上都是每个点代表一个数。以下,在讨论线段树的时候,区间[L,R]指的是下标从L到R的这(R-L+1)个数,而不是指一条连续的线段。只是有时候这些数代表实际上一条线段的统计结果而已。

     

     

    线段树是将每个区间[L,R]分解成[L,M]和[M+1,R] (其中M=(L+R)/2 这里的除法是整数除法,即对结果下取整)直到 L==R 为止。 

    开始时是区间[1,n] ,通过递归来逐步分解,假设根的高度为1的话,树的最大高度为(n>1)。

    线段树对于每个n的分解是唯一的,所以n相同的线段树结构相同,这也是实现可持久化线段树的基础。

    下图展示了区间[1,13]的分解过程:

     

    上图中,每个区间都是一个节点,每个节点存自己对应的区间的统计信息。

     

    (1)线段树的点修改:

     

    假设要修改[5]的值,可以发现,每层只有一个节点包含[5],所以修改了[5]之后,只需要每层更新一个节点就可以线段树每个节点的信息都是正确的,所以修改次数的最大值为层数

    复杂度O(log2(n))


    (2)线段树的区间查询:

     

    线段树能快速进行区间查询的基础是下面的定理:

    定理:n>=3时,一个[1,n]的线段树可以将[1,n]的任意子区间[L,R]分解为不超过个子区间。

    这样,在查询[L,R]的统计值的时候,只需要访问不超过个节点,就可以获得[L,R]的统计信息,实现了O(log2(n))的区间查询。

     

    下面给出证明:

     

    (2.1)先给出一个粗略的证明(结合下图):

    先考虑树的最下层,将所有在区间[L,R]内的点选中,然后,若相邻的点的直接父节点是同一个,那么就用这个父节点代替这两个节点(父节点在上一层)。这样操作之后,本层最多剩下两个节点。若最左侧被选中的节点是它父节点的右子树,那么这个节点会被剩下。若最右侧被选中的节点是它的父节点的左子树,那么这个节点会被剩下。中间的所有节点都被父节点取代。

    对最下层处理完之后,考虑它的上一层,继续进行同样的处理,可以发现,每一层最多留下2个节点,其余的节点升往上一层,这样可以说明分割成的区间(节点)个数是大概是树高的两倍左右。

     

    下图为n=13的线段树,区间[2,12],按照上面的叙述进行操作的过程图:

    由图可以看出:在n=13的线段树中,[2,12]=[2] + [3,4] + [5,7] + [8,10] + [11,12] 。

     

     

    (2.2)然后给出正式一点的证明:

    定理:n>=3时,一个[1,n]的线段树可以将[1,n]的任意子区间[L,R]分解为不超过个子区间。

     

    用数学归纳法,证明上面的定理:

    首先,n=3,4,5时,用穷举法不难证明定理成立。

    假设对于n= 3,4,5,...,k-1上式都成立,下面来证明对于n=k ( k>=6 )成立:

    分为4种情况来证明:

     

    情况一:[L,R]包含根节点(L=1且R=n),此时,[L,R]被分解为了一个节点,定理成立。

     

    情况二:[L,R]包含根节点的左子节点,此时[L,R]一定不包含根的右子节点(因为如果包含,就可以合并左右子节点,

    用根节点替代,此时就是情况一)。这时,以右子节点为根的这个树的元素个数为

    [L,R]分成的子区间由两部分组成:

    一:根的左子结点,区间数为1 

    二:以根的右子节点为根的树中,进行区间查询,这个可以递归使用本定理。

    由归纳假设可得,[L,R]一共被分成了个区间。

    情况三:跟情况二对称,不一样的是,以根的左子节点为根的树的元素个数为

    [L,R]一共被分成了个区间。

    从公式可以看出,情况二的区间数小于等于情况三的区间数,于是只需要证明情况三的区间数符合条件就行了。

    于是,情况二和情况三定理成立。

     

    情况四:[L,R]不包括根节点以及根节点的左右子节点。

    于是,剩下的层,每层最多两个节点(参考粗略证明中的内容)。

    于是[L,R]最多被分解成了个区间,定理成立。

     

     

    上面只证明了是上界,但是,其实它是最小上界。

    n=3,4时,有很多组区间的分解可以达到最小上界。

    当n>4时,当且仅当n=2^t (t>=3),L=2,R=2^t -1 时,区间[L,R]的分解可以达到最小上界

    就不证明了,有兴趣可以自己去证明。

    下图是n=16 , L=2 , R=15 时的操作图,此图展示了达到最小上界的树的结构。

     

     

     

     

     

    (3)线段树的区间修改:

    线段树的区间修改也是将区间分成子区间,但是要加一个标记,称作懒惰标记。

    标记的含义:

    本节点的统计信息已经根据标记更新过了,但是本节点的子节点仍需要进行更新。

    即,如果要给一个区间的所有值都加上1,那么,实际上并没有给这个区间的所有值都加上1,而是打个标记,记下来,这个节点所包含的区间需要加1.打上标记后,要根据标记更新本节点的统计信息,比如,如果本节点维护的是区间和,而本节点包含5个数,那么,打上+1的标记之后,要给本节点维护的和+5。这是向下延迟修改,但是向上显示的信息是修改以后的信息,所以查询的时候可以得到正确的结果。有的标记之间会相互影响,所以比较简单的做法是,每递归到一个区间,首先下推标记(若本节点有标记,就下推标记),然后再打上新的标记,这样仍然每个区间操作的复杂度是O(log2(n))。

     

    标记有相对标记绝对标记之分:

    相对标记是将区间的所有数+a之类的操作,标记之间可以共存,跟打标记的顺序无关(跟顺序无关才是重点)。

    所以,可以在区间修改的时候不下推标记,留到查询的时候再下推。

          注意:如果区间修改时不下推标记,那么PushUp函数中,必须考虑本节点的标记。

                     而如果所有操作都下推标记,那么PushUp函数可以不考虑本节点的标记,因为本节点的标记一定已经被下推了(也就是对本节点无效了)

    绝对标记是将区间的所有数变成a之类的操作,打标记的顺序直接影响结果,

    所以这种标记在区间修改的时候必须下推旧标记,不然会出错。

     

    注意,有多个标记的时候,标记下推的顺序也很重要,错误的下推顺序可能会导致错误。

     

    之所以要区分两种标记,是因为非递归线段树只能维护相对标记。

    因为非递归线段树是自底向上直接修改分成的每个子区间,所以根本做不到在区间修改的时候下推标记。

    非递归线段树一般不下推标记,而是自下而上求答案的过程中,根据标记更新答案。

     

    (4)线段树的存储结构:

    线段树是用数组来模拟树形结构,对于每一个节点R ,左子节点为 2*R (一般写作R<<1)右子节点为 2*R+1(一般写作R<<1|1)

    然后以1为根节点,所以,整体的统计信息是存在节点1中的。

    这么表示的原因看下图就很明白了,左子树的节点标号都是根节点的两倍,右子树的节点标号都是左子树+1:

    线段树需要的数组元素个数是:,一般都开4倍空间,比如: int A[n<<2];

     

     

    三:递归实现

    以下以维护数列区间和的线段树为例,演示最基本的线段树代码。

     

    (0)定义:

    #define maxn 100007  //元素总个数
    #define ls l,m,rt<<1
    #define rs m+1,r,rt<<1|1
    int Sum[maxn<<2],Add[maxn<<2];//Sum求和,Add为懒惰标记 
    int A[maxn],n;//存原数组数据下标[1,n] 
    

     

    (1)建树:

    //PushUp函数更新节点信息 ,这里是求和
    void PushUp(int rt){Sum[rt]=Sum[rt<<1]+Sum[rt<<1|1];}
    //Build函数建树 
    void Build(int l,int r,int rt){ //l,r表示当前节点区间,rt表示当前节点编号
    	if(l==r) {//若到达叶节点 
    		Sum[rt]=A[l];//储存数组值 
    		return;
    	}
    	int m=(l+r)>>1;
    	//左右递归 
    	Build(l,m,rt<<1);
    	Build(m+1,r,rt<<1|1);
    	//更新信息 
    	PushUp(rt);
    }
    

     

    (2)点修改:

    假设A[L]+=C:

    void Update(int L,int C,int l,int r,int rt){//l,r表示当前节点区间,rt表示当前节点编号
    	if(l==r){//到叶节点,修改 
    		Sum[rt]+=C;
    		return;
    	}
    	int m=(l+r)>>1;
    	//根据条件判断往左子树调用还是往右 
    	if(L <= m) Update(L,C,l,m,rt<<1);
    	else       Update(L,C,m+1,r,rt<<1|1);
    	PushUp(rt);//子节点更新了,所以本节点也需要更新信息 
    } 
    

     

    (3)区间修改:

    假设A[L,R]+=C

    void Update(int L,int R,int C,int l,int r,int rt){//L,R表示操作区间,l,r表示当前节点区间,rt表示当前节点编号 
    	if(L <= l && r <= R){//如果本区间完全在操作区间[L,R]以内 
    		Sum[rt]+=C*(r-l+1);//更新数字和,向上保持正确
    		Add[rt]+=C;//增加Add标记,表示本区间的Sum正确,子区间的Sum仍需要根据Add的值来调整
    		return ; 
    	}
    	int m=(l+r)>>1;
    	PushDown(rt,m-l+1,r-m);//下推标记
    	//这里判断左右子树跟[L,R]有无交集,有交集才递归 
    	if(L <= m) Update(L,R,C,l,m,rt<<1);
    	if(R >  m) Update(L,R,C,m+1,r,rt<<1|1); 
    	PushUp(rt);//更新本节点信息 
    } 
    

     

    (4)区间查询:

    询问A[L,R]的和

    首先是下推标记的函数:

    void PushDown(int rt,int ln,int rn){
    	//ln,rn为左子树,右子树的数字数量。 
    	if(Add[rt]){
    		//下推标记 
    		Add[rt<<1]+=Add[rt];
    		Add[rt<<1|1]+=Add[rt];
    		//修改子节点的Sum使之与对应的Add相对应 
    		Sum[rt<<1]+=Add[rt]*ln;
    		Sum[rt<<1|1]+=Add[rt]*rn;
    		//清除本节点标记 
    		Add[rt]=0;
    	}
    }
    

    然后是区间查询的函数:

    int Query(int L,int R,int l,int r,int rt){//L,R表示操作区间,l,r表示当前节点区间,rt表示当前节点编号
    	if(L <= l && r <= R){
    		//在区间内,直接返回 
    		return Sum[rt];
    	}
    	int m=(l+r)>>1;
    	//下推标记,否则Sum可能不正确
    	PushDown(rt,m-l+1,r-m); 
    	
    	//累计答案
    	int ANS=0;
    	if(L <= m) ANS+=Query(L,R,l,m,rt<<1);
    	if(R >  m) ANS+=Query(L,R,m+1,r,rt<<1|1);
    	return ANS;
    } 
    

     

    (5)函数调用:

    	//建树 
    	Build(1,n,1); 
    	//点修改
    	Update(L,C,1,n,1);
    	//区间修改 
    	Update(L,R,C,1,n,1);
    	//区间查询 
    	int ANS=Query(L,R,1,n,1);
    

     

    感谢几位网友指出了我的错误。

    我说相对标记在Update时可以不下推,这一点是对的,但是原来的代码是错误的。

    因为原来的代码中,PushUP函数是没有考虑本节点的Add值的,如果Update时下推标记,那么PushUp的时候,节点的Add值一定为零,所以不需要考虑Add。

    但是,如果Update时暂时不下推标记的话,那么PushUp函数就必须考虑本节点的Add值,否则会导致错误。

    为了简便,上面函数中,PushUp函数没有考虑Add标记。所以无论是相对标记还是绝对标记,在更新信息的时候,

    到达的每个节点都必须调用PushDown函数来下推标记,另外,代码中,点修改函数中没有PushDown函数,因为这里假设只有点修改一种操作,

    如果题目中是点修改和区间修改混合的话,那么点修改中也需要PushDown。


     

    四:非递归原理

    非递归的思路很巧妙,思路以及部分代码实现 来自  清华大学 张昆玮 《统计的力量》 ,有兴趣可以去找来看。

    非递归的实现,代码简单(尤其是点修改和区间查询),速度快,建树简单,遍历元素简单。总之能非递归就非递归吧。

    不过,要支持区间修改的话,代码会变得复杂,所以区间修改的时候还是要取舍。有个特例,如果区间修改,但是只需要

    在所有操作结束之后,一次性下推所有标记,然后求结果,这样的话,非递归写起来也是很方便的。

    下面先讲思路,再讲实现。

     

    点修改:

    非递归的思想总的来说就是自底向上进行各种操作。回忆递归线段树的点修改,首先由根节点1向下递归,找到对应的叶

    节点,然后,修改叶节点的值,再向上返回,在函数返回的过程中,更新路径上的节点的统计信息。而非递归线段树的思路是,

    如果可以直接找到叶节点,那么就可以直接从叶节点向上更新,而一个节点找父节点是很容易的,编号除以2再下取整就行了。

    那么,如何可以直接找到叶节点呢?非递归线段树扩充了普通线段树(假设元素数量为n),使得所有非叶结点都有两个子结点且叶子结点都在同一层。

    来观察一下扩充后的性质:

     

    可以注意到红色和黑色数字的差是固定的,如果事先算出这个差值,就可以直接找到叶节点。

     

    注意:区分3个概念:原数组下标,线段树中的下标和存储下标。

    原数组下标,是指,需要维护统计信息(比如区间求和)的数组的下标,这里都默认下标从1开始(一般用A数组表示)

    线段树下标,是指,加入线段树中某个位置的下标,比如,原数组中的第一个数,一般会加入到线段树中的第二个位置,

    为什么要这么做,后面会讲。

    存储下标,是指该元素所在的叶节点的编号,即实际存储的位置。

     

    【在上面的图片中,红色为原数组下标,黑色为存储下标】

     

    有了这3个概念,下面开始讲区间查询。

     

    点修改下的区间查询:

    首先,区间的划分没有变,现在关键是如何直接找到被分成的区间。原来是递归查找,判断左右子区间跟[L,R]是否有交点,

    若有交点则向下递归。现在要非递归实现,这就是巧妙之处,见下图,以查询[3,11]为例子。

     

     

     

    其实,容易发现,紫色部分的变化,跟原来分析线段树的区间分解的时候是一样的规则,图中多的蓝色是什么意思呢?

    首先注意到,蓝色节点刚好在紫色节点的两端。

    回忆一下,原来线段树在区间逐层被替代的过程中,哪些节点被留了下来?最左侧的节点,若为其父节点的右子节点,则留下。

    最右侧的节点,若为其父节点的左子节点则留下。那么对于包裹着紫色的蓝色节点来看,刚好相反。

    比如,以左侧的的蓝色为例,若该节点是其父节点的右子节点,就证明它右侧的那个紫色节点不会留下,会被其父替代,所以没必要在这一步计算,若该节点是其父节点的左子节点,就证明它右侧的那个紫色节点会留在这一层,所以必须在此刻计算,否则以后都不会再计算这个节点了。这样逐层上去,容易发现,对于左侧的蓝色节点来说,只要它是左子节点,那么就要计算对应的右子节点。同理,对于右侧的蓝色节点,只要它是右子节点,就需要计算它对应的左子节点。这个计算一直持续到左右蓝色节点的父亲为同一个的时候,才停止。于是,区间查询,其实就是两个蓝色节点一路向上走,在路径上更新答案。这样,区间修改就变成了两条同时向根走的链,明显复杂度O(log2(n))。并且可以非递归实现。

    至此,区间查询也解决了,可以直接找到所有分解成的区间。

    但是有一个问题,如果要查询[1,5]怎么办?[1]左边可是没地方可以放置蓝色节点了。

    问题的解决办法简单粗暴,原数组的1到n就不存在线段树的1到n了,而是存在线段树的2到n+1,

    而开始要建立一颗有n+2个元素的树,空出第一个和最后一个元素的空间。

     

    现在来讲如何对线段树进行扩充。

    再来看这个二叉树,令N=8;注意到,该树可以存8个元素,并且[1..7]是非叶节点,[8..15]是叶节点。

    也就是说,左下角为N的二叉树,可以存N个元素,并且[1..N-1]是非叶节点,[N..2N-1]是叶节点。

    并且,线段树下标+N-1=存储下标 (还记不记得原来对三个下标的定义)

     

    这时,这个线段树存在两段坐标映射:

    原数组下标+1=线段树下标

    线段树下标+N-1=存储下标 

    联立方程得到:原数组下标+N=存储下标

    于是从原数组下标到存储下标的转换及其简单。

     

    下一个问题:N怎么确定?

    上面提到了,N的含义之一是,这棵树可以存N个元素,也就是说N必须大于等于n+2

    于是,N的定义,N是大于等于n+2的,某个2的次方。

     

    区间修改下的区间查询:

    方法之一:如果题目许可,可以直接打上标记,最后一次下推所有标记,然后就可以遍历叶节点来获取信息。

    方法之二:如果题目查询跟修改混在一起,那么,采用标记永久化思想。也就是,不下推标记。

    递归线段树是在查询区间的时候下推标记,使得到达每个子区间的时候,Sum已经是正确值。

    非递归没法这么做,非递归是从下往上,遇到标记就更新答案。

    这题是Add标记,一个区间Add标记表示这个区间所有元素都需要增加Add

    Add含义不变,Add仍然表示本节点的Sum已经更新完毕,但是子节点的Sum仍需要更新.

    现在就是如何在查询的时候根据标记更新答案。

    观察下图:

    左边的蓝色节点从下往上走,在蓝色节点到达[1,4]时,注意到,左边蓝色节点之前计算过的所有节点(即[3,4])都是目前蓝色节点的子节点也就是说,当前蓝色节点的Add是要影响这个节点已经计算过的所有数。多用一个变量来记录这个蓝色节点已经计算过多少个数,根据个数以及当前蓝色节点的Add,来更新最终答案。

    更新完答案之后,再加上[5,8]的答案,同时当前蓝色节点计算过的个数要+4(因为[5,8]里有4个数)

    然后当这个节点到达[1,8]节点时,可以更新[1,8]的Add.

    这里,本来左右蓝色节点相遇之后就不再需要计算了,但是由于有了Add标记,左右蓝色节点的公共祖先上的Add标记会影响目前的所有数,所以还需要一路向上查询到根,沿路根据Add更新答案。

     

    区间修改:

    这里讲完了查询,再来讲讲修改

    修改的时候,给某个区间的Add加上了C,这个区间的子区间向上查询时,会经过这个节点,也就是会计算这个Add,但是

    如果路径经过这个区间的父节点,就不会计算这个节点的Add,也就会出错。这里其实跟递归线段树一样,改了某个区间的Add

    仍需要向上更新所有包含这个区间的Sum,来保持上面所有节点的正确性。

     

    五:非递归实现

    以下以维护数列区间和的线段树为例,演示最基本的非递归线段树代码。

     

    (0)定义

    // 
    #define maxn 100007
    int A[maxn],n,N;//原数组,n为原数组元素个数 ,N为扩充元素个数 
    int Sum[maxn<<2];//区间和 
    int Add[maxn<<2];//懒惰标记 
    

     

    (1)建树:

    //
    void Build(int n){
    	//计算N的值 
    	N=1;while(N < n+2) N <<= 1;
    	//更新叶节点 
    	for(int i=1;i<=n;++i) Sum[N+i]=A[i];//原数组下标+N=存储下标
    	//更新非叶节点 
    	for(int i=N-1;i>0;--i){
    		//更新所有非叶节点的统计信息 
    		Sum[i]=Sum[i<<1]+Sum[i<<1|1];
    		//清空所有非叶节点的Add标记 
    		Add[i]=0;
    	}
    } 
    

     

    (2)点修改:

    A[L]+=C

    //
    void Update(int L,int C){
    	for(int s=N+L;s;s>>=1){
    		Sum[s]+=C;
    	}
    } 
    

     

    (3)点修改下的区间查询:

    求A[L..R]的和(点修改没有使用Add所以不需要考虑)

    代码非常简洁,也不难理解,

    s和t分别代表之前的论述中的左右蓝色节点,其余的代码根据之前的论述应该很容易看懂了。

    s^t^1 在s和t的父亲相同时值为0,终止循环。

    两个if是判断s和t分别是左子节点还是右子节点,根据需要来计算Sum

    //
    int Query(int L,int R){
    	int ANS=0;
    	for(int s=N+L-1,t=N+R+1;s^t^1;s>>=1,t>>=1){
    		if(~s&1) ANS+=Sum[s^1];
    		if( t&1) ANS+=Sum[t^1];
    	}
    	return ANS;
    } 
    

     

    (4)区间修改:

    A[L..R]+=C

    <span style="font-size:14px;">//
    void Update(int L,int R,int C){
    	int s,t,Ln=0,Rn=0,x=1;
    	//Ln:  s一路走来已经包含了几个数
    	//Rn:  t一路走来已经包含了几个数
    	//x:   本层每个节点包含几个数
    	for(s=N+L-1,t=N+R+1;s^t^1;s>>=1,t>>=1,x<<=1){
    		//更新Sum
    		Sum[s]+=C*Ln;
    		Sum[t]+=C*Rn;
    		//处理Add
    		if(~s&1) Add[s^1]+=C,Sum[s^1]+=C*x,Ln+=x;
    		if( t&1) Add[t^1]+=C,Sum[t^1]+=C*x,Rn+=x;
    	}
    	//更新上层Sum
    	for(;s;s>>=1,t>>=1){
    		Sum[s]+=C*Ln;
    		Sum[t]+=C*Rn;
    	} 
    } </span>
    

     

    (5)区间修改下的区间查询:

    求A[L..R]的和

    //
    int Query(int L,int R){
    	int s,t,Ln=0,Rn=0,x=1;
    	int ANS=0;
    	for(s=N+L-1,t=N+R+1;s^t^1;s>>=1,t>>=1,x<<=1){
    		//根据标记更新 
    		if(Add[s]) ANS+=Add[s]*Ln;
    		if(Add[t]) ANS+=Add[t]*Rn;
    		//常规求和 
    		if(~s&1) ANS+=Sum[s^1],Ln+=x;
    		if( t&1) ANS+=Sum[t^1],Rn+=x; 
    	}
    	//处理上层标记
    	for(;s;s>>=1,t>>=1){
    		ANS+=Add[s]*Ln;
    		ANS+=Add[t]*Rn;
    	}
    	return ANS;
    }
    

     

    六:线段树解题模型

    给出线段树解题模型以及一些例题。

    先对图中各个名字给出定义:

    问题:可能可以用线段树解决的问题

    目标信息:由问题转换而成的,为了解决问题而需要统计的信息(可能不满足区间加法)。

    点信息:每个点储存的信息

    区间信息:每个区间维护的信息(线段树节点定义) (必须满足区间加法)

    区间信息包括 统计信息标记

    --------统计信息:统计节点代表的区间的信息,一般自下而上更新

    --------标记:对操作进行标记(在区间修改时需要),一般自上而下传递,或者不传递

    区间加法:实现区间加法的代码

    查询:实现查询操作的代码

    修改:实现修改操作的代码

     

    图中紫线右边是实际线段树的实现,左边是对问题的分析以及转换。

     

    一个问题,若能转换成对一些连续点的修改或者统计,就可以考虑用线段树解决。

    首先确定目标信息点信息,然后将目标信息转换成区间信息(必要时,增加信息,使之符合区间加法)。

    之后就是线段树的代码实现了,包括:

    1.区间加法 

    2.建树,点信息到区间信息的转换 

    3.每种操作(包括查询,修改)对区间信息的调用,修改

     

    这样,点的信息不同,区间信息不同,线段树可以维护很多种类的信息,所以是一种非常实用的数据结构。

    可以解决很多问题,下面给出几个例子来说明。

     

    (1):字符串哈希

    题目:URAL1989 Subpalindromes    题解

    给定一个字符串(长度<=100000),有两个操作。   1:改变某个字符。 2:判断某个子串是否构成回文串。 

    直接判断会超时。这个题目,是用线段树维护字符串哈希

    对于一个字符串a[0],a[1],...,a[n-1] 它对应的哈希函数为a[0]+a[1]*K + a[2]*K^2 +...+a[n-1]*K^(n-1)

    再维护一个从右往左的哈希值:a[0]*K^(n-1) + a[1]*K^(n-2) +...+a[n-1]

    若是回文串,则左右的哈希值会相等。而左右哈希值相等,则很大可能这是回文串。

    若出现误判,可以再用一个K2,进行二次哈希判断,可以减小误判概率。

    实现上,哈希值最好对某个质数取余数,这样分布更均匀。

     

    解题模型:

    问题经过转换之后:

    目标信息:某个区间的左,右哈希值

    点信息:一个字符

    目标信息已经符合区间加法,所以区间信息=目标信息

    所以线段树的结构为:

    区间信息:区间哈希值

    点信息:一个字符

    代码主要需要注意2个部分:

    1.区间加法 :(PushUp函数,Pow[a]=K^a)

    2.点信息->区间信息:(叶节点上,区间只包含一个点,所以需要将点信息转换成区间信息)

    修改以及查询,在有了区间加法的情况下,没什么难度了。

     

    可以看出,上述解题过程的核心,就是找到区间信息, 写好区间加法

    下面是维护区间和的部分,下面的代码没有取余,也就是实际上是对2^32取余数,这样其实分布不均匀,容易出现误判:

    // 
    #define K 137
    #define maxn 100001 
    char str[maxn];
    int Pow[maxn];//K的各个次方 
    struct Node{
    	int KeyL,KeyR;
    	Node():KeyL(0),KeyR(0){}
    	void init(){KeyL=KeyR=0;}
    }node[maxn<<2];
    void PushUp(int L,int R,int rt){
    	node[rt].KeyL=node[rt<<1].KeyL+node[rt<<1|1].KeyL*Pow[L];
    	node[rt].KeyR=node[rt<<1].KeyR*Pow[R]+node[rt<<1|1].KeyR;
    }

     

    (2):最长连续零

    题目:Codeforces 527C Glass Carving   题解

    题意是给定一个矩形,不停地纵向或横向切割,问每次切割后,最大的矩形面积是多少。

    最大矩形面积=最长的长*最宽的宽

    这题,长宽都是10^5,所以,用01序列表示每个点是否被切割,然后,

    最长的长就是长的最长连续0的数量+1

    最长的宽就是宽的最长连续0的数量+1

    于是用线段树维护最长连续零

     

    问题转换成:

    目标信息:区间最长连续零的个数

    点信息:0 或 1

    由于目标信息不符合区间加法,所以要扩充目标信息。

     

    转换后的线段树结构

    区间信息:从左,右开始的最长连续零,本区间是否全零,本区间最长连续零。

    点信息:0 或 1

    然后还是那2个问题:

     

    1.区间加法:

    这里,一个区间的最长连续零,需要考虑3部分:

    -(1):左子区间最长连续零

    -(2):右子区间最长连续零

    -(3):左右子区间拼起来,而在中间生成的连续零(可能长于两个子区间的最长连续零)

    而中间拼起来的部分长度,其实是左区间从右开始的最长连续零+右区间从左开始的最长连续零。

    所以每个节点需要多两个量,来存从左右开始的最长连续零。

    然而,左开始的最长连续零分两种情况,

    --(1):左区间不是全零,那么等于左区间的左最长连续零

    --(2):左区间全零,那么等于左区间0的个数加上右区间的左最长连续零

    于是,需要知道左区间是否全零,于是再多加一个变量。

    最终,通过维护4个值,达到了维护区间最长连续零的效果。

     

    2.点信息->区间信息 : 

    如果是0,那么  最长连续零=左最长连续零=右最长连续零=1 ,全零=true。

    如果是1,那么  最长连续零=左最长连续零=右最长连续零=0, 全零=false。

     

    至于修改和查询,有了区间加法之后,机械地写一下就好了。

    由于这里其实只有对整个区间的查询,所以查询函数是不用写的,直接找根的统计信息就行了。

     

    代码如下:

    //
    #define maxn 200001
    using namespace std;
    int L[maxn<<2][2];//从左开始连续零个数 
    int R[maxn<<2][2];//从右 
    int Max[maxn<<2][2];//区间最大连续零 
    bool Pure[maxn<<2][2];//是否全零 
    int M[2];
    void PushUp(int rt,int k){//更新rt节点的四个数据  k来选择两棵线段树
    	Pure[rt][k]=Pure[rt<<1][k]&&Pure[rt<<1|1][k]; 
    	Max[rt][k]=max(R[rt<<1][k]+L[rt<<1|1][k],max(Max[rt<<1][k],Max[rt<<1|1][k]));
    	L[rt][k]=Pure[rt<<1][k]?L[rt<<1][k]+L[rt<<1|1][k]:L[rt<<1][k];
    	R[rt][k]=Pure[rt<<1|1][k]?R[rt<<1|1][k]+R[rt<<1][k]:R[rt<<1|1][k];
    }
     
    

     

    (3):计数排序

    题目:Codeforces 558E A Simple Task  题解

    给定一个长度不超过10^5的字符串(小写英文字母),和不超过5000个操作。

    每个操作 L R K 表示给区间[L,R]的字符串排序,K=1为升序,K=0为降序。

    最后输出最终的字符串。

     

    题目转换成:

    目标信息:区间的计数排序结果

    点信息:一个字符

    这里,目标信息是符合区间加法的,但是为了支持区间操作,还是需要扩充信息。

     

    转换后的线段树结构

    区间信息:区间的计数排序结果,排序标记,排序种类(升,降)

    点信息:一个字符

     

    代码中需要解决的四个问题(难点在于标记下推和区间修改):

    1.区间加法

    对应的字符数量相加即可(注意标记是不上传的,所以区间加法不考虑标记)。

    2.点信息->区间信息:把对应字符的数量设置成1,其余为0,排序标记为false。

    3.标记下推

    明显,排序标记是绝对标记,也就是说,标记对子节点是覆盖式的效果,一旦被打上标记,下层节点的一切信息都无效。

    下推标记时,根据自己的排序结果,将元素分成对应的部分,分别装入两个子树。

    4.区间修改

    这个是难点,由于要对某个区间进行排序,首先对各个子区间求和(求和之前一定要下推标记,才能保证求的和是正确的)

    由于使用的计数排序,所以求和之后,新顺序也就出来了。然后按照排序的顺序按照每个子区间的大小来分配字符。

    操作后,每个子区间都被打上了标记。

     

    最后,在所有操作结束之后,一次下推所有标记,就可以得到最终的字符序列。

     

    这里只给出节点定义。

    // 
    struct Node{
    	int d[26];//计数排序 
    	int D;//总数
    	bool sorted;//是否排好序 
    	bool Inc;//是否升序
    };
    

    (4)总结:

    总结一下,线段树解题步骤。

     

    :将问题转换成点信息目标信息

    即,将问题转换成对一些点的信息的统计问题。

     

    :将目标信息根据需要扩充成区间信息

    1.增加信息符合区间加法。

    2.增加标记支持区间操作。

     

    :代码中的主要模块:

    1.区间加法 

    2.标记下推 

    3.点信息->区间信息 

    4.操作(各种操作,包括修改和查询)

     

     

    完成第一步之后,题目有了可以用线段树解决的可能。

    完成第二步之后,题目可以由线段树解决。

    第三步就是慢慢写代码了。
     

    七:扫描线

    线段树的一大应用是扫描线。

     

    先把相关题目给出,有兴趣可以去找来练习:

     

    POJ 1177 Picture:给定若干矩形求合并之后的图形周长    题解

    HDU 1255 覆盖的面积:给定平面上若干矩形,求出被这些矩形覆盖过至少两次的区域的面积.   题解

    HDU 3642 Get The Treasury:给定若干空间立方体,求重叠了3次或以上的体积(这个是扫描面,每个面再扫描线)题解

    再补充一道稍微需要一点模型转换的扫描线题:

    POJ 2482 Stars in your window : 给定一些星星的位置和亮度,求用W*H的矩形能够框住的星星亮度之和最大为多少。

    这题是把星星转换成了矩形,把矩形框转换成了点,然后再扫描线。  题解

     

     

    扫描线求重叠矩形面积:

    考虑下图中的四个矩形:

     

     

    观察第三个图:

    扫描线的思路:使用一条垂直于X轴的直线,从左到右来扫描这个图形,明显,只有在碰到矩形的左边界或者右边界的时候,

    这个线段所扫描到的情况才会改变,所以把所有矩形的入边,出边按X值排序。然后根据X值从小到大去处理,就可以

    用线段树来维护扫描到的情况。如上图,X1到X8是所有矩形的入边,出边的X坐标。

    而红色部分的线段,是这样,如果碰到矩形的入边,就把这条边加入,如果碰到出边,就拿走。红色部分就是有线段覆盖的部分。

    要求面积,只需要知道图中的L1到L8。而线段树就是用来维护这个L1到L8的。

    扫描线算法流程:

     

    X1:首先遇到X1,将第一条线段加入线段树,由线段树统计得到线段长度为L1.

     

    X2:然后继续扫描到X2,此时要进行两个动作:

    1.计算面积,目前扫过的面积=L1*(X2-X1)

    2.更新线段。由于X2处仍然是入边,所以往线段树中又加了一条线段,加的这条线段可以参考3幅图中的第一幅。

    然后线段树自动得出此时覆盖的线段长度为L2 (注意两条线段有重叠部分,重叠部分的长度只能算一次)

     

    X3:继续扫描到X3,步骤同X2

    先计算 扫过的面积+=L2*(X3-X2)

    再加入线段,得到L3.

     

    X4:扫描到X4有些不一样了。

    首先还是计算  扫过的面积+=L3*(X4-X3)

    然后这时遇到了第一个矩形的出边,这时要从线段树中删除一条线段。

    删除之后的结果是线段树中出现了2条线段,线段树自动维护这两条线段的长度之和L4

     

    讲到这里算法流程应该很清晰了。

    首先将所有矩形的入边,出边都存起来,然后根据X值排序。

    这里用一个结构体,来存这些信息,然后排序。

    //
    struct LINE{
    	int x;//横坐标 
    	int y1,y2;//矩形纵向线段的左右端点 
    	bool In;//标记是入边还是出边 
    	bool operator < (const Line &B)const{return x < B.x;}
    }Line[maxn]; 
    

    然后扫描的时候,需要两个变量,一个叫PreL,存前一个x的操作结束之后的L值,和X,前一个横坐标。

    假设一共有Ln条线段,线段下标从0开始,已经排好序。

    那么算法大概是这样:

    //
    int PreL=0;//前一个L值,刚开始是0,所以第一次计算时不会引入误差 
    int X;//X值 
    int ANS=0;//存累计面积
    int I=0;//线段的下标 
     
    while(I < Ln){
    	//先计算面积 
    	ANS+=PreL*(Line[I].x-X);
    	X=Line[I].x;//更新X值
    	//对所有X相同的线段进行操作 
    	while(I < Ln && Line[I].x == X){
    		//根据入边还是出边来选择加入线段还是移除线段 
    		if(Line[I].In) Cover(Line[I].y1,Line[I].y2-1,1,n,1);
    		else         Uncover(Line[I].y1,Line[I].y2-1,1,n,1);
    		++I;
    	} 
    }
    


    无论是求面积还是周长,扫描线的结构大概就是上面的样子。

     

    需要解决的几个问题:

    现在有两点需要说明一下。

    (1):线段树进行线段操作时,每个点的含义(比如为什么Cover函数中,y2后面要-1)。

    (2):线段树如何维护扫描线过程中的覆盖线段长度。

    (3):线段树如何维护扫描线过程中线段的数量。

    (1):线段树中点的含义

    线段树如果没有离散化,那么线段树下标为1,就代表线段[1,2)

    线段树下标为K的时候,代表的线段为[K,K+1) (长度为1)

    所以,将上面的所有线段都化为[y1,y2)就可以理解了,线段[y1,y2)只包括线段树下标中的y1,y1+1,...,y2-1

    当y值的范围是10^9时,就不能再按照上面的办法按值建树了,这时需要离散化。

    下面是离散化的代码:

    //
    int Rank[maxn],Rn;
    void SetRank(){//调用前,所有y值被无序存入Rank数组,下标为[1..Rn] 
    	int I=1;
    	//第一步排序 
    	sort(Rank+1,Rank+1+Rn); 
    	//第二步去除重复值 
    	for(int i=2;i<=Rn;++i) 
             if(Rank[i]!=Rank[i-1]) 
                 Rank[++I]=Rank[i];
    	Rn=I;
    	//此时,所有y值被从小到大无重复地存入Rank数组,下标为[1..Rn] 
    } 
    int GetRank(int x){//给定x,求x的下标 
    	//二分法求下标 
    	int L=1,R=Rn,M;//[L,R] first >=x
    	while(L!=R){
    		M=(L+R)>>1;
    		if(Rank[M]<x)
               L=M+1;
    		else R=M;
    	}
    	return L;
    }
    

    此时,线段树的下标的含义就变成:如果线段树下标为K,代表线段[ Rank[K] , Rank[K+1] )。

    下标为K的线段长度为Rank[K+1]-Rank[K]

    所以此时叶节点的线段长度不是1了。

    这时,之前的扫描线算法的函数调用部分就稍微的改变了一点:

    // 
    if(Line[I].In) 
        Cover(GetRank(Line[I].y1),GetRank(Line[I].y2)-1,1,n,1);
    else
        Uncover(GetRank(Line[I].y1),GetRank(Line[I].y2)-1,1,n,1);
    

    看着有点长,其实不难理解,只是多了一步从y值到离散之后的下标的转换。

     

    注意一点,如果下标为K的线段长度为Rank[K+1]-Rank[K],那么下标为Rn的线段树的长度呢?

    其实这个不用担心,Rank[Rn]作为所有y值中的最大值,它肯定是一个线段的右端点,

    而右端点求完离散之后的下标还要-1,所以上面的线段覆盖永远不会覆盖到Rn。

    所以线段树其实只需要建立Rn-1个元素,因为下标为Rn的无法定义,也不会被访问。

    不过有时候留着也有好处,这个看具体实现时自己取舍。

     

    (2):如何维护覆盖线段长度

    先提一个小技巧,一般,利用两个子节点来更新本节点的函数写成PushUp();

    但是,对于比较复杂的子区间合并问题,在区间查询的时候,需要合并若干个子区间。

    而合并子区间是没办法用PushUp函数的。于是,对于比较复杂的问题,把单个节点的信息写成一个结构体。

    在结构体内重载运算符"+",来实现区间合并。这样,不仅在PushUp函数可以调用这个加法,区间询问时也可以

    调用这个加法,这样更加方便。

     

    下面给出维护线段覆盖长度的节点定义:

    //
    struct Node{
    	int Cover;//区间整体被覆盖的次数 
    	int L;//Length : 所代表的区间总长度
    	int CL;//Cover Length :实际覆盖长度
    	Node operator +(const Node &B)const{
    		Node X;
    		X.Cover=0;//因为若上级的Cover不为0,不会调用子区间加法函数 
    		X.L=L+B.L;
    		X.CL=CL+B.CL;
    		return X;
    	}
    }K[maxn<<2];
    

     

    这样定义之后,区间的信息更新是这样的:

    若本区间的覆盖次数大于0,那么令CL=L,直接为全覆盖,不管下层是怎么覆盖的,反正本区间已经全被覆盖。

    若本区间的覆盖次数等于0,那么调用上面结构体中的加法函数,利用子区间的覆盖来计算。

    加入一条线段就是给每一个分解的子区间的Cover+1,删除线段就-1,每次修改Cover之后,更新区间信息。

    这里完全没有下推标记的过程。

    查询的代码如下:

    如果不把区间加法定义成结构体内部的函数,而是定义在PushUp函数内,那么这里几乎就要重写一遍区间合并。

    因为PushUp在这里用不上。

    //
    Node Query(int L,int R,int l,int r,int rt){
    	if(L <= l && r <= R){
    		return K[rt];
    	}
    	int m=(l+r)>>1;
    	Node LANS,RANS;
    	int X=0;
    	if(L <= m) 
            LANS=Query(L,R,ls),X+=1;
    	if(R >  m) 
            RANS=Query(L,R,rs),X+=2;
    	if(X==1) 
            return LANS;
    	if(X==2) 
            return RANS;
    	return LANS+RANS;
    }
    

     

    维护线段覆盖3次或以上的长度:

    //
    struct Nodes{  
        int C;//Cover  
        int CL[4];//CoverLength[0~3]  
        //CL[i]表示被覆盖了大于等于i次的线段长度,CL[0]其实就是线段总长 
    }ST[maxn<<2];  
    void PushUp(int rt){  
        for(int i=1;i<=3;++i){  
            if(ST[rt].C < i) 
                ST[rt].CL[i]=ST[rt<<1].CL[i-ST[rt].C]+ST[rt<<1|1].CL[i-ST[rt].C];  
            else 
                ST[rt].CL[i]=ST[rt].CL[0];  
        }  
    }  
    

     


    这里给出节点定义和PushUp().

    更新节点信息的思路大概就是:

    假设要更新CL[3],然后发现本节点被覆盖了2次,那么本节点被覆盖三次或以上的长度就等于子节点被覆盖了1次或以上的长度之和。

    而CL[0]建树时就赋值,之后不需要修改。

     

    (3):如何维护扫描线过程中线段的数量

    // 
    struct Node{  
        int cover;//完全覆盖层数  
        int lines;//分成多少个线段  
        bool L,R;//左右端点是否被覆盖  
        Node operator +(const Node &B){//连续区间的合并   
            Node C;  
            C.cover=0;  
            C.lines=lines+B.lines-(R&&B.L);  
            C.L=L;C.R=B.R;  
            return C;  
        }  
    }K[maxn<<2];  
    

    要维护被分成多少个线段,就需要记录左右端点是否被覆盖,知道了这个,就可以合并区间了。

    左右两个区间合并时,若左区间的最右侧有线段且右区间的最左侧也有线段,那么这两个线段会合二为一,于是总线段数量会减少1.

     

    扫描线求重叠矩形周长:

    这个图是在原来的基础上多画了一些东西,这次是要求周长。

    所有的横向边都画了紫色,所有的纵向边画了绿色。

     

    先考虑绿色的边,由图可以观察到,绿色边的长度其实就是L的变化值。

    比如考虑X1,本来L是0,从0变到L1,所以绿色边长为L1.

    再考虑X2,由L1变成了L2,所以绿色边长度为L2-L1,

    于是,绿色边的长度就是L的变化值(注意上图中令L0=0,L9=0)。

    因为长度是从0开始变化,最终归0.

     

    再考虑紫色的边,要计算紫色边,其实就是计算L的线段是有几个线段组成的,每个线段会贡献两个端点(紫色圆圈)

    而每个端点都会向右延伸出一条紫色边一直到下一个X值。

     

    所以周长就是以上两部分的和。而两部分怎么维护,前面都讲过了,下面给出代码。

    // 
    struct Node{  
        int cover;//完全覆盖层数  
        int lines;//分成多少个线段  
        bool L,R;//左右端点是否被覆盖  
        int CoverLength;//覆盖长度   
        int Length;//总长度   
        Node(){}  
        Node(int cover,int lines,bool L,bool R,int CoverLength):cover(cover),lines(lines),L(L),R(R),CoverLength(CoverLength){}  
        Node operator +(const Node &B){//连续区间的合并   
            Node C;  
            C.cover=0;  
            C.lines=lines+B.lines-(R&&B.L);  
            C.CoverLength=CoverLength+B.CoverLength;  
            C.L=L;C.R=B.R;  
            C.Length=Length+B.Length;  
            return C;  
        }  
    }K[maxn<<2];  
    void PushUp(int rt){//更新非叶节点   
        if(K[rt].cover){  
            K[rt].CoverLength=K[rt].Length;  
            K[rt].L=K[rt].R=K[rt].lines=1;  
        }  
        else{  
            K[rt]=K[rt<<1]+K[rt<<1|1];  
        }  
    }  
    

     

    扫描的代码:

            int PreX=L[0].x;//前X坐标   
            int ANS=0;//目前累计答案   
            int PreLength=0;//前线段总长  
            int PreLines=0;//前线段数量   
            Build(1,20001,1);  
            for(int i=0;i<nL;++i){  
                //操作   
                if(L[i].c) 
                    Cover(L[i].y1,L[i].y2-1,1,20001,1);  
                else 
                    Uncover(L[i].y1,L[i].y2-1,1,20001,1);  
                //更新横向的边界   
                ANS+=2*PreLines*(L[i].x-PreX);  
                PreLines=K[1].lines;  
                PreX=L[i].x;  
                //更新纵向边界   
                ANS+=abs(K[1].CoverLength-PreLength);  
                PreLength=K[1].CoverLength;  
            }  
            //输出答案   
            printf("%d\n",ANS);  
    

     


     

    求立方体重叠3次或以上的体积:

    这个首先扫描面,每个面内求重叠了3次或以上的面积,然后乘以移动距离就是体积。

    面内扫描线,用线段树维护重叠了3次或以上的线段长度,然后用长度乘移动距离就是重叠了3次或以上的面积。

    扫描面基本原理都跟扫描线一样,就是嵌套了一层而已,写的时候细心一点就没问题了。


     

    八:可持久化 (主席树)

    可持久化线段树,也叫主席树。

    可持久化数据结构思想,就是保留整个操作的历史,即,对一个线段树进行操作之后,保留访问操作前的线段树的能力。

    最简单的方法,每操作一次,建立一颗新树。这样对空间的需求会很大。

    而注意到,对于点修改,每次操作最多影响个节点,于是,其实操作前后的两个线段树,结构一样,

    而且只有个节点不同,其余的节点都一样,于是可以重复利用其余的点。

    这样,每次操作,会增加个节点。

    于是,这样的线段树,每次操作需要O(log2(n))的空间。

     

    题目:HDU 2665 Kth number      题解

    给定10万个数,10万个询问。

    每个询问,问区间[L,R]中的数,从小到大排列的话,第k个数是什么。

     

    这个题,首先对十万个数进行离散化,然后用线段树来维护数字出现的次数。

    每个节点都存出现次数,那么查询时,若左节点的数的个数>=k,就往左子树递归,否则往右子树递归。

    一直到叶节点,就找到了第k大的数。

     

    这题的问题是,怎么得到一个区间的每个数出现次数。

    注意到,数字的出现次数是满足区间减法的。

    于是要求区间[L,R]的数,其实就是T[R]-T[L-1]  ,其中T[X]表示区间[1,X]的数形成的线段树。

    现在的问题就是,如何建立这10万个线段树。

     

    由之前的分析,需要O(n log2(n))的空间

    下面是代码:

    //主席树   
    int L[maxnn],R[maxnn],Sum[maxnn],T[maxn],TP;//左右子树,总和,树根,指针   
    void Add(int &rt,int l,int r,int x){//建立新树,l,r是区间, x是新加入的数字的排名
        ++TP;L[TP]=L[rt];R[TP]=R[rt];Sum[TP]=Sum[rt]+1;rt=TP;//复制&新建  
        if(l==r) 
            return;  
        int m=(l+r)>>1;  
        if(x <= m) 
            Add(L[rt],l,m,x);  
        else
            Add(R[rt],m+1,r,x);  
    }  
    int Search(int TL,int TR,int l,int r,int k){//区间查询第k大  
        if(l==r) 
           return l;//返回第k大的下标  
        int m=(l+r)>>1;  
        if(Sum[L[TR]]-Sum[L[TL]]>=k) 
           return Search(L[TL],L[TR],l,m,k);  
        else 
           return Search(R[TL],R[TR],m+1,r,k-Sum[L[TR]]+Sum[L[TL]]);  
    }  
    

    以上就是主席树部分的代码。

    熟悉SBT的,应该都很熟悉这种表示方法。

    L,R是伪指针,指向左右子节点。

    特殊之处是,0 表示空树,并且 L[0]=R[0]=0.

    也就是说,空树的左右子树都是空树。

    而本题中,每一颗树其实都是完整的,刚开始有一颗空树。

    但是刚开始的空树,真的需要用空间去存吗?

    其实不需要,刚开始的空树有这些性质:

    1.每个节点的Sum值为0

    2.每个非叶节点的左右子节点的Sum值也是0

     

    而SBT的空树刚好满足这个性质。而线段树不依赖L,R指针来结束递归。

    线段树是根据区间l,r来结束的,所以不会出现死循环。

    所以只需要把Sum[0]=0;那么刚开始就不需要建树了,只有每个操作的个节点。

     

    这个线段树少了表示父节点的int rt,因为不需要(也不能够)通过rt来找子节点了,而是直接根据L,R来找。

     

    -----------------------------     补充     -------------------------------------

     

    终于又找到一道可以用主席树的题目了:Codeforces 650D.Zip-line  题解

    做这题之前需要会求普通的LIS问题(最长上升子序列问题)。

    九:练习题

    适合非递归线段树的题目:

     

    Codeforces 612D The Union of k-Segments :  题解

    题意:线段求交,给定一堆线段,按序输出被覆盖k次或以上的线段和点。

    基础题,先操作,最后一次下推标记,然后输出,

    维护两个线段树,一个线段覆盖,一个点覆盖。

     

    Codeforces 35E Parade : 题解

    题意:给定若干矩形,下端挨着地面,求最后的轮廓形成的折线,要求输出每一点的坐标。

    思路:虽然是区间修改的线段树,但只需要在操作结束后一次下推标记,然后输出,所以适合非递归线段树。

     

    URAL 1846 GCD2010 :  题解

    题意:总共10万个操作,每次向集合中加入或删除一个数,求集合的最大公因数。(规定空集的最大公因数为1)

     

    Codeforces 12D Ball :   题解

     

    题意:

    给N (N<=500000)个点,每个点有x,y,z ( 0<= x,y,z <=10^9 )

    对于某点(x,y,z),若存在一点(x1,y1,z1)使得x1 > x && y1 > y && z1 > z 则点(x,y,z)是特殊点。

    问N个点中,有多少个特殊点。

     

    提示:排序+线段树

     

    Codeforces 19D Points : 题解

     

    题意:

    给定最多20万个操作,共3种:

    1.add x y         :加入(x,y)这个点

    2.remove x y  :删除(x,y)这个点

    3.find x y         :找到在(x,y)这点右上方的x最小的点,若x相同找y最小的点,输出这点坐标,若没有,则输出-1.

     

    提示:排序,线段树套平衡树

     

    Codeforces 633E Startup Funding : 题解

    这题需要用到一点概率论,组合数学知识,和二分法。

    非递归线段树在这题中主要解决RMQ问题(区间最大最小值问题),由于不带修改,这题用Sparse Table求解RMQ是标答。

    因为RMQ询问是在二分法之内求的,而Sparse Table可以做到O(1)查询,所以用Sparse Table比较好,总复杂度O(n*log(n))。

    不过非递归线段树也算比较快的了,虽然复杂度是O(n*log(n)*log(n)),还是勉强过了这题。

     

    扫描线题目:

     

    POJ 1177 Picture:给定若干矩形求合并之后的图形周长    题解

    HDU 1255 覆盖的面积:给定平面上若干矩形,求出被这些矩形覆盖过至少两次的区域的面积.   题解

    HDU 3642 Get The Treasury:给定若干空间立方体,求重叠了3次或以上的体积(这个是扫描面,每个面再扫描线)题解

    POJ 2482 Stars in your window : 给定一些星星的位置和亮度,求用W*H的矩形能够框住的星星亮度之和最大为多少。  题解

     

    递归线段树题目:

    Codeforces 558E A Simple Task  题解

    给定一个长度不超过10^5的字符串(小写英文字母),和不超过5000个操作。

    每个操作 L R K 表示给区间[L,R]的字符串排序,K=1为升序,K=0为降序。

    最后输出最终的字符串。

     

    Codeforces 527C Glass Carving  :  题解

    给定一个矩形,不停地纵向或横向切割,问每次切割后,最大的矩形面积是多少。

     

    URAL1989 Subpalindromes    题解

    给定一个字符串(长度<=100000),有10万个操作。

    操作有两种:   

    1:改变某个字符。 

    2:判断某个子串是否构成回文串。 

     

    HDU 4288 Coder :  题解

     题意:对一个集合进行插入与删除操作。要求询问某个时刻,集合中的元素从小到大排序之后,序号%5 ==3 的元素值之和。

    这题其实不一定要用线段树去做的,不过线段树还是可以做的。

     

    HDU 2795 BillBoard : 题解

    题意:有一个板,h行,每行w长度的位置。每次往上面贴一张海报,长度为1*wi .

    每次贴的时候,需要找到最上面的,可以容纳的空间,并且靠边贴。

     

    Codeforces 374D Inna and Sequence :题解

    题意:给定百万个数a[m],然后有百万个操作,每次给现有序列加一个字符(0或1),或者删掉已有序列中,第 a[0] 个,第a[1]个,...,第a[m]个。

     

    Codeforces 482B Interesting Array:  题解

    题意就是,给定n,m.

    满足m个条件的n个数,或说明不存在。

    每个条件的形式是,给定 Li,Ri,Qi ,要求   a[Li]&a[Li+1]&...&a[Ri] = Qi ;

    Codeforces 474E Pillar (线段树+动态规划):  题解

    题意就是,给定10^5 个数(范围10^15),求最长子序列使得相邻两个数的差大于等于 d。

     

    POJ 2777  Count Color :   题解

    给线段涂颜色,最多30种颜色,10万个操作。

    每个操作给线段涂色,或问某一段线段有多少种颜色。

    30种颜色用int的最低30位来存,然后线段树解决。

     

    URAL 1019 Line Painting: 线段树的区间合并  题解

    给一段线段进行黑白涂色,最后问最长的一段白色线段的长度。

     

    Codeforces 633H Fibonacci-ish II  :题解

    这题需要用到莫队算法(Mo's Algorithm)+线段树区间修改,不过是单边界的区间,写起来挺有趣。

    另一种解法就是暴力,很巧妙的方法,高复杂度+低常数居然就这么给过了。

     

    树套树题目:

    ZOJ 2112 Dynamic Rankings 动态区间第k大  题解

    做法:树状数组套主席树 或者 线段树套平衡树

     

    Codeforces 605D Board Game :  题解

    做法:广度优先搜索(BFS)  +  线段树套平衡树

     

    Codeforces 19D Points : 题解

     

    题意:

    给定最多20万个操作,共3种:

    1.add x y         :加入(x,y)这个点

    2.remove x y  :删除(x,y)这个点

    3.find x y         :找到在(x,y)这点右上方的x最小的点,若x相同找y最小的点,输出这点坐标,若没有,则输出-1.

     

    提示:排序,线段树套平衡树

     

     

     

    本文转载于:

           https://blog.csdn.net/zearot/article/details/52280189

           https://blog.csdn.net/zearot/article/details/48299459

     

    展开全文
  • 线段树详解

    2018-06-14 11:02:43
    线段树详解By 岩之痕目录:一:综述二:原理三:递归实现四:非递归原理五:非递归实现六:线段树解题模型七:扫描线八:可持久化 (主席树)九:练习题一:综述假设有编号从1到n的n个点,每个点都存了一些信息,用[L,...
    线段树详解

    By 岩之痕

    目录:
    一:综述
    二:原理
    三:递归实现
    四:非递归原理
    五:非递归实现
    六:线段树解题模型
    七:扫描线
    八:可持久化 (主席树)
    九:练习题



    一:综述

    假设有编号从1到n的n个点,每个点都存了一些信息,用[L,R]表示下标从L到R的这些点。
    线段树的用处就是,对编号连续的一些点进行修改或者统计操作,修改和统计的复杂度都是O(log2(n)).

    线段树的原理,就是,将[1,n]分解成若干特定的子区间(数量不超过4*n),然后,将每个区间[L,R]都分解为
    少量特定的子区间,通过对这些少量子区间的修改或者统计,来实现快速对[L,R]的修改或者统计。

    由此看出,用线段树统计的东西,必须符合区间加法,否则,不可能通过分成的子区间来得到[L,R]的统计结果。

    符合区间加法的例子:
    数字之和——总数字之和 = 左区间数字之和 + 右区间数字之和
    最大公因数(GCD)——总GCD = gcd( 左区间GCD , 右区间GCD );
    最大值——总最大值=max(左区间最大值,右区间最大值)
    不符合区间加法的例子:
    众数——只知道左右区间的众数,没法求总区间的众数
    01序列的最长连续零——只知道左右区间的最长连续零,没法知道总的最长连续零

    一个问题,只要能化成对一些连续点的修改和统计问题,基本就可以用线段树来解决了,具体怎么转化在第六节会讲。
    由于点的信息可以千变万化,所以线段树是一种非常灵活的数据结构,可以做的题的类型特别多,只要会转化。
    线段树当然是可以维护线段信息的,因为线段信息也是可以转换成用点来表达的(每个点代表一条线段)。
    所以在以下对结构的讨论中,都是对点的讨论,线段和点的对应关系在第七节扫描线中会讲。

    本文二到五节是讲对线段树操作的原理和实现。
    六到八节介绍了线段树解题模型,以及一些例题。

    初学者可以先看这篇文章: 线段树从零开始

    二:原理

    (注:由于线段树的每个节点代表一个区间,以下叙述中不区分节点和区间,只是根据语境需要,选择合适的词)
    线段树本质上是维护下标为1,2,..,n的n个按顺序排列的数的信息,所以,其实是“点树”,是维护n的点的信息,至于每个点的数据的含义可以有很多,
    在对线段操作的线段树中,每个点代表一条线段,在用线段树维护数列信息的时候,每个点代表一个数,但本质上都是每个点代表一个数。以下,在讨论线段树的时候,区间[L,R]指的是下标从L到R的这(R-L+1)个数,而不是指一条连续的线段。只是有时候这些数代表实际上一条线段的统计结果而已。


    线段树是将每个区间[L,R]分解成[L,M]和[M+1,R] (其中M=(L+R)/2 这里的除法是整数除法,即对结果下取整)直到 L==R 为止。 
    开始时是区间[1,n] ,通过递归来逐步分解,假设根的高度为1的话,树的最大高度为(n>1)。
    线段树对于每个n的分解是唯一的,所以n相同的线段树结构相同,这也是实现可持久化线段树的基础。
    下图展示了区间[1,13]的分解过程:


    上图中,每个区间都是一个节点,每个节点存自己对应的区间的统计信息。

    (1)线段树的点修改:


    假设要修改[5]的值,可以发现,每层只有一个节点包含[5],所以修改了[5]之后,只需要每层更新一个节点就可以线段树每个节点的信息都是正确的,所以修改次数的最大值为层数
    复杂度O(log2(n))


    (2)线段树的区间查询:


    线段树能快速进行区间查询的基础是下面的定理:
    定理:n>=3时,一个[1,n]的线段树可以将[1,n]的任意子区间[L,R]分解为不超过个子区间。
    这样,在查询[L,R]的统计值的时候,只需要访问不超过个节点,就可以获得[L,R]的统计信息,实现了O(log2(n))的区间查询。

    下面给出证明:

    (2.1)先给出一个粗略的证明(结合下图):
    先考虑树的最下层,将所有在区间[L,R]内的点选中,然后,若相邻的点的直接父节点是同一个,那么就用这个父节点代替这两个节点(父节点在上一层)。这样操作之后,本层最多剩下两个节点。若最左侧被选中的节点是它父节点的右子树,那么这个节点会被剩下。若最右侧被选中的节点是它的父节点的左子树,那么这个节点会被剩下。中间的所有节点都被父节点取代。
    对最下层处理完之后,考虑它的上一层,继续进行同样的处理,可以发现,每一层最多留下2个节点,其余的节点升往上一层,这样可以说明分割成的区间(节点)个数是大概是树高的两倍左右。

    下图为n=13的线段树,区间[2,12],按照上面的叙述进行操作的过程图:

    由图可以看出:在n=13的线段树中,[2,12]=[2] + [3,4] + [5,7] + [8,10] + [11,12] 。


    (2.2)然后给出正式一点的证明:
    定理:n>=3时,一个[1,n]的线段树可以将[1,n]的任意子区间[L,R]分解为不超过个子区间。

    用数学归纳法,证明上面的定理:
    首先,n=3,4,5时,用穷举法不难证明定理成立。
    假设对于n= 3,4,5,...,k-1上式都成立,下面来证明对于n=k ( k>=6 )成立:
    分为4种情况来证明:

    情况一:[L,R]包含根节点(L=1且R=n),此时,[L,R]被分解为了一个节点,定理成立。

    情况二:[L,R]包含根节点的左子节点,此时[L,R]一定不包含根的右子节点(因为如果包含,就可以合并左右子节点,
    用根节点替代,此时就是情况一)。这时,以右子节点为根的这个树的元素个数为
    [L,R]分成的子区间由两部分组成:
    一:根的左子结点,区间数为1 
    二:以根的右子节点为根的树中,进行区间查询,这个可以递归使用本定理。
    由归纳假设可得,[L,R]一共被分成了个区间。
    情况三:跟情况二对称,不一样的是,以根的左子节点为根的树的元素个数为
    [L,R]一共被分成了个区间。
    从公式可以看出,情况二的区间数小于等于情况三的区间数,于是只需要证明情况三的区间数符合条件就行了。
    于是,情况二和情况三定理成立。

    情况四:[L,R]不包括根节点以及根节点的左右子节点。
    于是,剩下的层,每层最多两个节点(参考粗略证明中的内容)。
    于是[L,R]最多被分解成了个区间,定理成立。
     


    上面只证明了是上界,但是,其实它是最小上界。
    n=3,4时,有很多组区间的分解可以达到最小上界。
    当n>4时,当且仅当n=2^t (t>=3),L=2,R=2^t -1 时,区间[L,R]的分解可以达到最小上界
    就不证明了,有兴趣可以自己去证明。
    下图是n=16 , L=2 , R=15 时的操作图,此图展示了达到最小上界的树的结构。






    (3)线段树的区间修改:

    线段树的区间修改也是将区间分成子区间,但是要加一个标记,称作懒惰标记。
    标记的含义:
    本节点的统计信息已经根据标记更新过了,但是本节点的子节点仍需要进行更新。
    即,如果要给一个区间的所有值都加上1,那么,实际上并没有给这个区间的所有值都加上1,而是打个标记,记下来,这个节点所包含的区间需要加1.打上标记后,要根据标记更新本节点的统计信息,比如,如果本节点维护的是区间和,而本节点包含5个数,那么,打上+1的标记之后,要给本节点维护的和+5。这是向下延迟修改,但是向上显示的信息是修改以后的信息,所以查询的时候可以得到正确的结果。有的标记之间会相互影响,所以比较简单的做法是,每递归到一个区间,首先下推标记(若本节点有标记,就下推标记),然后再打上新的标记,这样仍然每个区间操作的复杂度是O(log2(n))。

    标记有相对标记绝对标记之分:
    相对标记是将区间的所有数+a之类的操作,标记之间可以共存,跟打标记的顺序无关(跟顺序无关才是重点)。
    所以,可以在区间修改的时候不下推标记,留到查询的时候再下推。
          注意:如果区间修改时不下推标记,那么PushUp函数中,必须考虑本节点的标记。
                     而如果所有操作都下推标记,那么PushUp函数可以不考虑本节点的标记,因为本节点的标记一定已经被下推了(也就是对本节点无效了)
    绝对标记是将区间的所有数变成a之类的操作,打标记的顺序直接影响结果,
    所以这种标记在区间修改的时候必须下推旧标记,不然会出错。

    注意,有多个标记的时候,标记下推的顺序也很重要,错误的下推顺序可能会导致错误。

    之所以要区分两种标记,是因为非递归线段树只能维护相对标记。
    因为非递归线段树是自底向上直接修改分成的每个子区间,所以根本做不到在区间修改的时候下推标记。
    非递归线段树一般不下推标记,而是自下而上求答案的过程中,根据标记更新答案。

    (4)线段树的存储结构:

    线段树是用数组来模拟树形结构,对于每一个节点R ,左子节点为 2*R (一般写作R<<1)右子节点为 2*R+1(一般写作R<<1|1)
    然后以1为根节点,所以,整体的统计信息是存在节点1中的。
    这么表示的原因看下图就很明白了,左子树的节点标号都是根节点的两倍,右子树的节点标号都是左子树+1:

    线段树需要的数组元素个数是:,一般都开4倍空间,比如: int A[n<<2];


    三:递归实现

    以下以维护数列区间和的线段树为例,演示最基本的线段树代码。

    (0)定义:

    1. #define maxn 100007  //元素总个数  
    2. #define ls l,m,rt<<1  
    3. #define rs m+1,r,rt<<1|1  
    4. int Sum[maxn<<2],Add[maxn<<2];//Sum求和,Add为懒惰标记   
    5. int A[maxn],n;//存原数组数据下标[1,n]   

    (1)建树:

    1. //PushUp函数更新节点信息 ,这里是求和  
    2. void PushUp(int rt){Sum[rt]=Sum[rt<<1]+Sum[rt<<1|1];}  
    3. //Build函数建树   
    4. void Build(int l,int r,int rt){ //l,r表示当前节点区间,rt表示当前节点编号  
    5.     if(l==r) {//若到达叶节点   
    6.         Sum[rt]=A[l];//储存数组值   
    7.         return;  
    8.     }  
    9.     int m=(l+r)>>1;  
    10.     //左右递归   
    11.     Build(l,m,rt<<1);  
    12.     Build(m+1,r,rt<<1|1);  
    13.     //更新信息   
    14.     PushUp(rt);  
    15. }  


    (2)点修改:

    假设A[L]+=C:
    1. void Update(int L,int C,int l,int r,int rt){//l,r表示当前节点区间,rt表示当前节点编号  
    2.     if(l==r){//到叶节点,修改   
    3.         Sum[rt]+=C;  
    4.         return;  
    5.     }  
    6.     int m=(l+r)>>1;  
    7.     //根据条件判断往左子树调用还是往右   
    8.     if(L <= m) Update(L,C,l,m,rt<<1);  
    9.     else       Update(L,C,m+1,r,rt<<1|1);  
    10.     PushUp(rt);//子节点更新了,所以本节点也需要更新信息   
    11. }   

    (3)区间修改:


    假设A[L,R]+=C
    1. void Update(int L,int R,int C,int l,int r,int rt){//L,R表示操作区间,l,r表示当前节点区间,rt表示当前节点编号   
    2.     if(L <= l && r <= R){//如果本区间完全在操作区间[L,R]以内   
    3.         Sum[rt]+=C*(r-l+1);//更新数字和,向上保持正确  
    4.         Add[rt]+=C;//增加Add标记,表示本区间的Sum正确,子区间的Sum仍需要根据Add的值来调整  
    5.         return ;   
    6.     }  
    7.     int m=(l+r)>>1;  
    8.     PushDown(rt,m-l+1,r-m);//下推标记  
    9.     //这里判断左右子树跟[L,R]有无交集,有交集才递归   
    10.     if(L <= m) Update(L,R,C,l,m,rt<<1);  
    11.     if(R >  m) Update(L,R,C,m+1,r,rt<<1|1);   
    12.     PushUp(rt);//更新本节点信息   
    13. }   

    (4)区间查询:

    询问A[L,R]的和
    首先是下推标记的函数:
    1. void PushDown(int rt,int ln,int rn){  
    2.     //ln,rn为左子树,右子树的数字数量。   
    3.     if(Add[rt]){  
    4.         //下推标记   
    5.         Add[rt<<1]+=Add[rt];  
    6.         Add[rt<<1|1]+=Add[rt];  
    7.         //修改子节点的Sum使之与对应的Add相对应   
    8.         Sum[rt<<1]+=Add[rt]*ln;  
    9.         Sum[rt<<1|1]+=Add[rt]*rn;  
    10.         //清除本节点标记   
    11.         Add[rt]=0;  
    12.     }  
    13. }  

    然后是区间查询的函数:
    1. int Query(int L,int R,int l,int r,int rt){//L,R表示操作区间,l,r表示当前节点区间,rt表示当前节点编号  
    2.     if(L <= l && r <= R){  
    3.         //在区间内,直接返回   
    4.         return Sum[rt];  
    5.     }  
    6.     int m=(l+r)>>1;  
    7.     //下推标记,否则Sum可能不正确  
    8.     PushDown(rt,m-l+1,r-m);   
    9.       
    10.     //累计答案  
    11.     int ANS=0;  
    12.     if(L <= m) ANS+=Query(L,R,l,m,rt<<1);  
    13.     if(R >  m) ANS+=Query(L,R,m+1,r,rt<<1|1);  
    14.     return ANS;  
    15. }   

    (5)函数调用:


    1. //建树   
    2. Build(1,n,1);   
    3. //点修改  
    4. Update(L,C,1,n,1);  
    5. //区间修改   
    6. Update(L,R,C,1,n,1);  
    7. //区间查询   
    8. int ANS=Query(L,R,1,n,1);  

    感谢几位网友指出了我的错误。
    我说相对标记在Update时可以不下推,这一点是对的,但是原来的代码是错误的。
    因为原来的代码中,PushUP函数是没有考虑本节点的Add值的,如果Update时下推标记,那么PushUp的时候,节点的Add值一定为零,所以不需要考虑Add。
    但是,如果Update时暂时不下推标记的话,那么PushUp函数就必须考虑本节点的Add值,否则会导致错误。
    为了简便,上面函数中,PushUp函数没有考虑Add标记。所以无论是相对标记还是绝对标记,在更新信息的时候,
    到达的每个节点都必须调用PushDown函数来下推标记,另外,代码中,点修改函数中没有PushDown函数,因为这里假设只有点修改一种操作,
    如果题目中是点修改和区间修改混合的话,那么点修改中也需要PushDown。


    四:非递归原理

    非递归的思路很巧妙,思路以及部分代码实现 来自  清华大学 张昆玮 《统计的力量》 ,有兴趣可以去找来看。
    非递归的实现,代码简单(尤其是点修改和区间查询),速度快,建树简单,遍历元素简单。总之能非递归就非递归吧。
    不过,要支持区间修改的话,代码会变得复杂,所以区间修改的时候还是要取舍。有个特例,如果区间修改,但是只需要
    在所有操作结束之后,一次性下推所有标记,然后求结果,这样的话,非递归写起来也是很方便的。
    下面先讲思路,再讲实现。

    点修改:

    非递归的思想总的来说就是自底向上进行各种操作。回忆递归线段树的点修改,首先由根节点1向下递归,找到对应的叶
    节点,然后,修改叶节点的值,再向上返回,在函数返回的过程中,更新路径上的节点的统计信息。而非递归线段树的思路是,
    如果可以直接找到叶节点,那么就可以直接从叶节点向上更新,而一个节点找父节点是很容易的,编号除以2再下取整就行了。
    那么,如何可以直接找到叶节点呢?非递归线段树扩充了普通线段树(假设元素数量为n),使得所有非叶结点都有两个子结点且叶子结点都在同一层。
    来观察一下扩充后的性质:


    可以注意到红色和黑色数字的差是固定的,如果事先算出这个差值,就可以直接找到叶节点。

    注意:区分3个概念:原数组下标,线段树中的下标和存储下标。
    原数组下标,是指,需要维护统计信息(比如区间求和)的数组的下标,这里都默认下标从1开始(一般用A数组表示)
    线段树下标,是指,加入线段树中某个位置的下标,比如,原数组中的第一个数,一般会加入到线段树中的第二个位置,
    为什么要这么做,后面会讲。
    存储下标,是指该元素所在的叶节点的编号,即实际存储的位置。

    【在上面的图片中,红色为原数组下标,黑色为存储下标】

    有了这3个概念,下面开始讲区间查询。

    点修改下的区间查询:

    首先,区间的划分没有变,现在关键是如何直接找到被分成的区间。原来是递归查找,判断左右子区间跟[L,R]是否有交点,
    若有交点则向下递归。现在要非递归实现,这就是巧妙之处,见下图,以查询[3,11]为例子。




    其实,容易发现,紫色部分的变化,跟原来分析线段树的区间分解的时候是一样的规则,图中多的蓝色是什么意思呢?
    首先注意到,蓝色节点刚好在紫色节点的两端。
    回忆一下,原来线段树在区间逐层被替代的过程中,哪些节点被留了下来?最左侧的节点,若为其父节点的右子节点,则留下。
    最右侧的节点,若为其父节点的左子节点则留下。那么对于包裹着紫色的蓝色节点来看,刚好相反。
    比如,以左侧的的蓝色为例,若该节点是其父节点的右子节点,就证明它右侧的那个紫色节点不会留下,会被其父替代,所以没必要在这一步计算,若该节点是其父节点的左子节点,就证明它右侧的那个紫色节点会留在这一层,所以必须在此刻计算,否则以后都不会再计算这个节点了。这样逐层上去,容易发现,对于左侧的蓝色节点来说,只要它是左子节点,那么就要计算对应的右子节点。同理,对于右侧的蓝色节点,只要它是右子节点,就需要计算它对应的左子节点。这个计算一直持续到左右蓝色节点的父亲为同一个的时候,才停止。于是,区间查询,其实就是两个蓝色节点一路向上走,在路径上更新答案。这样,区间修改就变成了两条同时向根走的链,明显复杂度O(log2(n))。并且可以非递归实现。
    至此,区间查询也解决了,可以直接找到所有分解成的区间。
    但是有一个问题,如果要查询[1,5]怎么办?[1]左边可是没地方可以放置蓝色节点了。
    问题的解决办法简单粗暴,原数组的1到n就不存在线段树的1到n了,而是存在线段树的2到n+1,
    而开始要建立一颗有n+2个元素的树,空出第一个和最后一个元素的空间。

    现在来讲如何对线段树进行扩充。

    再来看这个二叉树,令N=8;注意到,该树可以存8个元素,并且[1..7]是非叶节点,[8..15]是叶节点。
    也就是说,左下角为N的二叉树,可以存N个元素,并且[1..N-1]是非叶节点,[N..2N-1]是叶节点。
    并且,线段树下标+N-1=存储下标 (还记不记得原来对三个下标的定义)

    这时,这个线段树存在两段坐标映射:
    原数组下标+1=线段树下标
    线段树下标+N-1=存储下标 
    联立方程得到:原数组下标+N=存储下标
    于是从原数组下标到存储下标的转换及其简单。

    下一个问题:N怎么确定?
    上面提到了,N的含义之一是,这棵树可以存N个元素,也就是说N必须大于等于n+2
    于是,N的定义,N是大于等于n+2的,某个2的次方。

    区间修改下的区间查询:

    方法之一:如果题目许可,可以直接打上标记,最后一次下推所有标记,然后就可以遍历叶节点来获取信息。
    方法之二:如果题目查询跟修改混在一起,那么,采用标记永久化思想。也就是,不下推标记。
    递归线段树是在查询区间的时候下推标记,使得到达每个子区间的时候,Sum已经是正确值。
    非递归没法这么做,非递归是从下往上,遇到标记就更新答案。
    这题是Add标记,一个区间Add标记表示这个区间所有元素都需要增加Add
    Add含义不变,Add仍然表示本节点的Sum已经更新完毕,但是子节点的Sum仍需要更新.
    现在就是如何在查询的时候根据标记更新答案。
    观察下图:

    左边的蓝色节点从下往上走,在蓝色节点到达[1,4]时,注意到,左边蓝色节点之前计算过的所有节点(即[3,4])都是目前蓝色节点的子节点也就是说,当前蓝色节点的Add是要影响这个节点已经计算过的所有数。多用一个变量来记录这个蓝色节点已经计算过多少个数,根据个数以及当前蓝色节点的Add,来更新最终答案。
    更新完答案之后,再加上[5,8]的答案,同时当前蓝色节点计算过的个数要+4(因为[5,8]里有4个数)
    然后当这个节点到达[1,8]节点时,可以更新[1,8]的Add.
    这里,本来左右蓝色节点相遇之后就不再需要计算了,但是由于有了Add标记,左右蓝色节点的公共祖先上的Add标记会影响目前的所有数,所以还需要一路向上查询到根,沿路根据Add更新答案。

    区间修改:

    这里讲完了查询,再来讲讲修改
    修改的时候,给某个区间的Add加上了C,这个区间的子区间向上查询时,会经过这个节点,也就是会计算这个Add,但是
    如果路径经过这个区间的父节点,就不会计算这个节点的Add,也就会出错。这里其实跟递归线段树一样,改了某个区间的Add
    仍需要向上更新所有包含这个区间的Sum,来保持上面所有节点的正确性。

    五:非递归实现

    以下以维护数列区间和的线段树为例,演示最基本的非递归线段树代码。

    (0)定义

    1. //   
    2. #define maxn 100007  
    3. int A[maxn],n,N;//原数组,n为原数组元素个数 ,N为扩充元素个数   
    4. int Sum[maxn<<2];//区间和   
    5. int Add[maxn<<2];//懒惰标记   

    (1)建树:

    1. //  
    2. void Build(int n){  
    3.     //计算N的值   
    4.     N=1;while(N < n+2) N <<= 1;  
    5.     //更新叶节点   
    6.     for(int i=1;i<=n;++i) Sum[N+i]=A[i];//原数组下标+N=存储下标  
    7.     //更新非叶节点   
    8.     for(int i=N-1;i>0;--i){  
    9.         //更新所有非叶节点的统计信息   
    10.         Sum[i]=Sum[i<<1]+Sum[i<<1|1];  
    11.         //清空所有非叶节点的Add标记   
    12.         Add[i]=0;  
    13.     }  
    14. }   

    (2)点修改:

    A[L]+=C
    1. //  
    2. void Update(int L,int C){  
    3.     for(int s=N+L;s;s>>=1){  
    4.         Sum[s]+=C;  
    5.     }  
    6. }   

    (3)点修改下的区间查询:

    求A[L..R]的和(点修改没有使用Add所以不需要考虑)
    代码非常简洁,也不难理解,
    s和t分别代表之前的论述中的左右蓝色节点,其余的代码根据之前的论述应该很容易看懂了。
    s^t^1 在s和t的父亲相同时值为0,终止循环。
    两个if是判断s和t分别是左子节点还是右子节点,根据需要来计算Sum
    1. //  
    2. int Query(int L,int R){  
    3.     int ANS=0;  
    4.     for(int s=N+L-1,t=N+R+1;s^t^1;s>>=1,t>>=1){  
    5.         if(~s&1) ANS+=Sum[s^1];  
    6.         if( t&1) ANS+=Sum[t^1];  
    7.     }  
    8.     return ANS;  
    9. }   

    (4)区间修改:

    A[L..R]+=C
    1. <span style="font-size:14px;">//  
    2. void Update(int L,int R,int C){  
    3.     int s,t,Ln=0,Rn=0,x=1;  
    4.     //Ln:  s一路走来已经包含了几个数  
    5.     //Rn:  t一路走来已经包含了几个数  
    6.     //x:   本层每个节点包含几个数  
    7.     for(s=N+L-1,t=N+R+1;s^t^1;s>>=1,t>>=1,x<<=1){  
    8.         //更新Sum  
    9.         Sum[s]+=C*Ln;  
    10.         Sum[t]+=C*Rn;  
    11.         //处理Add  
    12.         if(~s&1) Add[s^1]+=C,Sum[s^1]+=C*x,Ln+=x;  
    13.         if( t&1) Add[t^1]+=C,Sum[t^1]+=C*x,Rn+=x;  
    14.     }  
    15.     //更新上层Sum  
    16.     for(;s;s>>=1,t>>=1){  
    17.         Sum[s]+=C*Ln;  
    18.         Sum[t]+=C*Rn;  
    19.     }   
    20. } </span>  

    (5)区间修改下的区间查询:

    求A[L..R]的和
    1. //  
    2. int Query(int L,int R){  
    3.     int s,t,Ln=0,Rn=0,x=1;  
    4.     int ANS=0;  
    5.     for(s=N+L-1,t=N+R+1;s^t^1;s>>=1,t>>=1,x<<=1){  
    6.         //根据标记更新   
    7.         if(Add[s]) ANS+=Add[s]*Ln;  
    8.         if(Add[t]) ANS+=Add[t]*Rn;  
    9.         //常规求和   
    10.         if(~s&1) ANS+=Sum[s^1],Ln+=x;  
    11.         if( t&1) ANS+=Sum[t^1],Rn+=x;   
    12.     }  
    13.     //处理上层标记  
    14.     for(;s;s>>=1,t>>=1){  
    15.         ANS+=Add[s]*Ln;  
    16.         ANS+=Add[t]*Rn;  
    17.     }  
    18.     return ANS;  
    19. }  

    六:线段树解题模型

    给出线段树解题模型以及一些例题。

    先对图中各个名字给出定义:
    问题:可能可以用线段树解决的问题
    目标信息:由问题转换而成的,为了解决问题而需要统计的信息(可能不满足区间加法)。
    点信息:每个点储存的信息
    区间信息:每个区间维护的信息(线段树节点定义) (必须满足区间加法)
    区间信息包括 统计信息标记
    --------统计信息:统计节点代表的区间的信息,一般自下而上更新
    --------标记:对操作进行标记(在区间修改时需要),一般自上而下传递,或者不传递
    区间加法:实现区间加法的代码
    查询:实现查询操作的代码
    修改:实现修改操作的代码

    图中紫线右边是实际线段树的实现,左边是对问题的分析以及转换。

    一个问题,若能转换成对一些连续点的修改或者统计,就可以考虑用线段树解决。
    首先确定目标信息点信息,然后将目标信息转换成区间信息(必要时,增加信息,使之符合区间加法)。
    之后就是线段树的代码实现了,包括:
    1.区间加法 
    2.建树,点信息到区间信息的转换 
    3.每种操作(包括查询,修改)对区间信息的调用,修改

    这样,点的信息不同,区间信息不同,线段树可以维护很多种类的信息,所以是一种非常实用的数据结构。
    可以解决很多问题,下面给出几个例子来说明。

    (1):字符串哈希

    题目:URAL1989 Subpalindromes    题解
    给定一个字符串(长度<=100000),有两个操作。   1:改变某个字符。 2:判断某个子串是否构成回文串。 
    直接判断会超时。这个题目,是用线段树维护字符串哈希
    对于一个字符串a[0],a[1],...,a[n-1] 它对应的哈希函数为a[0]+a[1]*K + a[2]*K^2 +...+a[n-1]*K^(n-1)
    再维护一个从右往左的哈希值:a[0]*K^(n-1) + a[1]*K^(n-2) +...+a[n-1]
    若是回文串,则左右的哈希值会相等。而左右哈希值相等,则很大可能这是回文串。
    若出现误判,可以再用一个K2,进行二次哈希判断,可以减小误判概率。
    实现上,哈希值最好对某个质数取余数,这样分布更均匀。


    解题模型:
    问题经过转换之后:
    目标信息:某个区间的左,右哈希值
    点信息:一个字符
    目标信息已经符合区间加法,所以区间信息=目标信息
    所以线段树的结构为:
    区间信息:区间哈希值
    点信息:一个字符
    代码主要需要注意2个部分:
    1.区间加法 :(PushUp函数,Pow[a]=K^a)
    2.点信息->区间信息:(叶节点上,区间只包含一个点,所以需要将点信息转换成区间信息)
    修改以及查询,在有了区间加法的情况下,没什么难度了。

    可以看出,上述解题过程的核心,就是找到区间信息, 写好区间加法
    下面是维护区间和的部分,下面的代码没有取余,也就是实际上是对2^32取余数,这样其实分布不均匀,容易出现误判:
    1. //   
    2. #define K 137  
    3. #define maxn 100001   
    4. char str[maxn];  
    5. int Pow[maxn];//K的各个次方   
    6. struct Node{  
    7.     int KeyL,KeyR;  
    8.     Node():KeyL(0),KeyR(0){}  
    9.     void init(){KeyL=KeyR=0;}  
    10. }node[maxn<<2];  
    11. void PushUp(int L,int R,int rt){  
    12.     node[rt].KeyL=node[rt<<1].KeyL+node[rt<<1|1].KeyL*Pow[L];  
    13.     node[rt].KeyR=node[rt<<1].KeyR*Pow[R]+node[rt<<1|1].KeyR;  
    14. }  

    (2):最长连续零

    题目:Codeforces 527C Glass Carving   题解
    题意是给定一个矩形,不停地纵向或横向切割,问每次切割后,最大的矩形面积是多少。
    最大矩形面积=最长的长*最宽的宽
    这题,长宽都是10^5,所以,用01序列表示每个点是否被切割,然后,
    最长的长就是长的最长连续0的数量+1
    最长的宽就是宽的最长连续0的数量+1
    于是用线段树维护最长连续零

    问题转换成:
    目标信息:区间最长连续零的个数
    点信息:0 或 1
    由于目标信息不符合区间加法,所以要扩充目标信息。

    转换后的线段树结构
    区间信息:从左,右开始的最长连续零,本区间是否全零,本区间最长连续零。
    点信息:0 或 1
    然后还是那2个问题:

    1.区间加法:
    这里,一个区间的最长连续零,需要考虑3部分:
    -(1):左子区间最长连续零
    -(2):右子区间最长连续零
    -(3):左右子区间拼起来,而在中间生成的连续零(可能长于两个子区间的最长连续零)
    而中间拼起来的部分长度,其实是左区间从右开始的最长连续零+右区间从左开始的最长连续零。
    所以每个节点需要多两个量,来存从左右开始的最长连续零。
    然而,左开始的最长连续零分两种情况,
    --(1):左区间不是全零,那么等于左区间的左最长连续零
    --(2):左区间全零,那么等于左区间0的个数加上右区间的左最长连续零
    于是,需要知道左区间是否全零,于是再多加一个变量。
    最终,通过维护4个值,达到了维护区间最长连续零的效果。

    2.点信息->区间信息 : 
    如果是0,那么  最长连续零=左最长连续零=右最长连续零=1 ,全零=true。
    如果是1,那么  最长连续零=左最长连续零=右最长连续零=0, 全零=false。

    至于修改和查询,有了区间加法之后,机械地写一下就好了。
    由于这里其实只有对整个区间的查询,所以查询函数是不用写的,直接找根的统计信息就行了。

    代码如下:
    1. //  
    2. #define maxn 200001  
    3. using namespace std;  
    4. int L[maxn<<2][2];//从左开始连续零个数   
    5. int R[maxn<<2][2];//从右   
    6. int Max[maxn<<2][2];//区间最大连续零   
    7. bool Pure[maxn<<2][2];//是否全零   
    8. int M[2];  
    9. void PushUp(int rt,int k){//更新rt节点的四个数据  k来选择两棵线段树  
    10.     Pure[rt][k]=Pure[rt<<1][k]&&Pure[rt<<1|1][k];   
    11.     Max[rt][k]=max(R[rt<<1][k]+L[rt<<1|1][k],max(Max[rt<<1][k],Max[rt<<1|1][k]));  
    12.     L[rt][k]=Pure[rt<<1][k]?L[rt<<1][k]+L[rt<<1|1][k]:L[rt<<1][k];  
    13.     R[rt][k]=Pure[rt<<1|1][k]?R[rt<<1|1][k]+R[rt<<1][k]:R[rt<<1|1][k];  
    14. }  

    (3):计数排序

    题目:Codeforces 558E A Simple Task  题解

    给定一个长度不超过10^5的字符串(小写英文字母),和不超过5000个操作。

    每个操作 L R K 表示给区间[L,R]的字符串排序,K=1为升序,K=0为降序。

    最后输出最终的字符串。


    题目转换成:

    目标信息:区间的计数排序结果

    点信息:一个字符

    这里,目标信息是符合区间加法的,但是为了支持区间操作,还是需要扩充信息。


    转换后的线段树结构

    区间信息:区间的计数排序结果,排序标记,排序种类(升,降)

    点信息:一个字符


    代码中需要解决的四个问题(难点在于标记下推和区间修改):

    1.区间加法

    对应的字符数量相加即可(注意标记是不上传的,所以区间加法不考虑标记)。

    2.点信息->区间信息:把对应字符的数量设置成1,其余为0,排序标记为false。

    3.标记下推

    明显,排序标记是绝对标记,也就是说,标记对子节点是覆盖式的效果,一旦被打上标记,下层节点的一切信息都无效。

    下推标记时,根据自己的排序结果,将元素分成对应的部分,分别装入两个子树。

    4.区间修改

    这个是难点,由于要对某个区间进行排序,首先对各个子区间求和(求和之前一定要下推标记,才能保证求的和是正确的)

    由于使用的计数排序,所以求和之后,新顺序也就出来了。然后按照排序的顺序按照每个子区间的大小来分配字符。

    操作后,每个子区间都被打上了标记。


    最后,在所有操作结束之后,一次下推所有标记,就可以得到最终的字符序列。


    这里只给出节点定义。
    1. //   
    2. struct Node{  
    3.     int d[26];//计数排序   
    4.     int D;//总数  
    5.     bool sorted;//是否排好序   
    6.     bool Inc;//是否升序  
    7. };  

    (4)总结:

    总结一下,线段树解题步骤。

    :将问题转换成点信息目标信息
    即,将问题转换成对一些点的信息的统计问题。

    :将目标信息根据需要扩充成区间信息
    1.增加信息符合区间加法。
    2.增加标记支持区间操作。

    :代码中的主要模块:
    1.区间加法 
    2.标记下推 
    3.点信息->区间信息 
    4.操作(各种操作,包括修改和查询)


    完成第一步之后,题目有了可以用线段树解决的可能。
    完成第二步之后,题目可以由线段树解决。
    第三步就是慢慢写代码了。

    七:扫描线

    线段树的一大应用是扫描线。

    先把相关题目给出,有兴趣可以去找来练习:

    POJ 1177 Picture:给定若干矩形求合并之后的图形周长    题解
    HDU 1255 覆盖的面积:给定平面上若干矩形,求出被这些矩形覆盖过至少两次的区域的面积.   题解
    HDU 3642 Get The Treasury:给定若干空间立方体,求重叠了3次或以上的体积(这个是扫描面,每个面再扫描线)题解
    再补充一道稍微需要一点模型转换的扫描线题:
    POJ 2482 Stars in your window : 给定一些星星的位置和亮度,求用W*H的矩形能够框住的星星亮度之和最大为多少。
    这题是把星星转换成了矩形,把矩形框转换成了点,然后再扫描线。  题解


    扫描线求重叠矩形面积:

    考虑下图中的四个矩形:





    观察第三个图:
    扫描线的思路:使用一条垂直于X轴的直线,从左到右来扫描这个图形,明显,只有在碰到矩形的左边界或者右边界的时候,
    这个线段所扫描到的情况才会改变,所以把所有矩形的入边,出边按X值排序。然后根据X值从小到大去处理,就可以
    用线段树来维护扫描到的情况。如上图,X1到X8是所有矩形的入边,出边的X坐标。
    而红色部分的线段,是这样,如果碰到矩形的入边,就把这条边加入,如果碰到出边,就拿走。红色部分就是有线段覆盖的部分。
    要求面积,只需要知道图中的L1到L8。而线段树就是用来维护这个L1到L8的。
    扫描线算法流程:

    X1:首先遇到X1,将第一条线段加入线段树,由线段树统计得到线段长度为L1.

    X2:然后继续扫描到X2,此时要进行两个动作:
    1.计算面积,目前扫过的面积=L1*(X2-X1)
    2.更新线段。由于X2处仍然是入边,所以往线段树中又加了一条线段,加的这条线段可以参考3幅图中的第一幅。
    然后线段树自动得出此时覆盖的线段长度为L2 (注意两条线段有重叠部分,重叠部分的长度只能算一次)

    X3:继续扫描到X3,步骤同X2
    先计算 扫过的面积+=L2*(X3-X2)
    再加入线段,得到L3.

    X4:扫描到X4有些不一样了。
    首先还是计算  扫过的面积+=L3*(X4-X3)
    然后这时遇到了第一个矩形的出边,这时要从线段树中删除一条线段。
    删除之后的结果是线段树中出现了2条线段,线段树自动维护这两条线段的长度之和L4

    讲到这里算法流程应该很清晰了。
    首先将所有矩形的入边,出边都存起来,然后根据X值排序。
    这里用一个结构体,来存这些信息,然后排序。
    1. //  
    2. struct LINE{  
    3.     int x;//横坐标   
    4.     int y1,y2;//矩形纵向线段的左右端点   
    5.     bool In;//标记是入边还是出边   
    6.     bool operator < (const Line &B)const{return x < B.x;}  
    7. }Line[maxn];   

    然后扫描的时候,需要两个变量,一个叫PreL,存前一个x的操作结束之后的L值,和X,前一个横坐标。
    假设一共有Ln条线段,线段下标从0开始,已经排好序。
    那么算法大概是这样:
    1. //  
    2. int PreL=0;//前一个L值,刚开始是0,所以第一次计算时不会引入误差   
    3. int X;//X值   
    4. int ANS=0;//存累计面积  
    5. int I=0;//线段的下标   
    6.   
    7. while(I < Ln){  
    8.     //先计算面积   
    9.     ANS+=PreL*(Line[I].x-X);  
    10.     X=Line[I].x;//更新X值  
    11.     //对所有X相同的线段进行操作   
    12.     while(I < Ln && Line[I].x == X){  
    13.         //根据入边还是出边来选择加入线段还是移除线段   
    14.         if(Line[I].In) Cover(Line[I].y1,Line[I].y2-1,1,n,1);  
    15.         else         Uncover(Line[I].y1,Line[I].y2-1,1,n,1);  
    16.         ++I;  
    17.     }   
    18. }  

    无论是求面积还是周长,扫描线的结构大概就是上面的样子。

    需要解决的几个问题:

    现在有两点需要说明一下。
    (1):线段树进行线段操作时,每个点的含义(比如为什么Cover函数中,y2后面要-1)。
    (2):线段树如何维护扫描线过程中的覆盖线段长度。
    (3):线段树如何维护扫描线过程中线段的数量。

    (1):线段树中点的含义

    线段树如果没有离散化,那么线段树下标为1,就代表线段[1,2)
    线段树下标为K的时候,代表的线段为[K,K+1) (长度为1)
    所以,将上面的所有线段都化为[y1,y2)就可以理解了,线段[y1,y2)只包括线段树下标中的y1,y1+1,...,y2-1
    当y值的范围是10^9时,就不能再按照上面的办法按值建树了,这时需要离散化。
    下面是离散化的代码:
    1. //  
    2. int Rank[maxn],Rn;  
    3. void SetRank(){//调用前,所有y值被无序存入Rank数组,下标为[1..Rn]   
    4.     int I=1;  
    5.     //第一步排序   
    6.     sort(Rank+1,Rank+1+Rn);   
    7.     //第二步去除重复值   
    8.     for(int i=2;i<=Rn;++i) if(Rank[i]!=Rank[i-1]) Rank[++I]=Rank[i];  
    9.     Rn=I;  
    10.     //此时,所有y值被从小到大无重复地存入Rank数组,下标为[1..Rn]   
    11. }   
    12. int GetRank(int x){//给定x,求x的下标   
    13.     //二分法求下标   
    14.     int L=1,R=Rn,M;//[L,R] first >=x  
    15.     while(L!=R){  
    16.         M=(L+R)>>1;  
    17.         if(Rank[M]<x) L=M+1;  
    18.         else R=M;  
    19.     }  
    20.     return L;  
    21. }  

    此时,线段树的下标的含义就变成:如果线段树下标为K,代表线段[ Rank[K] , Rank[K+1] )。
    下标为K的线段长度为Rank[K+1]-Rank[K]
    所以此时叶节点的线段长度不是1了。
    这时,之前的扫描线算法的函数调用部分就稍微的改变了一点:
    1. //   
    2. if(Line[I].In) Cover(GetRank(Line[I].y1),GetRank(Line[I].y2)-1,1,n,1);  
    3. else         Uncover(GetRank(Line[I].y1),GetRank(Line[I].y2)-1,1,n,1);  
    看着有点长,其实不难理解,只是多了一步从y值到离散之后的下标的转换。

    注意一点,如果下标为K的线段长度为Rank[K+1]-Rank[K],那么下标为Rn的线段树的长度呢?
    其实这个不用担心,Rank[Rn]作为所有y值中的最大值,它肯定是一个线段的右端点,
    而右端点求完离散之后的下标还要-1,所以上面的线段覆盖永远不会覆盖到Rn。
    所以线段树其实只需要建立Rn-1个元素,因为下标为Rn的无法定义,也不会被访问。
    不过有时候留着也有好处,这个看具体实现时自己取舍。

    (2):如何维护覆盖线段长度

    先提一个小技巧,一般,利用两个子节点来更新本节点的函数写成PushUp();
    但是,对于比较复杂的子区间合并问题,在区间查询的时候,需要合并若干个子区间。
    而合并子区间是没办法用PushUp函数的。于是,对于比较复杂的问题,把单个节点的信息写成一个结构体。
    在结构体内重载运算符"+",来实现区间合并。这样,不仅在PushUp函数可以调用这个加法,区间询问时也可以
    调用这个加法,这样更加方便。

    下面给出维护线段覆盖长度的节点定义:
    1. //  
    2. struct Node{  
    3.     int Cover;//区间整体被覆盖的次数   
    4.     int L;//Length : 所代表的区间总长度  
    5.     int CL;//Cover Length :实际覆盖长度  
    6.     Node operator +(const Node &B)const{  
    7.         Node X;  
    8.         X.Cover=0;//因为若上级的Cover不为0,不会调用子区间加法函数   
    9.         X.L=L+B.L;  
    10.         X.CL=CL+B.CL;  
    11.         return X;  
    12.     }  
    13. }K[maxn<<2];  


    这样定义之后,区间的信息更新是这样的:
    若本区间的覆盖次数大于0,那么令CL=L,直接为全覆盖,不管下层是怎么覆盖的,反正本区间已经全被覆盖。
    若本区间的覆盖次数等于0,那么调用上面结构体中的加法函数,利用子区间的覆盖来计算。
     
    加入一条线段就是给每一个分解的子区间的Cover+1,删除线段就-1,每次修改Cover之后,更新区间信息。
    这里完全没有下推标记的过程。
     
    查询的代码如下:
    如果不把区间加法定义成结构体内部的函数,而是定义在PushUp函数内,那么这里几乎就要重写一遍区间合并。
    因为PushUp在这里用不上。
    1. //  
    2. Node Query(int L,int R,int l,int r,int rt){  
    3.     if(L <= l && r <= R){  
    4.         return K[rt];  
    5.     }  
    6.     int m=(l+r)>>1;  
    7.     Node LANS,RANS;  
    8.     int X=0;  
    9.     if(L <= m) LANS=Query(L,R,ls),X+=1;  
    10.     if(R >  m) RANS=Query(L,R,rs),X+=2;  
    11.     if(X==1) return LANS;  
    12.     if(X==2) return RANS;  
    13.     return LANS+RANS;  
    14. }  

    维护线段覆盖3次或以上的长度:

    1. //  
    2. struct Nodes{    
    3.     int C;//Cover    
    4.     int CL[4];//CoverLength[0~3]    
    5.     //CL[i]表示被覆盖了大于等于i次的线段长度,CL[0]其实就是线段总长   
    6. }ST[maxn<<2];    
    7. void PushUp(int rt){    
    8.     for(int i=1;i<=3;++i){    
    9.         if(ST[rt].C < i) ST[rt].CL[i]=ST[rt<<1].CL[i-ST[rt].C]+ST[rt<<1|1].CL[i-ST[rt].C];    
    10.         else ST[rt].CL[i]=ST[rt].CL[0];    
    11.     }    
    12. }    

    这里给出节点定义和PushUp().
    更新节点信息的思路大概就是:
    假设要更新CL[3],然后发现本节点被覆盖了2次,那么本节点被覆盖三次或以上的长度就等于子节点被覆盖了1次或以上的长度之和。
    而CL[0]建树时就赋值,之后不需要修改。

    (3):如何维护扫描线过程中线段的数量

    1. //   
    2. struct Node{    
    3.     int cover;//完全覆盖层数    
    4.     int lines;//分成多少个线段    
    5.     bool L,R;//左右端点是否被覆盖    
    6.     Node operator +(const Node &B){//连续区间的合并     
    7.         Node C;    
    8.         C.cover=0;    
    9.         C.lines=lines+B.lines-(R&&B.L);    
    10.         C.L=L;C.R=B.R;    
    11.         return C;    
    12.     }    
    13. }K[maxn<<2];    

    要维护被分成多少个线段,就需要记录左右端点是否被覆盖,知道了这个,就可以合并区间了。
    左右两个区间合并时,若左区间的最右侧有线段且右区间的最左侧也有线段,那么这两个线段会合二为一,于是总线段数量会少1.

    扫描线求重叠矩形周长:


    这个图是在原来的基础上多画了一些东西,这次是要求周长。
    所有的横向边都画了紫色,所有的纵向边画了绿色。

    先考虑绿色的边,由图可以观察到,绿色边的长度其实就是L的变化值。
    比如考虑X1,本来L是0,从0变到L1,所以绿色边长为L1.
    再考虑X2,由L1变成了L2,所以绿色边长度为L2-L1,
    于是,绿色边的长度就是L的变化值(注意上图中令L0=0,L9=0)。
    因为长度是从0开始变化,最终归0.

    再考虑紫色的边,要计算紫色边,其实就是计算L的线段是有几个线段组成的,每个线段会贡献两个端点(紫色圆圈)
    而每个端点都会向右延伸出一条紫色边一直到下一个X值。

    所以周长就是以上两部分的和。而两部分怎么维护,前面都讲过了,下面给出代码。
    1. //   
    2. struct Node{    
    3.     int cover;//完全覆盖层数    
    4.     int lines;//分成多少个线段    
    5.     bool L,R;//左右端点是否被覆盖    
    6.     int CoverLength;//覆盖长度     
    7.     int Length;//总长度     
    8.     Node(){}    
    9.     Node(int cover,int lines,bool L,bool R,int CoverLength):cover(cover),lines(lines),L(L),R(R),CoverLength(CoverLength){}    
    10.     Node operator +(const Node &B){//连续区间的合并     
    11.         Node C;    
    12.         C.cover=0;    
    13.         C.lines=lines+B.lines-(R&&B.L);    
    14.         C.CoverLength=CoverLength+B.CoverLength;    
    15.         C.L=L;C.R=B.R;    
    16.         C.Length=Length+B.Length;    
    17.         return C;    
    18.     }    
    19. }K[maxn<<2];    
    20. void PushUp(int rt){//更新非叶节点     
    21.     if(K[rt].cover){    
    22.         K[rt].CoverLength=K[rt].Length;    
    23.         K[rt].L=K[rt].R=K[rt].lines=1;    
    24.     }    
    25.     else{    
    26.         K[rt]=K[rt<<1]+K[rt<<1|1];    
    27.     }    
    28. }    

    扫描的代码:
    1. int PreX=L[0].x;//前X坐标     
    2. int ANS=0;//目前累计答案     
    3. int PreLength=0;//前线段总长    
    4. int PreLines=0;//前线段数量     
    5. Build(1,20001,1);    
    6. for(int i=0;i<nL;++i){    
    7.     //操作     
    8.     if(L[i].c) Cover(L[i].y1,L[i].y2-1,1,20001,1);    
    9.     else Uncover(L[i].y1,L[i].y2-1,1,20001,1);    
    10.     //更新横向的边界     
    11.     ANS+=2*PreLines*(L[i].x-PreX);    
    12.     PreLines=K[1].lines;    
    13.     PreX=L[i].x;    
    14.     //更新纵向边界     
    15.     ANS+=abs(K[1].CoverLength-PreLength);    
    16.     PreLength=K[1].CoverLength;    
    17. }    
    18. //输出答案     
    19. printf("%d\n",ANS);    


    求立方体重叠3次或以上的体积:

    这个首先扫描面,每个面内求重叠了3次或以上的面积,然后乘以移动距离就是体积。
    面内扫描线,用线段树维护重叠了3次或以上的线段长度,然后用长度乘移动距离就是重叠了3次或以上的面积。
    扫描面基本原理都跟扫描线一样,就是嵌套了一层而已,写的时候细心一点就没问题了。


    八:可持久化 (主席树)

    可持久化线段树,也叫主席树。
    可持久化数据结构思想,就是保留整个操作的历史,即,对一个线段树进行操作之后,保留访问操作前的线段树的能力。
    最简单的方法,每操作一次,建立一颗新树。这样对空间的需求会很大。
    而注意到,对于点修改,每次操作最多影响个节点,于是,其实操作前后的两个线段树,结构一样,
    而且只有个节点不同,其余的节点都一样,于是可以重复利用其余的点。
    这样,每次操作,会增加个节点。
    于是,这样的线段树,每次操作需要O(log2(n))的空间。

    题目:HDU 2665 Kth number      题解
    给定10万个数,10万个询问。
    每个询问,问区间[L,R]中的数,从小到大排列的话,第k个数是什么。

    这个题,首先对十万个数进行离散化,然后用线段树来维护数字出现的次数。
    每个节点都存出现次数,那么查询时,若左节点的数的个数>=k,就往左子树递归,否则往右子树递归。
    一直到叶节点,就找到了第k大的数。

    这题的问题是,怎么得到一个区间的每个数出现次数。
    注意到,数字的出现次数是满足区间减法的。
    于是要求区间[L,R]的数,其实就是T[R]-T[L-1]  ,其中T[X]表示区间[1,X]的数形成的线段树。
    现在的问题就是,如何建立这10万个线段树。

    由之前的分析,需要O(n log2(n))的空间
    下面是代码:
    1. //主席树     
    2. int L[maxnn],R[maxnn],Sum[maxnn],T[maxn],TP;//左右子树,总和,树根,指针     
    3. void Add(int &rt,int l,int r,int x){//建立新树,l,r是区间, x是新加入的数字的排名  
    4.     ++TP;L[TP]=L[rt];R[TP]=R[rt];Sum[TP]=Sum[rt]+1;rt=TP;//复制&新建    
    5.     if(l==r) return;    
    6.     int m=(l+r)>>1;    
    7.     if(x <= m) Add(L[rt],l,m,x);    
    8.     else       Add(R[rt],m+1,r,x);    
    9. }    
    10. int Search(int TL,int TR,int l,int r,int k){//区间查询第k大    
    11.     if(l==r) return l;//返回第k大的下标    
    12.     int m=(l+r)>>1;    
    13.     if(Sum[L[TR]]-Sum[L[TL]]>=k) return Search(L[TL],L[TR],l,m,k);    
    14.     else return Search(R[TL],R[TR],m+1,r,k-Sum[L[TR]]+Sum[L[TL]]);    
    15. }    

    以上就是主席树部分的代码。
    熟悉SBT的,应该都很熟悉这种表示方法。
    L,R是伪指针,指向左右子节点。
    特殊之处是,0 表示空树,并且 L[0]=R[0]=0.
    也就是说,空树的左右子树都是空树。
    而本题中,每一颗树其实都是完整的,刚开始有一颗空树。
    但是刚开始的空树,真的需要用空间去存吗?
    其实不需要,刚开始的空树有这些性质:
    1.每个节点的Sum值为0
    2.每个非叶节点的左右子节点的Sum值也是0

    而SBT的空树刚好满足这个性质。而线段树不依赖L,R指针来结束递归。
    线段树是根据区间l,r来结束的,所以不会出现死循环。
    所以只需要把Sum[0]=0;那么刚开始就不需要建树了,只有每个操作的个节点。

    这个线段树少了表示父节点的int rt,因为不需要(也不能够)通过rt来找子节点了,而是直接根据L,R来找。

    -----------------------------     补充     -------------------------------------

    终于又找到一道可以用主席树的题目了:Codeforces 650D.Zip-line  题解
    做这题之前需要会求普通的LIS问题(最长上升子序列问题)。

    九:练习题

    适合非递归线段树的题目:


    Codeforces 612D The Union of k-Segments :  题解
    题意:线段求交,给定一堆线段,按序输出被覆盖k次或以上的线段和点。
    基础题,先操作,最后一次下推标记,然后输出,
    维护两个线段树,一个线段覆盖,一个点覆盖。

    Codeforces 35E Parade : 题解

    题意:给定若干矩形,下端挨着地面,求最后的轮廓形成的折线,要求输出每一点的坐标。

    思路:虽然是区间修改的线段树,但只需要在操作结束后一次下推标记,然后输出,所以适合非递归线段树。


    URAL 1846 GCD2010 :  题解

    题意:总共10万个操作,每次向集合中加入或删除一个数,求集合的最大公因数。(规定空集的最大公因数为1)


    Codeforces 12D Ball :   题解

    题意:

    给N (N<=500000)个点,每个点有x,y,z ( 0<= x,y,z <=10^9 )

    对于某点(x,y,z),若存在一点(x1,y1,z1)使得x1 > x && y1 > y && z1 > z 则点(x,y,z)是特殊点。

    问N个点中,有多少个特殊点。


    提示:排序+线段树


    Codeforces 19D Points : 题解

     

    题意:

    给定最多20万个操作,共3种:

    1.add x y         :加入(x,y)这个点

    2.remove x y  :删除(x,y)这个点

    3.find x y         :找到在(x,y)这点右上方的x最小的点,若x相同找y最小的点,输出这点坐标,若没有,则输出-1.

    提示:排序,线段树套平衡树


    Codeforces 633E Startup Funding : 题解

    这题需要用到一点概率论,组合数学知识,和二分法。

    非递归线段树在这题中主要解决RMQ问题(区间最大最小值问题),由于不带修改,这题用Sparse Table求解RMQ是标答。

    因为RMQ询问是在二分法之内求的,而Sparse Table可以做到O(1)查询,所以用Sparse Table比较好,总复杂度O(n*log(n))。

    不过非递归线段树也算比较快的了,虽然复杂度是O(n*log(n)*log(n)),还是勉强过了这题。


    扫描线题目:

     

    POJ 1177 Picture:给定若干矩形求合并之后的图形周长    题解
    HDU 1255 覆盖的面积:给定平面上若干矩形,求出被这些矩形覆盖过至少两次的区域的面积.   题解
    HDU 3642 Get The Treasury:给定若干空间立方体,求重叠了3次或以上的体积(这个是扫描面,每个面再扫描线)题解
    POJ 2482 Stars in your window : 给定一些星星的位置和亮度,求用W*H的矩形能够框住的星星亮度之和最大为多少。  题解

    递归线段树题目:

    Codeforces 558E A Simple Task  题解

    给定一个长度不超过10^5的字符串(小写英文字母),和不超过5000个操作。

    每个操作 L R K 表示给区间[L,R]的字符串排序,K=1为升序,K=0为降序。

    最后输出最终的字符串。


    Codeforces 527C Glass Carving  :  题解
    给定一个矩形,不停地纵向或横向切割,问每次切割后,最大的矩形面积是多少。

    URAL1989 Subpalindromes    题解
    给定一个字符串(长度<=100000),有10万个操作。
    操作有两种:   
    1:改变某个字符。 
    2:判断某个子串是否构成回文串。 

    HDU 4288 Coder :  题解
     题意:对一个集合进行插入与删除操作。要求询问某个时刻,集合中的元素从小到大排序之后,序号%5 ==3 的元素值之和。
    这题其实不一定要用线段树去做的,不过线段树还是可以做的。

    HDU 2795 BillBoard : 题解

    题意:有一个板,h行,每行w长度的位置。每次往上面贴一张海报,长度为1*wi .

    每次贴的时候,需要找到最上面的,可以容纳的空间,并且靠边贴。


    Codeforces 374D Inna and Sequence :题解
    题意:给定百万个数a[m],然后有百万个操作,每次给现有序列加一个字符(0或1),或者删掉已有序列中,第 a[0] 个,第a[1]个,...,第a[m]个。

    Codeforces 482B Interesting Array:  题解

    题意就是,给定n,m.

    满足m个条件的n个数,或说明不存在。

    每个条件的形式是,给定 Li,Ri,Qi ,要求   a[Li]&a[Li+1]&...&a[Ri] = Qi ;

    Codeforces 474E Pillar (线段树+动态规划):  题解

    题意就是,给定10^5 个数(范围10^15),求最长子序列使得相邻两个数的差大于等于 d。


    POJ 2777  Count Color :   题解

    给线段涂颜色,最多30种颜色,10万个操作。

    每个操作给线段涂色,或问某一段线段有多少种颜色。

    30种颜色用int的最低30位来存,然后线段树解决。


    URAL 1019 Line Painting: 线段树的区间合并  题解

    给一段线段进行黑白涂色,最后问最长的一段白色线段的长度。


    Codeforces 633H Fibonacci-ish II  :题解

    这题需要用到莫队算法(Mo's Algorithm)+线段树区间修改,不过是单边界的区间,写起来挺有趣。

    另一种解法就是暴力,很巧妙的方法,高复杂度+低常数居然就这么给过了。


    树套树题目:

    ZOJ 2112 Dynamic Rankings 动态区间第k大  题解
    做法:树状数组套主席树 或者 线段树套平衡树

    Codeforces 605D Board Game :  题解
    做法:广度优先搜索(BFS)  +  线段树套平衡树

    Codeforces 19D Points : 题解

     

    题意:

    给定最多20万个操作,共3种:

    1.add x y         :加入(x,y)这个点

    2.remove x y  :删除(x,y)这个点

    3.find x y         :找到在(x,y)这点右上方的x最小的点,若x相同找y最小的点,输出这点坐标,若没有,则输出-1.

    提示:排序,线段树套平衡树



    转载请注明出处: 原文地址:http://blog.csdn.net/zearot/article/details/48299459

    展开全文
  • 线段树总结

    2018-04-18 21:51:50
    线段树详解   By 岩之痕   目录: 一:综述 二:原理 三:递归实现 四:非递归原理 五:非递归实现 六:线段树解题模型 七:扫描线 八:可持久化 (主席树) 九:练习题       一:综述 假设有...

    线段树详解

     

    By 岩之痕

     

    目录:

    一:综述

    二:原理

    三:递归实现

    四:非递归原理

    五:非递归实现

    六:线段树解题模型

    七:扫描线

    八:可持久化 (主席树)

    九:练习题

     

     

     

    一:综述

    假设有编号从1到n的n个点,每个点都存了一些信息,用[L,R]表示下标从L到R的这些点。

    线段树的用处就是,对编号连续的一些点进行修改或者统计操作,修改和统计的复杂度都是O(log2(n)).

     

    线段树的原理,就是,将[1,n]分解成若干特定的子区间(数量不超过4*n),然后,将每个区间[L,R]都分解为

    少量特定的子区间,通过对这些少量子区间的修改或者统计,来实现快速对[L,R]的修改或者统计。

     

    由此看出,用线段树统计的东西,必须符合区间加法,否则,不可能通过分成的子区间来得到[L,R]的统计结果。

     

    符合区间加法的例子:

    数字之和——总数字之和 = 左区间数字之和 + 右区间数字之和

    最大公因数(GCD)——总GCD = gcd( 左区间GCD , 右区间GCD );

    最大值——总最大值=max(左区间最大值,右区间最大值)

    不符合区间加法的例子:

    众数——只知道左右区间的众数,没法求总区间的众数

    01序列的最长连续零——只知道左右区间的最长连续零,没法知道总的最长连续零

     

    一个问题,只要能化成对一些连续点的修改和统计问题,基本就可以用线段树来解决了,具体怎么转化在第六节会讲。

    由于点的信息可以千变万化,所以线段树是一种非常灵活的数据结构,可以做的题的类型特别多,只要会转化。

    线段树当然是可以维护线段信息的,因为线段信息也是可以转换成用点来表达的(每个点代表一条线段)。

    所以在以下对结构的讨论中,都是对点的讨论,线段和点的对应关系在第七节扫描线中会讲。

     

    本文二到五节是讲对线段树操作的原理和实现。

    六到八节介绍了线段树解题模型,以及一些例题。

     

    初学者可以先看这篇文章: 线段树从零开始

     

    二:原理

    (注:由于线段树的每个节点代表一个区间,以下叙述中不区分节点和区间,只是根据语境需要,选择合适的词)

    线段树本质上是维护下标为1,2,..,n的n个按顺序排列的数的信息,所以,其实是“点树”,是维护n的点的信息,至于每个点的数据的含义可以有很多,

    在对线段操作的线段树中,每个点代表一条线段,在用线段树维护数列信息的时候,每个点代表一个数,但本质上都是每个点代表一个数。以下,在讨论线段树的时候,区间[L,R]指的是下标从L到R的这(R-L+1)个数,而不是指一条连续的线段。只是有时候这些数代表实际上一条线段的统计结果而已。

     

     

    线段树是将每个区间[L,R]分解成[L,M]和[M+1,R] (其中M=(L+R)/2 这里的除法是整数除法,即对结果下取整)直到 L==R 为止。 

    开始时是区间[1,n] ,通过递归来逐步分解,假设根的高度为1的话,树的最大高度为(n>1)。

    线段树对于每个n的分解是唯一的,所以n相同的线段树结构相同,这也是实现可持久化线段树的基础。

    下图展示了区间[1,13]的分解过程:

     

    上图中,每个区间都是一个节点,每个节点存自己对应的区间的统计信息。

     

    (1)线段树的点修改:

     

    假设要修改[5]的值,可以发现,每层只有一个节点包含[5],所以修改了[5]之后,只需要每层更新一个节点就可以线段树每个节点的信息都是正确的,所以修改次数的最大值为层数

    复杂度O(log2(n))


    (2)线段树的区间查询:

     

    线段树能快速进行区间查询的基础是下面的定理:

    定理:n>=3时,一个[1,n]的线段树可以将[1,n]的任意子区间[L,R]分解为不超过个子区间。

    这样,在查询[L,R]的统计值的时候,只需要访问不超过个节点,就可以获得[L,R]的统计信息,实现了O(log2(n))的区间查询。

     

    下面给出证明:

     

    (2.1)先给出一个粗略的证明(结合下图):

    先考虑树的最下层,将所有在区间[L,R]内的点选中,然后,若相邻的点的直接父节点是同一个,那么就用这个父节点代替这两个节点(父节点在上一层)。这样操作之后,本层最多剩下两个节点。若最左侧被选中的节点是它父节点的右子树,那么这个节点会被剩下。若最右侧被选中的节点是它的父节点的左子树,那么这个节点会被剩下。中间的所有节点都被父节点取代。

    对最下层处理完之后,考虑它的上一层,继续进行同样的处理,可以发现,每一层最多留下2个节点,其余的节点升往上一层,这样可以说明分割成的区间(节点)个数是大概是树高的两倍左右。

     

    下图为n=13的线段树,区间[2,12],按照上面的叙述进行操作的过程图:

    由图可以看出:在n=13的线段树中,[2,12]=[2] + [3,4] + [5,7] + [8,10] + [11,12] 。

     

     

    (2.2)然后给出正式一点的证明:

    定理:n>=3时,一个[1,n]的线段树可以将[1,n]的任意子区间[L,R]分解为不超过个子区间。

     

    用数学归纳法,证明上面的定理:

    首先,n=3,4,5时,用穷举法不难证明定理成立。

    假设对于n= 3,4,5,...,k-1上式都成立,下面来证明对于n=k ( k>=6 )成立:

    分为4种情况来证明:

     

    情况一:[L,R]包含根节点(L=1且R=n),此时,[L,R]被分解为了一个节点,定理成立。

     

    情况二:[L,R]包含根节点的左子节点,此时[L,R]一定不包含根的右子节点(因为如果包含,就可以合并左右子节点,

    用根节点替代,此时就是情况一)。这时,以右子节点为根的这课树的元素个数为

    [L,R]分成的子区间由两部分组成:

    一:根的左子结点,区间数为1 

    二:以根的右子节点为根的树中,进行区间查询,这个可以递归使用本定理。

    由归纳假设可得,[L,R]一共被分成了个区间。

    情况三:跟情况二对称,不一样的是,以根的左子节点为根的树的元素个数为

    [L,R]一共被分成了个区间。

    从公式可以看出,情况二的区间数小于等于情况三的区间数,于是只需要证明情况三的区间数符合条件就行了。

    于是,情况二和情况三定理成立。

     

    情况四:[L,R]不包括根节点以及根节点的左右子节点。

    于是,剩下的层,每层最多两个节点(参考粗略证明中的内容)。

    于是[L,R]最多被分解成了个区间,定理成立。

     

     

    上面只证明了是上界,但是,其实它是最小上界。

    n=3,4时,有很多组区间的分解可以达到最小上界。

    当n>4时,当且仅当n=2^t (t>=3),L=2,R=2^t -1 时,区间[L,R]的分解可以达到最小上界

    就不证明了,有兴趣可以自己去证明。

    下图是n=16 , L=2 , R=15 时的操作图,此图展示了达到最小上界的树的结构。

     

     

     

     

     

    (3)线段树的区间修改:

    线段树的区间修改也是将区间分成子区间,但是要加一个标记,称作懒惰标记。

    标记的含义:

    本节点的统计信息已经根据标记更新过了,但是本节点的子节点仍需要进行更新。

    即,如果要给一个区间的所有值都加上1,那么,实际上并没有给这个区间的所有值都加上1,而是打个标记,记下来,这个节点所包含的区间需要加1.打上标记后,要根据标记更新本节点的统计信息,比如,如果本节点维护的是区间和,而本节点包含5个数,那么,打上+1的标记之后,要给本节点维护的和+5。这是向下延迟修改,但是向上显示的信息是修改以后的信息,所以查询的时候可以得到正确的结果。有的标记之间会相互影响,所以比较简单的做法是,每递归到一个区间,首先下推标记(若本节点有标记,就下推标记),然后再打上新的标记,这样仍然每个区间操作的复杂度是O(log2(n))。

     

    标记有相对标记绝对标记之分:

    相对标记是将区间的所有数+a之类的操作,标记之间可以共存,跟打标记的顺序无关(跟顺序无关才是重点)。

    所以,可以在区间修改的时候不下推标记,留到查询的时候再下推。

          注意:如果区间修改时不下推标记,那么PushUp函数中,必须考虑本节点的标记。

                     而如果所有操作都下推标记,那么PushUp函数可以不考虑本节点的标记,因为本节点的标记一定已经被下推了(也就是对本节点无效了)

    绝对标记是将区间的所有数变成a之类的操作,打标记的顺序直接影响结果,

    所以这种标记在区间修改的时候必须下推旧标记,不然会出错。

     

    注意,有多个标记的时候,标记下推的顺序也很重要,错误的下推顺序可能会导致错误。

     

    之所以要区分两种标记,是因为非递归线段树只能维护相对标记。

    因为非递归线段树是自底向上直接修改分成的每个子区间,所以根本做不到在区间修改的时候下推标记。

    非递归线段树一般不下推标记,而是自下而上求答案的过程中,根据标记更新答案。

     

    (4)线段树的存储结构:

    线段树是用数组来模拟树形结构,对于每一个节点R ,左子节点为 2*R (一般写作R<<1)右子节点为 2*R+1(一般写作R<<1|1)

    然后以1为根节点,所以,整体的统计信息是存在节点1中的。

    这么表示的原因看下图就很明白了,左子树的节点标号都是根节点的两倍,右子树的节点标号都是左子树+1:

    线段树需要的数组元素个数是:,一般都开4倍空间,比如: int A[n<<2];

     

     

    三:递归实现

    以下以维护数列区间和的线段树为例,演示最基本的线段树代码。

    (0)定义:

    [cpp] view plain copy

    1. #define maxn 100007  //元素总个数  
    2. #define ls l,m,rt<<1  
    3. #define rs m+1,r,rt<<1|1  
    4. int Sum[maxn<<2],Add[maxn<<2];//Sum求和,Add为懒惰标记   
    5. int A[maxn],n;//存原数组数据下标[1,n]   

    [cpp] view plain copy

    1. #define maxn 100007  //元素总个数  
    2. #define ls l,m,rt<<1  
    3. #define rs m+1,r,rt<<1|1  
    4. int Sum[maxn<<2],Add[maxn<<2];//Sum求和,Add为懒惰标记   
    5. int A[maxn],n;//存原数组数据下标[1,n]   

     

    (1)建树:

    [cpp] view plain copy

    1. //PushUp函数更新节点信息 ,这里是求和  
    2. void PushUp(int rt){Sum[rt]=Sum[rt<<1]+Sum[rt<<1|1];}  
    3. //Build函数建树   
    4. void Build(int l,int r,int rt){ //l,r表示当前节点区间,rt表示当前节点编号  
    5.     if(l==r) {//若到达叶节点   
    6.         Sum[rt]=A[l];//储存数组值   
    7.         return;  
    8.     }  
    9.     int m=(l+r)>>1;  
    10.     //左右递归   
    11.     Build(l,m,rt<<1);  
    12.     Build(m+1,r,rt<<1|1);  
    13.     //更新信息   
    14.     PushUp(rt);  
    15. }  

    [cpp] view plain copy

    1. //PushUp函数更新节点信息 ,这里是求和  
    2. void PushUp(int rt){Sum[rt]=Sum[rt<<1]+Sum[rt<<1|1];}  
    3. //Build函数建树   
    4. void Build(int l,int r,int rt){ //l,r表示当前节点区间,rt表示当前节点编号  
    5.     if(l==r) {//若到达叶节点   
    6.         Sum[rt]=A[l];//储存数组值   
    7.         return;  
    8.     }  
    9.     int m=(l+r)>>1;  
    10.     //左右递归   
    11.     Build(l,m,rt<<1);  
    12.     Build(m+1,r,rt<<1|1);  
    13.     //更新信息   
    14.     PushUp(rt);  
    15. }  

     

    (2)点修改:

    假设A[L]+=C:

    [cpp] view plain copy

    1. void Update(int L,int C,int l,int r,int rt){//l,r表示当前节点区间,rt表示当前节点编号  
    2.     if(l==r){//到叶节点,修改   
    3.         Sum[rt]+=C;  
    4.         return;  
    5.     }  
    6.     int m=(l+r)>>1;  
    7.     //根据条件判断往左子树调用还是往右   
    8.     if(L <= m) Update(L,C,l,m,rt<<1);  
    9.     else       Update(L,C,m+1,r,rt<<1|1);  
    10.     PushUp(rt);//子节点更新了,所以本节点也需要更新信息   
    11. }   

    [cpp] view plain copy

    1. void Update(int L,int C,int l,int r,int rt){//l,r表示当前节点区间,rt表示当前节点编号  
    2.     if(l==r){//到叶节点,修改   
    3.         Sum[rt]+=C;  
    4.         return;  
    5.     }  
    6.     int m=(l+r)>>1;  
    7.     //根据条件判断往左子树调用还是往右   
    8.     if(L <= m) Update(L,C,l,m,rt<<1);  
    9.     else       Update(L,C,m+1,r,rt<<1|1);  
    10.     PushUp(rt);//子节点更新了,所以本节点也需要更新信息   
    11. }   

     

    (3)区间修改:

     

    假设A[L,R]+=C

    [cpp] view plain copy

    1. void Update(int L,int R,int C,int l,int r,int rt){//L,R表示操作区间,l,r表示当前节点区间,rt表示当前节点编号   
    2.     if(L <= l && r <= R){//如果本区间完全在操作区间[L,R]以内   
    3.         Sum[rt]+=C*(r-l+1);//更新数字和,向上保持正确  
    4.         Add[rt]+=C;//增加Add标记,表示本区间的Sum正确,子区间的Sum仍需要根据Add的值来调整  
    5.         return ;   
    6.     }  
    7.     int m=(l+r)>>1;  
    8.     PushDown(rt,m-l+1,r-m);//下推标记  
    9.     //这里判断左右子树跟[L,R]有无交集,有交集才递归   
    10.     if(L <= m) Update(L,R,C,l,m,rt<<1);  
    11.     if(R >  m) Update(L,R,C,m+1,r,rt<<1|1);   
    12.     PushUp(rt);//更新本节点信息   
    13. }   

    [cpp] view plain copy

    1. void Update(int L,int R,int C,int l,int r,int rt){//L,R表示操作区间,l,r表示当前节点区间,rt表示当前节点编号   
    2.     if(L <= l && r <= R){//如果本区间完全在操作区间[L,R]以内   
    3.         Sum[rt]+=C*(r-l+1);//更新数字和,向上保持正确  
    4.         Add[rt]+=C;//增加Add标记,表示本区间的Sum正确,子区间的Sum仍需要根据Add的值来调整  
    5.         return ;   
    6.     }  
    7.     int m=(l+r)>>1;  
    8.     PushDown(rt,m-l+1,r-m);//下推标记  
    9.     //这里判断左右子树跟[L,R]有无交集,有交集才递归   
    10.     if(L <= m) Update(L,R,C,l,m,rt<<1);  
    11.     if(R >  m) Update(L,R,C,m+1,r,rt<<1|1);   
    12.     PushUp(rt);//更新本节点信息   
    13. }   

     

    (4)区间查询:

    询问A[L,R]的和

    首先是下推标记的函数:

    [cpp] view plain copy

    1. void PushDown(int rt,int ln,int rn){  
    2.     //ln,rn为左子树,右子树的数字数量。   
    3.     if(Add[rt]){  
    4.         //下推标记   
    5.         Add[rt<<1]+=Add[rt];  
    6.         Add[rt<<1|1]+=Add[rt];  
    7.         //修改子节点的Sum使之与对应的Add相对应   
    8.         Sum[rt<<1]+=Add[rt]*ln;  
    9.         Sum[rt<<1|1]+=Add[rt]*rn;  
    10.         //清除本节点标记   
    11.         Add[rt]=0;  
    12.     }  
    13. }  

    [cpp] view plain copy

    1. void PushDown(int rt,int ln,int rn){  
    2.     //ln,rn为左子树,右子树的数字数量。   
    3.     if(Add[rt]){  
    4.         //下推标记   
    5.         Add[rt<<1]+=Add[rt];  
    6.         Add[rt<<1|1]+=Add[rt];  
    7.         //修改子节点的Sum使之与对应的Add相对应   
    8.         Sum[rt<<1]+=Add[rt]*ln;  
    9.         Sum[rt<<1|1]+=Add[rt]*rn;  
    10.         //清除本节点标记   
    11.         Add[rt]=0;  
    12.     }  
    13. }  


    然后是区间查询的函数:

    [cpp] view plain copy

    1. int Query(int L,int R,int l,int r,int rt){//L,R表示操作区间,l,r表示当前节点区间,rt表示当前节点编号  
    2.     if(L <= l && r <= R){  
    3.         //在区间内,直接返回   
    4.         return Sum[rt];  
    5.     }  
    6.     int m=(l+r)>>1;  
    7.     //下推标记,否则Sum可能不正确  
    8.     PushDown(rt,m-l+1,r-m);   
    9.       
    10.     //累计答案  
    11.     int ANS=0;  
    12.     if(L <= m) ANS+=Query(L,R,l,m,rt<<1);  
    13.     if(R >  m) ANS+=Query(L,R,m+1,r,rt<<1|1);  
    14.     return ANS;  
    15. }   

    [cpp] view plain copy

    1. int Query(int L,int R,int l,int r,int rt){//L,R表示操作区间,l,r表示当前节点区间,rt表示当前节点编号  
    2.     if(L <= l && r <= R){  
    3.         //在区间内,直接返回   
    4.         return Sum[rt];  
    5.     }  
    6.     int m=(l+r)>>1;  
    7.     //下推标记,否则Sum可能不正确  
    8.     PushDown(rt,m-l+1,r-m);   
    9.       
    10.     //累计答案  
    11.     int ANS=0;  
    12.     if(L <= m) ANS+=Query(L,R,l,m,rt<<1);  
    13.     if(R >  m) ANS+=Query(L,R,m+1,r,rt<<1|1);  
    14.     return ANS;  
    15. }   

     

    (5)函数调用:

     

    [cpp] view plain copy

    1. //建树   
    2. Build(1,n,1);   
    3. //点修改  
    4. Update(L,C,1,n,1);  
    5. //区间修改   
    6. Update(L,R,C,1,n,1);  
    7. //区间查询   
    8. int ANS=Query(L,R,1,n,1);  

    [cpp] view plain copy

    1. //建树   
    2. Build(1,n,1);   
    3. //点修改  
    4. Update(L,C,1,n,1);  
    5. //区间修改   
    6. Update(L,R,C,1,n,1);  
    7. //区间查询   
    8. int ANS=Query(L,R,1,n,1);  

     

    感谢几位网友指出了我的错误。

    我说相对标记在Update时可以不下推,这一点是对的,但是原来的代码是错误的。

    因为原来的代码中,PushUP函数是没有考虑本节点的Add值的,如果Update时下推标记,那么PushUp的时候,节点的Add值一定为零,所以不需要考虑Add。

    但是,如果Update时暂时不下推标记的话,那么PushUp函数就必须考虑本节点的Add值,否则会导致错误。

    为了简便,上面函数中,PushUp函数没有考虑Add标记。所以无论是相对标记还是绝对标记,在更新信息的时候,

    到达的每个节点都必须调用PushDown函数来下推标记,另外,代码中,点修改函数中没有PushDown函数,因为这里假设只有点修改一种操作,

    如果题目中是点修改和区间修改混合的话,那么点修改中也需要PushDown。


     

    四:非递归原理

    非递归的思路很巧妙,思路以及部分代码实现 来自  清华大学 张昆玮 《统计的力量》 ,有兴趣可以去找来看。

    非递归的实现,代码简单(尤其是点修改和区间查询),速度快,建树简单,遍历元素简单。总之能非递归就非递归吧。

    不过,要支持区间修改的话,代码会变得复杂,所以区间修改的时候还是要取舍。有个特例,如果区间修改,但是只需要

    在所有操作结束之后,一次性下推所有标记,然后求结果,这样的话,非递归写起来也是很方便的。

    下面先讲思路,再讲实现。

     

    点修改:

    非递归的思想总的来说就是自底向上进行各种操作。回忆递归线段树的点修改,首先由根节点1向下递归,找到对应的叶

    节点,然后,修改叶节点的值,再向上返回,在函数返回的过程中,更新路径上的节点的统计信息。而非递归线段树的思路是,

    如果可以直接找到叶节点,那么就可以直接从叶节点向上更新,而一个节点找父节点是很容易的,编号除以2再下取整就行了。

    那么,如何可以直接找到叶节点呢?非递归线段树将普通线段树(假设元素数量为n)扩充成一颗满二叉树。

    来观察一下满二叉树的性质:

     

    可以注意到红色和黑色数字的差是固定的,如果事先算出这个差值,就可以直接找到叶节点。

     

    注意:区分3个概念:原数组下标,线段树中的下标和存储下标。

    原数组下标,是指,需要维护统计信息(比如区间求和)的数组的下标,这里都默认下标从1开始(一般用A数组表示)

    线段树下标,是指,加入线段树中某个位置的下标,比如,原数组中的第一个数,一般会加入到线段树中的第二个位置,

    为什么要这么做,后面会讲。

    存储下标,是指该元素所在的叶节点的编号,即实际存储的位置。

     

    【在上面的图片中,红色为原数组下标,黑色为存储下标】

     

    有了这3个概念,下面开始讲区间查询。

     

    点修改下的区间查询:

    首先,区间的划分没有变,现在关键是如何直接找到被分成的区间。原来是递归查找,判断左右子区间跟[L,R]是否有交点,

    若有交点则向下递归。现在要非递归实现,这就是巧妙之处,见下图,以查询[3,11]为例子。

     

     

     

    其实,容易发现,紫色部分的变化,跟原来分析线段树的区间分解的时候是一样的规则,图中多的蓝色是什么意思呢?

    首先注意到,蓝色节点刚好在紫色节点的两端。

    回忆一下,原来线段树在区间逐层被替代的过程中,哪些节点被留了下来?最左侧的节点,若为其父节点的右子节点,则留下。

    最右侧的节点,若为其父节点的左子节点则留下。那么对于包裹着紫色的蓝色节点来看,刚好相反。

    比如,以左侧的的蓝色为例,若该节点是其父节点的右子节点,就证明它右侧的那个紫色节点不会留下,会被其父替代,所以没必要在这一步计算,若该节点是其父节点的左子节点,就证明它右侧的那个紫色节点会留在这一层,所以必须在此刻计算,否则以后都不会再计算这个节点了。这样逐层上去,容易发现,对于左侧的蓝色节点来说,只要它是左子节点,那么就要计算对应的右子节点。同理,对于右侧的蓝色节点,只要它是右子节点,就需要计算它对应的左子节点。这个计算一直持续到左右蓝色节点的父亲为同一个的时候,才停止。于是,区间查询,其实就是两个蓝色节点一路向上走,在路径上更新答案。这样,区间修改就变成了两条同时向根走的链,明显复杂度O(log2(n))。并且可以非递归实现。

    至此,区间查询也解决了,可以直接找到所有分解成的区间。

    但是有一个问题,如果要查询[1,5]怎么办?[1]左边可是没地方可以放置蓝色节点了。

    问题的解决办法简单粗暴,原数组的1到n就不存在线段树的1到n了,而是存在线段树的2到n+1,

    而开始要建立一颗有n+2个元素的树,空出第一个和最后一个元素的空间。

     

    现在来讲如何扩充成一颗满二叉树。

    再来看这课满二叉树,令N=8;注意到,该树可以存8个元素,并且[1..7]是非叶节点,[8..15]是叶节点。

    也就是说,左下角为N的满二叉树,可以存N个元素,并且[1..N-1]是非叶节点,[N..2N-1]是叶节点。

    并且,线段树下标+N-1=存储下标 (还记不记得原来对三个下标的定义)

     

    这时,这个线段树存在两段坐标映射:

    原数组下标+1=线段树下标

    线段树下标+N-1=存储下标 

    联立方程得到:原数组下标+N=存储下标

    于是从原数组下标到存储下标的转换及其简单。

     

    下一个问题:N怎么确定?

    上面提到了,N的含义之一是,这棵树可以存N个元素,也就是说N必须大于等于n+2

    于是,N的定义,N是大于等于n+2的,某个2的次方。

     

    区间修改下的区间查询:

    方法之一:如果题目许可,可以直接打上标记,最后一次下推所有标记,然后就可以遍历叶节点来获取信息。

    方法之二:如果题目查询跟修改混在一起,那么,采用标记永久化思想。也就是,不下推标记。

    递归线段树是在查询区间的时候下推标记,使得到达每个子区间的时候,Sum已经是正确值。

    非递归没法这么做,非递归是从下往上,遇到标记就更新答案。

    这题是Add标记,一个区间Add标记表示这个区间所有元素都需要增加Add

    Add含义不变,Add仍然表示本节点的Sum已经更新完毕,但是子节点的Sum仍需要更新.

    现在就是如何在查询的时候根据标记更新答案。

    观察下图:

    左边的蓝色节点从下往上走,在蓝色节点到达[1,4]时,注意到,左边蓝色节点之前计算过的所有节点(即[3,4])都是目前蓝色节点的子节点也就是说,当前蓝色节点的Add是要影响这个节点已经计算过的所有数。多用一个变量来记录这个蓝色节点已经计算过多少个数,根据个数以及当前蓝色节点的Add,来更新最终答案。

    更新完答案之后,再加上[5,8]的答案,同时当前蓝色节点计算过的个数要+4(因为[5,8]里有4个数)

    然后当这个节点到达[1,8]节点时,可以更新[1,8]的Add.

    这里,本来左右蓝色节点相遇之后就不再需要计算了,但是由于有了Add标记,左右蓝色节点的公共祖先上的Add标记会影响目前的所有数,所以还需要一路向上查询到根,沿路根据Add更新答案。

     

    区间修改:

    这里讲完了查询,再来讲讲修改

    修改的时候,给某个区间的Add加上了C,这个区间的子区间向上查询时,会经过这个节点,也就是会计算这个Add,但是

    如果路径经过这个区间的父节点,就不会计算这个节点的Add,也就会出错。这里其实跟递归线段树一样,改了某个区间的Add

    仍需要向上更新所有包含这个区间的Sum,来保持上面所有节点的正确性。

     

    五:非递归实现

    以下以维护数列区间和的线段树为例,演示最基本的非递归线段树代码。

    (0)定义

    [cpp] view plain copy

    1. //   
    2. #define maxn 100007  
    3. int A[maxn],n,N;//原数组,n为原数组元素个数 ,N为扩充元素个数   
    4. int Sum[maxn<<2];//区间和   
    5. int Add[maxn<<2];//懒惰标记   

    [cpp] view plain copy

    1. //   
    2. #define maxn 100007  
    3. int A[maxn],n,N;//原数组,n为原数组元素个数 ,N为扩充元素个数   
    4. int Sum[maxn<<2];//区间和   
    5. int Add[maxn<<2];//懒惰标记   

     

    (1)建树:

    [cpp] view plain copy

    1. //  
    2. void Build(int n){  
    3.     //计算N的值   
    4.     N=1;while(N < n+2) N <<= 1;  
    5.     //更新叶节点   
    6.     for(int i=1;i<=n;++i) Sum[N+i]=A[i];//原数组下标+N=存储下标  
    7.     //更新非叶节点   
    8.     for(int i=N-1;i>0;--i){  
    9.         //更新所有非叶节点的统计信息   
    10.         Sum[i]=Sum[i<<1]+Sum[i<<1|1];  
    11.         //清空所有非叶节点的Add标记   
    12.         Add[i]=0;  
    13.     }  
    14. }   

    [cpp] view plain copy

    1. //  
    2. void Build(int n){  
    3.     //计算N的值   
    4.     N=1;while(N < n+2) N <<= 1;  
    5.     //更新叶节点   
    6.     for(int i=1;i<=n;++i) Sum[N+i]=A[i];//原数组下标+N=存储下标  
    7.     //更新非叶节点   
    8.     for(int i=N-1;i>0;--i){  
    9.         //更新所有非叶节点的统计信息   
    10.         Sum[i]=Sum[i<<1]+Sum[i<<1|1];  
    11.         //清空所有非叶节点的Add标记   
    12.         Add[i]=0;  
    13.     }  
    14. }   

     

    (2)点修改:

    A[L]+=C

    [cpp] view plain copy

    1. //  
    2. void Update(int L,int C){  
    3.     for(int s=N+L;s;s>>=1){  
    4.         Sum[s]+=C;  
    5.     }  
    6. }   

    [cpp] view plain copy

    1. //  
    2. void Update(int L,int C){  
    3.     for(int s=N+L;s;s>>=1){  
    4.         Sum[s]+=C;  
    5.     }  
    6. }   

     

    (3)点修改下的区间查询:

    求A[L..R]的和(点修改没有使用Add所以不需要考虑)

    代码非常简洁,也不难理解,

    s和t分别代表之前的论述中的左右蓝色节点,其余的代码根据之前的论述应该很容易看懂了。

    s^t^1 在s和t的父亲相同时值为0,终止循环。

    两个if是判断s和t分别是左子节点还是右子节点,根据需要来计算Sum

    [cpp] view plain copy

    1. //  
    2. int Query(int L,int R){  
    3.     int ANS=0;  
    4.     for(int s=N+L-1,t=N+R+1;s^t^1;s>>=1,t>>=1){  
    5.         if(~s&1) ANS+=Sum[s^1];  
    6.         if( t&1) ANS+=Sum[t^1];  
    7.     }  
    8.     return ANS;  
    9. }   

    [cpp] view plain copy

    1. //  
    2. int Query(int L,int R){  
    3.     int ANS=0;  
    4.     for(int s=N+L-1,t=N+R+1;s^t^1;s>>=1,t>>=1){  
    5.         if(~s&1) ANS+=Sum[s^1];  
    6.         if( t&1) ANS+=Sum[t^1];  
    7.     }  
    8.     return ANS;  
    9. }   

     

    (4)区间修改:

    A[L..R]+=C

    [cpp] view plain copy

    1. <span style="font-size:14px;">//  
    2. void Update(int L,int R,int C){  
    3.     int s,t,Ln=0,Rn=0,x=1;  
    4.     //Ln:  s一路走来已经包含了几个数  
    5.     //Rn:  t一路走来已经包含了几个数  
    6.     //x:   本层每个节点包含几个数  
    7.     for(s=N+L-1,t=N+R+1;s^t^1;s>>=1,t>>=1,x<<=1){  
    8.         //更新Sum  
    9.         Sum[s]+=C*Ln;  
    10.         Sum[t]+=C*Rn;  
    11.         //处理Add  
    12.         if(~s&1) Add[s^1]+=C,Sum[s^1]+=C*x,Ln+=x;  
    13.         if( t&1) Add[t^1]+=C,Sum[t^1]+=C*x,Rn+=x;  
    14.     }  
    15.     //更新上层Sum  
    16.     for(;s;s>>=1,t>>=1){  
    17.         Sum[s]+=C*Ln;  
    18.         Sum[t]+=C*Rn;  
    19.     }   
    20. } </span>  

    [cpp] view plain copy

    1. <span style="font-size:14px;">//  
    2. void Update(int L,int R,int C){  
    3.     int s,t,Ln=0,Rn=0,x=1;  
    4.     //Ln:  s一路走来已经包含了几个数  
    5.     //Rn:  t一路走来已经包含了几个数  
    6.     //x:   本层每个节点包含几个数  
    7.     for(s=N+L-1,t=N+R+1;s^t^1;s>>=1,t>>=1,x<<=1){  
    8.         //更新Sum  
    9.         Sum[s]+=C*Ln;  
    10.         Sum[t]+=C*Rn;  
    11.         //处理Add  
    12.         if(~s&1) Add[s^1]+=C,Sum[s^1]+=C*x,Ln+=x;  
    13.         if( t&1) Add[t^1]+=C,Sum[t^1]+=C*x,Rn+=x;  
    14.     }  
    15.     //更新上层Sum  
    16.     for(;s;s>>=1,t>>=1){  
    17.         Sum[s]+=C*Ln;  
    18.         Sum[t]+=C*Rn;  
    19.     }   
    20. } </span>  

     

    (5)区间修改下的区间查询:

    求A[L..R]的和

    [cpp] view plain copy

    1. //  
    2. int Query(int L,int R){  
    3.     int s,t,Ln=0,Rn=0,x=1;  
    4.     int ANS=0;  
    5.     for(s=N+L-1,t=N+R+1;s^t^1;s>>=1,t>>=1,x<<=1){  
    6.         //根据标记更新   
    7.         if(Add[s]) ANS+=Add[s]*Ln;  
    8.         if(Add[t]) ANS+=Add[t]*Rn;  
    9.         //常规求和   
    10.         if(~s&1) ANS+=Sum[s^1],Ln+=x;  
    11.         if( t&1) ANS+=Sum[t^1],Rn+=x;   
    12.     }  
    13.     //处理上层标记  
    14.     for(;s;s>>=1,t>>=1){  
    15.         ANS+=Add[s]*Ln;  
    16.         ANS+=Add[t]*Rn;  
    17.     }  
    18.     return ANS;  
    19. }  

    [cpp] view plain copy

    1. //  
    2. int Query(int L,int R){  
    3.     int s,t,Ln=0,Rn=0,x=1;  
    4.     int ANS=0;  
    5.     for(s=N+L-1,t=N+R+1;s^t^1;s>>=1,t>>=1,x<<=1){  
    6.         //根据标记更新   
    7.         if(Add[s]) ANS+=Add[s]*Ln;  
    8.         if(Add[t]) ANS+=Add[t]*Rn;  
    9.         //常规求和   
    10.         if(~s&1) ANS+=Sum[s^1],Ln+=x;  
    11.         if( t&1) ANS+=Sum[t^1],Rn+=x;   
    12.     }  
    13.     //处理上层标记  
    14.     for(;s;s>>=1,t>>=1){  
    15.         ANS+=Add[s]*Ln;  
    16.         ANS+=Add[t]*Rn;  
    17.     }  
    18.     return ANS;  
    19. }  

    六:线段树解题模型

    给出线段树解题模型以及一些例题。

    先对图中各个名字给出定义:

    问题:可能可以用线段树解决的问题

    目标信息:由问题转换而成的,为了解决问题而需要统计的信息(可能不满足区间加法)。

    点信息:每个点储存的信息

    区间信息:每个区间维护的信息(线段树节点定义) (必须满足区间加法)

    区间信息包括 统计信息标记

    --------统计信息:统计节点代表的区间的信息,一般自下而上更新

    --------标记:对操作进行标记(在区间修改时需要),一般自上而下传递,或者不传递

    区间加法:实现区间加法的代码

    查询:实现查询操作的代码

    修改:实现修改操作的代码

     

    图中紫线右边是实际线段树的实现,左边是对问题的分析以及转换。

     

    一个问题,若能转换成对一些连续点的修改或者统计,就可以考虑用线段树解决。

    首先确定目标信息点信息,然后将目标信息转换成区间信息(必要时,增加信息,使之符合区间加法)。

    之后就是线段树的代码实现了,包括:

    1.区间加法 

    2.建树,点信息到区间信息的转换 

    3.每种操作(包括查询,修改)对区间信息的调用,修改

     

    这样,点的信息不同,区间信息不同,线段树可以维护很多种类的信息,所以是一种非常实用的数据结构。

    可以解决很多问题,下面给出几个例子来说明。

     

    (1):字符串哈希

    题目:URAL1989 Subpalindromes    题解

    给定一个字符串(长度<=100000),有两个操作。   1:改变某个字符。 2:判断某个子串是否构成回文串。 

    直接判断会超时。这个题目,是用线段树维护字符串哈希

    对于一个字符串a[0],a[1],...,a[n-1] 它对应的哈希函数为a[0]+a[1]*K + a[2]*K^2 +...+a[n-1]*K^(n-1)

    再维护一个从右往左的哈希值:a[0]*K^(n-1) + a[1]*K^(n-2) +...+a[n-1]

    若是回文串,则左右的哈希值会相等。而左右哈希值相等,则很大可能这是回文串。

    若出现误判,可以再用一个K2,进行二次哈希判断,可以减小误判概率。

    实现上,哈希值最好对某个质数取余数,这样分布更均匀。

     

     

    解题模型:

    问题经过转换之后:

    目标信息:某个区间的左,右哈希值

    点信息:一个字符

    目标信息已经符合区间加法,所以区间信息=目标信息

    所以线段树的结构为:

    区间信息:区间哈希值

    点信息:一个字符

    代码主要需要注意2个部分:

    1.区间加法 :(PushUp函数,Pow[a]=K^a)

    2.点信息->区间信息:(叶节点上,区间只包含一个点,所以需要将点信息转换成区间信息)

    修改以及查询,在有了区间加法的情况下,没什么难度了。

     

    可以看出,上述解题过程的核心,就是找到区间信息, 写好区间加法

    下面是维护区间和的部分,下面的代码没有取余,也就是实际上是对2^32取余数,这样其实分布不均匀,容易出现误判:

    [cpp] view plain copy

    1. //   
    2. #define K 137  
    3. #define maxn 100001   
    4. char str[maxn];  
    5. int Pow[maxn];//K的各个次方   
    6. struct Node{  
    7.     int KeyL,KeyR;  
    8.     Node():KeyL(0),KeyR(0){}  
    9.     void init(){KeyL=KeyR=0;}  
    10. }node[maxn<<2];  
    11. void PushUp(int L,int R,int rt){  
    12.     node[rt].KeyL=node[rt<<1].KeyL+node[rt<<1|1].KeyL*Pow[L];  
    13.     node[rt].KeyR=node[rt<<1].KeyR*Pow[R]+node[rt<<1|1].KeyR;  
    14. }  

    [cpp] view plain copy

    1. //   
    2. #define K 137  
    3. #define maxn 100001   
    4. char str[maxn];  
    5. int Pow[maxn];//K的各个次方   
    6. struct Node{  
    7.     int KeyL,KeyR;  
    8.     Node():KeyL(0),KeyR(0){}  
    9.     void init(){KeyL=KeyR=0;}  
    10. }node[maxn<<2];  
    11. void PushUp(int L,int R,int rt){  
    12.     node[rt].KeyL=node[rt<<1].KeyL+node[rt<<1|1].KeyL*Pow[L];  
    13.     node[rt].KeyR=node[rt<<1].KeyR*Pow[R]+node[rt<<1|1].KeyR;  
    14. }  

     

    (2):最长连续零

    题目:Codeforces 527C Glass Carving   题解

    题意是给定一个矩形,不停地纵向或横向切割,问每次切割后,最大的矩形面积是多少。

    最大矩形面积=最长的长*最宽的宽

    这题,长宽都是10^5,所以,用01序列表示每个点是否被切割,然后,

    最长的长就是长的最长连续0的数量+1

    最长的宽就是宽的最长连续0的数量+1

    于是用线段树维护最长连续零

     

    问题转换成:

    目标信息:区间最长连续零的个数

    点信息:0 或 1

    由于目标信息不符合区间加法,所以要扩充目标信息。

     

    转换后的线段树结构

    区间信息:从左,右开始的最长连续零,本区间是否全零,本区间最长连续零。

    点信息:0 或 1

    然后还是那2个问题:

     

    1.区间加法:

    这里,一个区间的最长连续零,需要考虑3部分:

    -(1):左子区间最长连续零

    -(2):右子区间最长连续零

    -(3):左右子区间拼起来,而在中间生成的连续零(可能长于两个子区间的最长连续零)

    而中间拼起来的部分长度,其实是左区间从右开始的最长连续零+右区间从左开始的最长连续零。

    所以每个节点需要多两个量,来存从左右开始的最长连续零。

    然而,左开始的最长连续零分两种情况,

    --(1):左区间不是全零,那么等于左区间的左最长连续零

    --(2):左区间全零,那么等于左区间0的个数加上右区间的左最长连续零

    于是,需要知道左区间是否全零,于是再多加一个变量。

    最终,通过维护4个值,达到了维护区间最长连续零的效果。

     

    2.点信息->区间信息 : 

    如果是0,那么  最长连续零=左最长连续零=右最长连续零=1 ,全零=true。

    如果是1,那么  最长连续零=左最长连续零=右最长连续零=0, 全零=false。

     

    至于修改和查询,有了区间加法之后,机械地写一下就好了。

    由于这里其实只有对整个区间的查询,所以查询函数是不用写的,直接找根的统计信息就行了。

     

    代码如下:

    [cpp] view plain copy

    1. //  
    2. #define maxn 200001  
    3. using namespace std;  
    4. int L[maxn<<2][2];//从左开始连续零个数   
    5. int R[maxn<<2][2];//从右   
    6. int Max[maxn<<2][2];//区间最大连续零   
    7. bool Pure[maxn<<2][2];//是否全零   
    8. int M[2];  
    9. void PushUp(int rt,int k){//更新rt节点的四个数据  k来选择两棵线段树  
    10.     Pure[rt][k]=Pure[rt<<1][k]&&Pure[rt<<1|1][k];   
    11.     Max[rt][k]=max(R[rt<<1][k]+L[rt<<1|1][k],max(Max[rt<<1][k],Max[rt<<1|1][k]));  
    12.     L[rt][k]=Pure[rt<<1][k]?L[rt<<1][k]+L[rt<<1|1][k]:L[rt<<1][k];  
    13.     R[rt][k]=Pure[rt<<1|1][k]?R[rt<<1|1][k]+R[rt<<1][k]:R[rt<<1|1][k];  
    14. }  

    [cpp] view plain copy

    1. //  
    2. #define maxn 200001  
    3. using namespace std;  
    4. int L[maxn<<2][2];//从左开始连续零个数   
    5. int R[maxn<<2][2];//从右   
    6. int Max[maxn<<2][2];//区间最大连续零   
    7. bool Pure[maxn<<2][2];//是否全零   
    8. int M[2];  
    9. void PushUp(int rt,int k){//更新rt节点的四个数据  k来选择两棵线段树  
    10.     Pure[rt][k]=Pure[rt<<1][k]&&Pure[rt<<1|1][k];   
    11.     Max[rt][k]=max(R[rt<<1][k]+L[rt<<1|1][k],max(Max[rt<<1][k],Max[rt<<1|1][k]));  
    12.     L[rt][k]=Pure[rt<<1][k]?L[rt<<1][k]+L[rt<<1|1][k]:L[rt<<1][k];  
    13.     R[rt][k]=Pure[rt<<1|1][k]?R[rt<<1|1][k]+R[rt<<1][k]:R[rt<<1|1][k];  
    14. }  

     

    (3):计数排序

    题目:Codeforces 558E A Simple Task  题解

    给定一个长度不超过10^5的字符串(小写英文字母),和不超过5000个操作。

    每个操作 L R K 表示给区间[L,R]的字符串排序,K=1为升序,K=0为降序。

    最后输出最终的字符串。

     

    题目转换成:

    目标信息:区间的计数排序结果

    点信息:一个字符

    这里,目标信息是符合区间加法的,但是为了支持区间操作,还是需要扩充信息。

     

    转换后的线段树结构

    区间信息:区间的计数排序结果,排序标记,排序种类(升,降)

    点信息:一个字符

     

    代码中需要解决的四个问题(难点在于标记下推和区间修改):

    1.区间加法

    对应的字符数量相加即可(注意标记是不上传的,所以区间加法不考虑标记)。

    2.点信息->区间信息:把对应字符的数量设置成1,其余为0,排序标记为false。

    3.标记下推

    明显,排序标记是绝对标记,也就是说,标记对子节点是覆盖式的效果,一旦被打上标记,下层节点的一切信息都无效。

    下推标记时,根据自己的排序结果,将元素分成对应的部分,分别装入两个子树。

    4.区间修改

    这个是难点,由于要对某个区间进行排序,首先对各个子区间求和(求和之前一定要下推标记,才能保证求的和是正确的)

    由于使用的计数排序,所以求和之后,新顺序也就出来了。然后按照排序的顺序按照每个子区间的大小来分配字符。

    操作后,每个子区间都被打上了标记。

     

    最后,在所有操作结束之后,一次下推所有标记,就可以得到最终的字符序列。

     

    这里只给出节点定义。

    [cpp] view plain copy

    1. //   
    2. struct Node{  
    3.     int d[26];//计数排序   
    4.     int D;//总数  
    5.     bool sorted;//是否排好序   
    6.     bool Inc;//是否升序  
    7. };  

    [cpp] view plain copy

    1. //   
    2. struct Node{  
    3.     int d[26];//计数排序   
    4.     int D;//总数  
    5.     bool sorted;//是否排好序   
    6.     bool Inc;//是否升序  
    7. };  

     

    (4)总结:

    总结一下,线段树解题步骤。

     

    :将问题转换成点信息目标信息

    即,将问题转换成对一些点的信息的统计问题。

     

    :将目标信息根据需要扩充成区间信息

    1.增加信息符合区间加法。

    2.增加标记支持区间操作。

     

    :代码中的主要模块:

    1.区间加法 

    2.标记下推 

    3.点信息->区间信息 

    4.操作(各种操作,包括修改和查询)

     

     

    完成第一步之后,题目有了可以用线段树解决的可能。

    完成第二步之后,题目可以由线段树解决。

    第三步就是慢慢写代码了。

    七:扫描线

    线段树的一大应用是扫描线。

     

    先把相关题目给出,有兴趣可以去找来练习:

     

    POJ 1177 Picture:给定若干矩形求合并之后的图形周长    题解

    HDU 1255 覆盖的面积:给定平面上若干矩形,求出被这些矩形覆盖过至少两次的区域的面积.   题解

    HDU 3642 Get The Treasury:给定若干空间立方体,求重叠了3次或以上的体积(这个是扫描面,每个面再扫描线)题解

    再补充一道稍微需要一点模型转换的扫描线题:

    POJ 2482 Stars in your window : 给定一些星星的位置和亮度,求用W*H的矩形能够框住的星星亮度之和最大为多少。

    这题是把星星转换成了矩形,把矩形框转换成了点,然后再扫描线。  题解

     

     

    扫描线求重叠矩形面积:

    考虑下图中的四个矩形:

     

     

    观察第三个图:

    扫描线的思路:使用一条垂直于X轴的直线,从左到右来扫描这个图形,明显,只有在碰到矩形的左边界或者右边界的时候,

    这个线段所扫描到的情况才会改变,所以把所有矩形的入边,出边按X值排序。然后根据X值从小到大去处理,就可以

    用线段树来维护扫描到的情况。如上图,X1到X8是所有矩形的入边,出边的X坐标。

    而红色部分的线段,是这样,如果碰到矩形的入边,就把这条边加入,如果碰到出边,就拿走。红色部分就是有线段覆盖的部分。

    要求面积,只需要知道图中的L1到L8。而线段树就是用来维护这个L1到L8的。

    扫描线算法流程:

     

    X1:首先遇到X1,将第一条线段加入线段树,由线段树统计得到线段长度为L1.

     

    X2:然后继续扫描到X2,此时要进行两个动作:

    1.计算面积,目前扫过的面积=L1*(X2-X1)

    2.更新线段。由于X2处仍然是入边,所以往线段树中又加了一条线段,加的这条线段可以参考3幅图中的第一幅。

    然后线段树自动得出此时覆盖的线段长度为L2 (注意两条线段有重叠部分,重叠部分的长度只能算一次)

     

    X3:继续扫描到X3,步骤同X2

    先计算 扫过的面积+=L2*(X3-X2)

    再加入线段,得到L3.

     

    X4:扫描到X4有些不一样了。

    首先还是计算  扫过的面积+=L3*(X4-X3)

    然后这时遇到了第一个矩形的出边,这时要从线段树中删除一条线段。

    删除之后的结果是线段树中出现了2条线段,线段树自动维护这两条线段的长度之和L4

     

    讲到这里算法流程应该很清晰了。

    首先将所有矩形的入边,出边都存起来,然后根据X值排序。

    这里用一个结构体,来存这些信息,然后排序。

    [cpp] view plain copy

    1. //  
    2. struct LINE{  
    3.     int x;//横坐标   
    4.     int y1,y2;//矩形纵向线段的左右端点   
    5.     bool In;//标记是入边还是出边   
    6.     bool operator < (const Line &B)const{return x < B.x;}  
    7. }Line[maxn];   

    [cpp] view plain copy

    1. //  
    2. struct LINE{  
    3.     int x;//横坐标   
    4.     int y1,y2;//矩形纵向线段的左右端点   
    5.     bool In;//标记是入边还是出边   
    6.     bool operator < (const Line &B)const{return x < B.x;}  
    7. }Line[maxn];   


    然后扫描的时候,需要两个变量,一个叫PreL,存前一个x的操作结束之后的L值,和X,前一个横坐标。

    假设一共有Ln条线段,线段下标从0开始,已经排好序。

    那么算法大概是这样:

    [cpp] view plain copy

    1. //  
    2. int PreL=0;//前一个L值,刚开始是0,所以第一次计算时不会引入误差   
    3. int X;//X值   
    4. int ANS=0;//存累计面积  
    5. int I=0;//线段的下标   
    6.   
    7. while(I < Ln){  
    8.     //先计算面积   
    9.     ANS+=PreL*(Line[I].x-X);  
    10.     X=Line[I].x;//更新X值  
    11.     //对所有X相同的线段进行操作   
    12.     while(I < Ln && Line[I].x == X){  
    13.         //根据入边还是出边来选择加入线段还是移除线段   
    14.         if(Line[I].In) Cover(Line[I].y1,Line[I].y2-1,1,n,1);  
    15.         else         Uncover(Line[I].y1,Line[I].y2-1,1,n,1);  
    16.         ++I;  
    17.     }   
    18. }  

    [cpp] view plain copy

    1. //  
    2. int PreL=0;//前一个L值,刚开始是0,所以第一次计算时不会引入误差   
    3. int X;//X值   
    4. int ANS=0;//存累计面积  
    5. int I=0;//线段的下标   
    6.   
    7. while(I < Ln){  
    8.     //先计算面积   
    9.     ANS+=PreL*(Line[I].x-X);  
    10.     X=Line[I].x;//更新X值  
    11.     //对所有X相同的线段进行操作   
    12.     while(I < Ln && Line[I].x == X){  
    13.         //根据入边还是出边来选择加入线段还是移除线段   
    14.         if(Line[I].In) Cover(Line[I].y1,Line[I].y2-1,1,n,1);  
    15.         else         Uncover(Line[I].y1,Line[I].y2-1,1,n,1);  
    16.         ++I;  
    17.     }   
    18. }  


    无论是求面积还是周长,扫描线的结构大概就是上面的样子。

     

    需要解决的几个问题:

    现在有两点需要说明一下。

    (1):线段树进行线段操作时,每个点的含义(比如为什么Cover函数中,y2后面要-1)。

    (2):线段树如何维护扫描线过程中的覆盖线段长度。

    (3):线段树如何维护扫描线过程中线段的数量。

    (1):线段树中点的含义

    线段树如果没有离散化,那么线段树下标为1,就代表线段[1,2)

    线段树下标为K的时候,代表的线段为[K,K+1) (长度为1)

    所以,将上面的所有线段都化为[y1,y2)就可以理解了,线段[y1,y2)只包括线段树下标中的y1,y1+1,...,y2-1

    当y值的范围是10^9时,就不能再按照上面的办法按值建树了,这时需要离散化。

    下面是离散化的代码:

    [cpp] view plain copy

    1. //  
    2. int Rank[maxn],Rn;  
    3. void SetRank(){//调用前,所有y值被无序存入Rank数组,下标为[1..Rn]   
    4.     int I=1;  
    5.     //第一步排序   
    6.     sort(Rank+1,Rank+1+Rn);   
    7.     //第二步去除重复值   
    8.     for(int i=2;i<=Rn;++i) if(Rank[i]!=Rank[i-1]) Rank[++I]=Rank[i];  
    9.     Rn=I;  
    10.     //此时,所有y值被从小到大无重复地存入Rank数组,下标为[1..Rn]   
    11. }   
    12. int GetRank(int x){//给定x,求x的下标   
    13.     //二分法求下标   
    14.     int L=1,R=Rn,M;//[L,R] first >=x  
    15.     while(L!=R){  
    16.         M=(L+R)>>1;  
    17.         if(Rank[M]<x) L=M+1;  
    18.         else R=M;  
    19.     }  
    20.     return L;  
    21. }  

    [cpp] view plain copy

    1. //  
    2. int Rank[maxn],Rn;  
    3. void SetRank(){//调用前,所有y值被无序存入Rank数组,下标为[1..Rn]   
    4.     int I=1;  
    5.     //第一步排序   
    6.     sort(Rank+1,Rank+1+Rn);   
    7.     //第二步去除重复值   
    8.     for(int i=2;i<=Rn;++i) if(Rank[i]!=Rank[i-1]) Rank[++I]=Rank[i];  
    9.     Rn=I;  
    10.     //此时,所有y值被从小到大无重复地存入Rank数组,下标为[1..Rn]   
    11. }   
    12. int GetRank(int x){//给定x,求x的下标   
    13.     //二分法求下标   
    14.     int L=1,R=Rn,M;//[L,R] first >=x  
    15.     while(L!=R){  
    16.         M=(L+R)>>1;  
    17.         if(Rank[M]<x) L=M+1;  
    18.         else R=M;  
    19.     }  
    20.     return L;  
    21. }  


    此时,线段树的下标的含义就变成:如果线段树下标为K,代表线段[ Rank[K] , Rank[K+1] )。

    下标为K的线段长度为Rank[K+1]-Rank[K]

    所以此时叶节点的线段长度不是1了。

    这时,之前的扫描线算法的函数调用部分就稍微的改变了一点:

    [cpp] view plain copy

    1. //   
    2. if(Line[I].In) Cover(GetRank(Line[I].y1),GetRank(Line[I].y2)-1,1,n,1);  
    3. else         Uncover(GetRank(Line[I].y1),GetRank(Line[I].y2)-1,1,n,1);  

    [cpp] view plain copy

    1. //   
    2. if(Line[I].In) Cover(GetRank(Line[I].y1),GetRank(Line[I].y2)-1,1,n,1);  
    3. else         Uncover(GetRank(Line[I].y1),GetRank(Line[I].y2)-1,1,n,1);  

    看着有点长,其实不难理解,只是多了一步从y值到离散之后的下标的转换。

     

    注意一点,如果下标为K的线段长度为Rank[K+1]-Rank[K],那么下标为Rn的线段树的长度呢?

    其实这个不用担心,Rank[Rn]作为所有y值中的最大值,它肯定是一个线段的右端点,

    而右端点求完离散之后的下标还要-1,所以上面的线段覆盖永远不会覆盖到Rn。

    所以线段树其实只需要建立Rn-1个元素,因为下标为Rn的无法定义,也不会被访问。

    不过有时候留着也有好处,这个看具体实现时自己取舍。

     

    (2):如何维护覆盖线段长度

    先提一个小技巧,一般,利用两个子节点来更新本节点的函数写成PushUp();

    但是,对于比较复杂的子区间合并问题,在区间查询的时候,需要合并若干个子区间。

    而合并子区间是没办法用PushUp函数的。于是,对于比较复杂的问题,把单个节点的信息写成一个结构体。

    在结构体内重载运算符"+",来实现区间合并。这样,不仅在PushUp函数可以调用这个加法,区间询问时也可以

    调用这个加法,这样更加方便。

     

    下面给出维护线段覆盖长度的节点定义:

    [cpp] view plain copy

    1. //  
    2. struct Node{  
    3.     int Cover;//区间整体被覆盖的次数   
    4.     int L;//Length : 所代表的区间总长度  
    5.     int CL;//Cover Length :实际覆盖长度  
    6.     Node operator +(const Node &B)const{  
    7.         Node X;  
    8.         X.Cover=0;//因为若上级的Cover不为0,不会调用子区间加法函数   
    9.         X.L=L+B.L;  
    10.         X.CL=CL+B.CL;  
    11.         return X;  
    12.     }  
    13. }K[maxn<<2];  

    [cpp] view plain copy

    1. //  
    2. struct Node{  
    3.     int Cover;//区间整体被覆盖的次数   
    4.     int L;//Length : 所代表的区间总长度  
    5.     int CL;//Cover Length :实际覆盖长度  
    6.     Node operator +(const Node &B)const{  
    7.         Node X;  
    8.         X.Cover=0;//因为若上级的Cover不为0,不会调用子区间加法函数   
    9.         X.L=L+B.L;  
    10.         X.CL=CL+B.CL;  
    11.         return X;  
    12.     }  
    13. }K[maxn<<2];  

     

    
     

    这样定义之后,区间的信息更新是这样的:

    若本区间的覆盖次数大于0,那么令CL=L,直接为全覆盖,不管下层是怎么覆盖的,反正本区间已经全被覆盖。

    若本区间的覆盖次数等于0,那么调用上面结构体中的加法函数,利用子区间的覆盖来计算。

    加入一条线段就是给每一个分解的子区间的Cover+1,删除线段就-1,每次修改Cover之后,更新区间信息。

    这里完全没有下推标记的过程。

    查询的代码如下:

    如果不把区间加法定义成结构体内部的函数,而是定义在PushUp函数内,那么这里几乎就要重写一遍区间合并。

    因为PushUp在这里用不上。

    [cpp] view plain copy

    1. //  
    2. Node Query(int L,int R,int l,int r,int rt){  
    3.     if(L <= l && r <= R){  
    4.         return K[rt];  
    5.     }  
    6.     int m=(l+r)>>1;  
    7.     Node LANS,RANS;  
    8.     int X=0;  
    9.     if(L <= m) LANS=Query(L,R,ls),X+=1;  
    10.     if(R >  m) RANS=Query(L,R,rs),X+=2;  
    11.     if(X==1) return LANS;  
    12.     if(X==2) return RANS;  
    13.     return LANS+RANS;  
    14. }  

    [cpp] view plain copy

    1. //  
    2. Node Query(int L,int R,int l,int r,int rt){  
    3.     if(L <= l && r <= R){  
    4.         return K[rt];  
    5.     }  
    6.     int m=(l+r)>>1;  
    7.     Node LANS,RANS;  
    8.     int X=0;  
    9.     if(L <= m) LANS=Query(L,R,ls),X+=1;  
    10.     if(R >  m) RANS=Query(L,R,rs),X+=2;  
    11.     if(X==1) return LANS;  
    12.     if(X==2) return RANS;  
    13.     return LANS+RANS;  
    14. }  


    维护线段覆盖3次或以上的长度:

     

    [cpp] view plain copy

    1. //  
    2. struct Nodes{    
    3.     int C;//Cover    
    4.     int CL[4];//CoverLength[0~3]    
    5.     //CL[i]表示被覆盖了大于等于i次的线段长度,CL[0]其实就是线段总长   
    6. }ST[maxn<<2];    
    7. void PushUp(int rt){    
    8.     for(int i=1;i<=3;++i){    
    9.         if(ST[rt].C < i) ST[rt].CL[i]=ST[rt<<1].CL[i-ST[rt].C]+ST[rt<<1|1].CL[i-ST[rt].C];    
    10.         else ST[rt].CL[i]=ST[rt].CL[0];    
    11.     }    
    12. }    

    [cpp] view plain copy

    1. //  
    2. struct Nodes{    
    3.     int C;//Cover    
    4.     int CL[4];//CoverLength[0~3]    
    5.     //CL[i]表示被覆盖了大于等于i次的线段长度,CL[0]其实就是线段总长   
    6. }ST[maxn<<2];    
    7. void PushUp(int rt){    
    8.     for(int i=1;i<=3;++i){    
    9.         if(ST[rt].C < i) ST[rt].CL[i]=ST[rt<<1].CL[i-ST[rt].C]+ST[rt<<1|1].CL[i-ST[rt].C];    
    10.         else ST[rt].CL[i]=ST[rt].CL[0];    
    11.     }    
    12. }    


    这里给出节点定义和PushUp().

    更新节点信息的思路大概就是:

    假设要更新CL[3],然后发现本节点被覆盖了2次,那么本节点被覆盖三次或以上的长度就等于子节点被覆盖了1次或以上的长度之和。

    而CL[0]建树时就赋值,之后不需要修改。

     

    (3):如何维护扫描线过程中线段的数量

    [cpp] view plain copy

    1. //   
    2. struct Node{    
    3.     int cover;//完全覆盖层数    
    4.     int lines;//分成多少个线段    
    5.     bool L,R;//左右端点是否被覆盖    
    6.     Node operator +(const Node &B){//连续区间的合并     
    7.         Node C;    
    8.         C.cover=0;    
    9.         C.lines=lines+B.lines-(R&&B.L);    
    10.         C.L=L;C.R=B.R;    
    11.         return C;    
    12.     }    
    13. }K[maxn<<2];    

    [cpp] view plain copy

    1. //   
    2. struct Node{    
    3.     int cover;//完全覆盖层数    
    4.     int lines;//分成多少个线段    
    5.     bool L,R;//左右端点是否被覆盖    
    6.     Node operator +(const Node &B){//连续区间的合并     
    7.         Node C;    
    8.         C.cover=0;    
    9.         C.lines=lines+B.lines-(R&&B.L);    
    10.         C.L=L;C.R=B.R;    
    11.         return C;    
    12.     }    
    13. }K[maxn<<2];    


    要维护被分成多少个线段,就需要记录左右端点是否被覆盖,知道了这个,就可以合并区间了。

    左右两个区间合并时,若左区间的最右侧有线段且右区间的最左侧也有线段,那么这两个线段会合二为一,于是总线段数量会少1.

     

    扫描线求重叠矩形周长:

    这个图是在原来的基础上多画了一些东西,这次是要求周长。

    所有的横向边都画了紫色,所有的纵向边画了绿色。

     

    先考虑绿色的边,由图可以观察到,绿色边的长度其实就是L的变化值。

    比如考虑X1,本来L是0,从0变到L1,所以绿色边长为L1.

    再考虑X2,由L1变成了L2,所以绿色边长度为L2-L1,

    于是,绿色边的长度就是L的变化值(注意上图中令L0=0,L9=0)。

    因为长度是从0开始变化,最终归0.

     

    再考虑紫色的边,要计算紫色边,其实就是计算L的线段是有几个线段组成的,每个线段会贡献两个端点(紫色圆圈)

    而每个端点都会向右延伸出一条紫色边一直到下一个X值。

     

    所以周长就是以上两部分的和。而两部分怎么维护,前面都讲过了,下面给出代码。

    [cpp] view plain copy

    1. //   
    2. struct Node{    
    3.     int cover;//完全覆盖层数    
    4.     int lines;//分成多少个线段    
    5.     bool L,R;//左右端点是否被覆盖    
    6.     int CoverLength;//覆盖长度     
    7.     int Length;//总长度     
    8.     Node(){}    
    9.     Node(int cover,int lines,bool L,bool R,int CoverLength):cover(cover),lines(lines),L(L),R(R),CoverLength(CoverLength){}    
    10.     Node operator +(const Node &B){//连续区间的合并     
    11.         Node C;    
    12.         C.cover=0;    
    13.         C.lines=lines+B.lines-(R&&B.L);    
    14.         C.CoverLength=CoverLength+B.CoverLength;    
    15.         C.L=L;C.R=B.R;    
    16.         C.Length=Length+B.Length;    
    17.         return C;    
    18.     }    
    19. }K[maxn<<2];    
    20. void PushUp(int rt){//更新非叶节点     
    21.     if(K[rt].cover){    
    22.         K[rt].CoverLength=K[rt].Length;    
    23.         K[rt].L=K[rt].R=K[rt].lines=1;    
    24.     }    
    25.     else{    
    26.         K[rt]=K[rt<<1]+K[rt<<1|1];    
    27.     }    
    28. }    

    [cpp] view plain copy

    1. //   
    2. struct Node{    
    3.     int cover;//完全覆盖层数    
    4.     int lines;//分成多少个线段    
    5.     bool L,R;//左右端点是否被覆盖    
    6.     int CoverLength;//覆盖长度     
    7.     int Length;//总长度     
    8.     Node(){}    
    9.     Node(int cover,int lines,bool L,bool R,int CoverLength):cover(cover),lines(lines),L(L),R(R),CoverLength(CoverLength){}    
    10.     Node operator +(const Node &B){//连续区间的合并     
    11.         Node C;    
    12.         C.cover=0;    
    13.         C.lines=lines+B.lines-(R&&B.L);    
    14.         C.CoverLength=CoverLength+B.CoverLength;    
    15.         C.L=L;C.R=B.R;    
    16.         C.Length=Length+B.Length;    
    17.         return C;    
    18.     }    
    19. }K[maxn<<2];    
    20. void PushUp(int rt){//更新非叶节点     
    21.     if(K[rt].cover){    
    22.         K[rt].CoverLength=K[rt].Length;    
    23.         K[rt].L=K[rt].R=K[rt].lines=1;    
    24.     }    
    25.     else{    
    26.         K[rt]=K[rt<<1]+K[rt<<1|1];    
    27.     }    
    28. }    

     

    扫描的代码:

    [cpp] view plain copy

    1. int PreX=L[0].x;//前X坐标     
    2. int ANS=0;//目前累计答案     
    3. int PreLength=0;//前线段总长    
    4. int PreLines=0;//前线段数量     
    5. Build(1,20001,1);    
    6. for(int i=0;i<nL;++i){    
    7.     //操作     
    8.     if(L[i].c) Cover(L[i].y1,L[i].y2-1,1,20001,1);    
    9.     else Uncover(L[i].y1,L[i].y2-1,1,20001,1);    
    10.     //更新横向的边界     
    11.     ANS+=2*PreLines*(L[i].x-PreX);    
    12.     PreLines=K[1].lines;    
    13.     PreX=L[i].x;    
    14.     //更新纵向边界     
    15.     ANS+=abs(K[1].CoverLength-PreLength);    
    16.     PreLength=K[1].CoverLength;    
    17. }    
    18. //输出答案     
    19. printf("%d\n",ANS);    

    [cpp] view plain copy

    1. int PreX=L[0].x;//前X坐标     
    2. int ANS=0;//目前累计答案     
    3. int PreLength=0;//前线段总长    
    4. int PreLines=0;//前线段数量     
    5. Build(1,20001,1);    
    6. for(int i=0;i<nL;++i){    
    7.     //操作     
    8.     if(L[i].c) Cover(L[i].y1,L[i].y2-1,1,20001,1);    
    9.     else Uncover(L[i].y1,L[i].y2-1,1,20001,1);    
    10.     //更新横向的边界     
    11.     ANS+=2*PreLines*(L[i].x-PreX);    
    12.     PreLines=K[1].lines;    
    13.     PreX=L[i].x;    
    14.     //更新纵向边界     
    15.     ANS+=abs(K[1].CoverLength-PreLength);    
    16.     PreLength=K[1].CoverLength;    
    17. }    
    18. //输出答案     
    19. printf("%d\n",ANS);    

     

    求立方体重叠3次或以上的体积:

    这个首先扫描面,每个面内求重叠了3次或以上的面积,然后乘以移动距离就是体积。

    面内扫描线,用线段树维护重叠了3次或以上的线段长度,然后用长度乘移动距离就是重叠了3次或以上的面积。

    扫描面基本原理都跟扫描线一样,就是嵌套了一层而已,写的时候细心一点就没问题了。

     

    八:可持久化 (主席树)

    可持久化线段树,也叫主席树。

    可持久化数据结构思想,就是保留整个操作的历史,即,对一个线段树进行操作之后,保留访问操作前的线段树的能力。

    最简单的方法,每操作一次,建立一颗新树。这样对空间的需求会很大。

    而注意到,对于点修改,每次操作最多影响个节点,于是,其实操作前后的两棵线段树,结构一样,

    而且只有个节点不同,其余的节点都一样,于是可以重复利用其余的点。

    这样,每次操作,会增加个节点。

    于是,这样的线段树,每次操作需要O(log2(n))的空间。

     

    题目:HDU 2665 Kth number      题解

    给定10万个数,10万个询问。

    每个询问,问区间[L,R]中的数,从小到大排列的话,第k个数是什么。

     

    这个题,首先对十万个数进行离散化,然后用线段树来维护数字出现的次数。

    每个节点都存出现次数,那么查询时,若左节点的数的个数>=k,就往左子树递归,否则往右子树递归。

    一直到叶节点,就找到了第k大的数。

     

    这题的问题是,怎么得到一个区间的每个数出现次数。

    注意到,数字的出现次数是满足区间减法的。

    于是要求区间[L,R]的数,其实就是T[R]-T[L-1]  ,其中T[X]表示区间[1,X]的数形成的线段树。

    现在的问题就是,如何建立这10万棵线段树。

     

    由之前的分析,需要O(n log2(n))的空间

    下面是代码:

    [cpp] view plain copy

    1. //主席树     
    2. int L[maxnn],R[maxnn],Sum[maxnn],T[maxn],TP;//左右子树,总和,树根,指针     
    3. void Add(int &rt,int l,int r,int x){//建立新树,l,r是区间, x是新加入的数字的排名  
    4.     ++TP;L[TP]=L[rt];R[TP]=R[rt];Sum[TP]=Sum[rt]+1;rt=TP;//复制&新建    
    5.     if(l==r) return;    
    6.     int m=(l+r)>>1;    
    7.     if(x <= m) Add(L[rt],l,m,x);    
    8.     else       Add(R[rt],m+1,r,x);    
    9. }    
    10. int Search(int TL,int TR,int l,int r,int k){//区间查询第k大    
    11.     if(l==r) return l;//返回第k大的下标    
    12.     int m=(l+r)>>1;    
    13.     if(Sum[L[TR]]-Sum[L[TL]]>=k) return Search(L[TL],L[TR],l,m,k);    
    14.     else return Search(R[TL],R[TR],m+1,r,k-Sum[L[TR]]+Sum[L[TL]]);    
    15. }    

    [cpp] view plain copy

    1. //主席树     
    2. int L[maxnn],R[maxnn],Sum[maxnn],T[maxn],TP;//左右子树,总和,树根,指针     
    3. void Add(int &rt,int l,int r,int x){//建立新树,l,r是区间, x是新加入的数字的排名  
    4.     ++TP;L[TP]=L[rt];R[TP]=R[rt];Sum[TP]=Sum[rt]+1;rt=TP;//复制&新建    
    5.     if(l==r) return;    
    6.     int m=(l+r)>>1;    
    7.     if(x <= m) Add(L[rt],l,m,x);    
    8.     else       Add(R[rt],m+1,r,x);    
    9. }    
    10. int Search(int TL,int TR,int l,int r,int k){//区间查询第k大    
    11.     if(l==r) return l;//返回第k大的下标    
    12.     int m=(l+r)>>1;    
    13.     if(Sum[L[TR]]-Sum[L[TL]]>=k) return Search(L[TL],L[TR],l,m,k);    
    14.     else return Search(R[TL],R[TR],m+1,r,k-Sum[L[TR]]+Sum[L[TL]]);    
    15. }    


    以上就是主席树部分的代码。

    熟悉SBT的,应该都很熟悉这种表示方法。

    L,R是伪指针,指向左右子节点。

    特殊之处是,0 表示空树,并且 L[0]=R[0]=0.

    也就是说,空树的左右子树都是空树。

    而本题中,每一颗树其实都是完整的,刚开始有一颗空树。

    但是刚开始的空树,真的需要用空间去存吗?

    其实不需要,刚开始的空树有这些性质:

    1.每个节点的Sum值为0

    2.每个非叶节点的左右子节点的Sum值也是0

     

    而SBT的空树刚好满足这个性质。而线段树不依赖L,R指针来结束递归。

    线段树是根据区间l,r来结束的,所以不会出现死循环。

    所以只需要把Sum[0]=0;那么刚开始就不需要建树了,只有每个操作的个节点。

     

    这个线段树少了表示父节点的int rt,因为不需要(也不能够)通过rt来找子节点了,而是直接根据L,R来找。

     

    -----------------------------     补充     -------------------------------------

     

    终于又找到一道可以用主席树的题目了:Codeforces 650D.Zip-line  题解

    做这题之前需要会求普通的LIS问题(最长上升子序列问题)。

    九:练习题

    适合非递归线段树的题目:

     

    Codeforces 612D The Union of k-Segments :  题解

    题意:线段求交,给定一堆线段,按序输出被覆盖k次或以上的线段和点。

    基础题,先操作,最后一次下推标记,然后输出,

    维护两个线段树,一个线段覆盖,一个点覆盖。

     

    Codeforces 35E Parade : 题解

    题意:给定若干矩形,下端挨着地面,求最后的轮廓形成的折线,要求输出每一点的坐标。

    思路:虽然是区间修改的线段树,但只需要在操作结束后一次下推标记,然后输出,所以适合非递归线段树。

     

    URAL 1846 GCD2010 :  题解

    题意:总共10万个操作,每次向集合中加入或删除一个数,求集合的最大公因数。(规定空集的最大公因数为1)

     

    Codeforces 12D Ball :   题解

     

    题意:

    给N (N<=500000)个点,每个点有x,y,z ( 0<= x,y,z <=10^9 )

    对于某点(x,y,z),若存在一点(x1,y1,z1)使得x1 > x && y1 > y && z1 > z 则点(x,y,z)是特殊点。

    问N个点中,有多少个特殊点。

     

    提示:排序+线段树

     

    Codeforces 19D Points : 题解

     

    题意:

    给定最多20万个操作,共3种:

    1.add x y         :加入(x,y)这个点

    2.remove x y  :删除(x,y)这个点

    3.find x y         :找到在(x,y)这点右上方的x最小的点,若x相同找y最小的点,输出这点坐标,若没有,则输出-1.

     

    提示:排序,线段树套平衡树

     

    Codeforces 633E Startup Funding : 题解

    这题需要用到一点概率论,组合数学知识,和二分法。

    非递归线段树在这题中主要解决RMQ问题(区间最大最小值问题),由于不带修改,这题用Sparse Table求解RMQ是标答。

    因为RMQ询问是在二分法之内求的,而Sparse Table可以做到O(1)查询,所以用Sparse Table比较好,总复杂度O(n*log(n))。

    不过非递归线段树也算比较快的了,虽然复杂度是O(n*log(n)*log(n)),还是勉强过了这题。

     

    扫描线题目:

     

    POJ 1177 Picture:给定若干矩形求合并之后的图形周长    题解

    HDU 1255 覆盖的面积:给定平面上若干矩形,求出被这些矩形覆盖过至少两次的区域的面积.   题解

    HDU 3642 Get The Treasury:给定若干空间立方体,求重叠了3次或以上的体积(这个是扫描面,每个面再扫描线)题解

    POJ 2482 Stars in your window : 给定一些星星的位置和亮度,求用W*H的矩形能够框住的星星亮度之和最大为多少。  题解

     

    递归线段树题目:

    Codeforces 558E A Simple Task  题解

    给定一个长度不超过10^5的字符串(小写英文字母),和不超过5000个操作。

    每个操作 L R K 表示给区间[L,R]的字符串排序,K=1为升序,K=0为降序。

    最后输出最终的字符串。

     

    Codeforces 527C Glass Carving  :  题解

    给定一个矩形,不停地纵向或横向切割,问每次切割后,最大的矩形面积是多少。

     

    URAL1989 Subpalindromes    题解

    给定一个字符串(长度<=100000),有10万个操作。

    操作有两种:   

    1:改变某个字符。 

    2:判断某个子串是否构成回文串。 

     

    HDU 4288 Coder :  题解

     题意:对一个集合进行插入与删除操作。要求询问某个时刻,集合中的元素从小到大排序之后,序号%5 ==3 的元素值之和。

    这题其实不一定要用线段树去做的,不过线段树还是可以做的。

     

    HDU 2795 BillBoard : 题解

    题意:有一个板,h行,每行w长度的位置。每次往上面贴一张海报,长度为1*wi .

    每次贴的时候,需要找到最上面的,可以容纳的空间,并且靠边贴。

     

    Codeforces 374D Inna and Sequence :题解

    题意:给定百万个数a[m],然后有百万个操作,每次给现有序列加一个字符(0或1),或者删掉已有序列中,第 a[0] 个,第a[1]个,...,第a[m]个。

     

    Codeforces 482B Interesting Array:  题解

    题意就是,给定n,m.

    满足m个条件的n个数,或说明不存在。

    每个条件的形式是,给定 Li,Ri,Qi ,要求   a[Li]&a[Li+1]&...&a[Ri] = Qi ;

    Codeforces 474E Pillar (线段树+动态规划):  题解

    题意就是,给定10^5 个数(范围10^15),求最长子序列使得相邻两个数的差大于等于 d。

     

    POJ 2777  Count Color :   题解

    给线段涂颜色,最多30种颜色,10万个操作。

    每个操作给线段涂色,或问某一段线段有多少种颜色。

    30种颜色用int的最低30位来存,然后线段树解决。

     

    URAL 1019 Line Painting: 线段树的区间合并  题解

    给一段线段进行黑白涂色,最后问最长的一段白色线段的长度。

     

    Codeforces 633H Fibonacci-ish II  :题解

    这题需要用到莫队算法(Mo's Algorithm)+线段树区间修改,不过是单边界的区间,写起来挺有趣。

    另一种解法就是暴力,很巧妙的方法,高复杂度+低常数居然就这么给过了。

     

    树套树题目:

    ZOJ 2112 Dynamic Rankings 动态区间第k大  题解

    做法:树状数组套主席树 或者 线段树套平衡树

     

    Codeforces 605D Board Game :  题解

    做法:广度优先搜索(BFS)  +  线段树套平衡树

     

     

    Codeforces 19D Points : 题解

     

    题意:

    给定最多20万个操作,共3种:

    1.add x y         :加入(x,y)这个点

    2.remove x y  :删除(x,y)这个点

    3.find x y         :找到在(x,y)这点右上方的x最小的点,若x相同找y最小的点,输出这点坐标,若没有,则输出-1.

     

    提示:排序,线段树套平衡树

    展开全文
  • 线段树专辑

    2018-01-05 17:35:37
    个人学习线段树的时候发现的比较好的博客,就转载了。 原文章地址:http://blog.csdn.net/zearot/article/details/48299459 目录: 一:综述 二:原理 三:递归实现 四:非递归原理 五:非递归实现 六:线段...
  • 线段树详解 (原理,实现与应用)

    万次阅读 多人点赞 2015-09-09 01:58:46
    线段树详解 By 岩之痕 一:综述 线段树是一种可以快速进行区间修改和区间查询的数据结构。点修改,区间修改和区间查询的复杂度都是O(log2(n)) 并且,线段树可以维护很多种类的信息。说到线段树就不得不提一下树状...
  • 解两相互垂直的直线中的一个实际应用的计算公式 已知L(Ax+By+C=0)的过p1(x1,y1),p2(x2,y2)两点的直线方程 且p3(x3,y3)是p1到p2两点间的中间点坐标 求过p3且垂直于L的直线中的两个点到p3的距离为d的坐标对(x0,y0)...
  • 线段树讲解

    2018-04-10 14:48:19
    线段树详解By 岩之痕目录:一:综述二:原理三:递归实现四:非递归原理五:非递归实现六:线段树解题模型七:扫描线八:可持久化 (主席树)九:练习题一:综述假设有编号从1到n的n个点,每个点都存了一些信息,用[L,...
  • poj 1436 线段

    2015-04-21 08:42:00
    题意:给你N条线段垂直于x轴)的两个y坐标还有x坐标,问相互看到的三元组有多少个。有点纠结就是,如果两个连线之间正好有一条线段的某个端点,这个也是不能计算的,所以这个端点就有意义了,所以就用上面那个题的...
  • 最好的线段树总结

    万次阅读 多人点赞 2016-11-17 00:59:12
    线段树详解 By 岩之痕 目录: 一:综述 二:原理 三:递归实现 四:非递归原理 五:非递归实现 六:线段树解题模型 七:扫描线 八:可持久化 (主席树) 九:练习题 一:综述 假设有...
  • 大佬的线段树详解

    2018-07-15 11:18:40
    线段树详解 By 岩之痕 目录: 一:综述 二:原理 三:递归实现 四:非递归原理 五:非递归实现 六:线段树解题模型 七:扫描线 八:可持久化 (主席树) 九:练习题 一:综述 假设有编号从1到n的n个点,每个点都...
  • 【详解】线段

    2018-02-09 17:01:08
    线段树详解By 岩之痕目录:一:综述二:原理三:递归实现四:非递归原理五:非递归实现六:线段树解题模型七:扫描线八:可持久化 (主席树)九:练习题一:综述假设有编号从1到n的n个点,每个点都存了一些信息,用[L,...
  • 当两条线段之间可以用一条不覆盖到其他线条且平行于X轴的线段连接时,定义两条线段相互见。求有多少 “两两可见的三条线段” 的数量。 思维: 首先把题目给的数据可视化一下(图有点丑) 然后用肉眼观察(废话) 从...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,851
精华内容 1,940
关键字:

互相垂直的线段