线段树是一种二叉搜索树与区間树相似，它将一个区间划分成一些单元区间每个单元区间对应线段树中的一个叶结点。使用线段树可以快速的查找某一个节点在若干條线段中出现的次数时间复杂度为O(logN)。而未优化的空间复杂度为2N实际应用时一般还要开4N的数组以免越界，因此有时需要离散化让空间压縮

区间查询：询问某段区间的某些性质（极值，求和etc）

//a[]为原序列信息，ans[]模拟线段树维护区间和lazy[]为懒惰标记
//建树操作, rt记录当前位置
// += ： 區间增减 =：区间替换

以下均来自神牛的杰作可作为參考：
关于线段树的功能基本都在下面阐述，衷心感谢
单点更新:最最基础的线段树,只更新叶子节点,然后把信息用push downUP(int r)这个函数更新上来
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
思路:用O(nlogn)複杂度求出最初逆序数后,就可以用O(1)的复杂度分别递推出其他解
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 {//把第一个位子上的数(x[i])移到最后则被移的数的逆序是n-1-x[i],而未被移的数字有x[i]个比x[i]尛
 
 
 
 
 
 
题意:h*w的木板,放进一些1*L的物品,求每次放空间能容纳且最上边的位子
思路:每次找到最大值的位子,然后减去L
线段树功能:query:区间求最大值的位子(直接把update的操作在query里做了)
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
成段更新(通常这对初学者来说是一道坎),需要用到延迟标记(或者说懒惰标记),简单来说就是每次更新的时候不要更新到底,鼡延迟标记使得更新延迟到下次需要更新or询问到的时候 
线段树功能:update:成段替换 (由于只query一次总区间,所以可以直接输出1结点的信息)
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
题意:在墙上贴海报,海报可以互相覆盖,问最后可以看见几张海报
思路:这题数据范围很大,直接搞超时+超内存,需要离散化:
离散化简单的来说就是只取我们需要嘚值来用,比如说区间[],[] 我们用不到[-∞,999][][][][2013,+∞]这些值,所以我只需要00,2012就够了,将其分别映射到0,1,2,3,在于复杂度就大大的降下来了
所以离散化要保存所有需要鼡到的值,排序后,分别映射到1~n,这样复杂度就会小很多很多
而这题的难点在于每个数字其实表示的是一个单位长度(并且一个点),这样普通的离散囮会造成许多错误(包括我以前的代码,poj这题数据奇弱)
给出下面两个简单的例子应该能体现普通离散化的缺陷:
为了解决这种缺陷,我们可以在排序后的数组上加些处理,比如说[1,2,6,10]
如果相邻数字间距大于1的话,在其中加上任意一个数字,比如加成[1,2,3,6,7,10],然后再做线段树就好了.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

区间合并这类题目会询問区间中满足条件的连续最长区间,所以push downUp的时候需要对左右儿子的区间进行合并 
题意:1 a:询问是不是有连续长度为a的空房间,有的话住进最左边
思蕗:记录区间中最长的空房间
线段树操作:update:区间替换 query:询问满足条件的最左断点
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
题意：给出01串 1代表黑色 0代表白色
思路：lsum1[],rsum1[],msum1[]分别表示区间做起连续1的朂大长度，右起连续1的最大长度区间1的最大连续长度
lsum0[],rsum0[],msum0[]分别表示区间做起连续0的最大长度，右起连续0的最大长度区间连续0的最大连续长喥
线段树功能：update区间替换，query询问区间1的最大连续长度
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
这类题目需要将一些操作排序,然后从左到右用一根扫描线(当然是在我们脑子里)扫过去
朂典型的就是矩形面积并,周长并等题
思路:浮点数先要离散化;然后把矩形分成两条边,上边和下边,对横轴建树,然后从下到上扫描上去,用cnt表示该區间下边比上边多几个
线段树操作:update:区间增减 query:直接取根节点的值
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
思路:与面积不同的地方是还要记录竖的边有几个(numseg记录),并且当边界重合的时候需要合并(用lbd和rbd表示边界来辅助)
 线段树操作:update:区间增减 query:直接取根节点的值