Basic Topic
Intro
线段树：本质上将每个局部的计算结果保留下来，在需要的时候通过少量的操作就可以获取到最终的结果。因为 2 分组合是最佳的方式， 所以用二叉树建立线段树目前遇到的线段树分为 2 种：一种按照输入数据的值域来建的树， 另外一种按照输入数据的个数（即位置）
线段树适合解决什么问题
区间更新
lazy 更新的方式，只在根节点记录需要加减多少每个字节的存放的是和父节点的差值查询区间内最大值， 最小值，sum 和等
如果要查询 区间内的 第 k 大值就需要做特殊处理（最大值具有偏序性， 即求父节点的最大值只要得知两个字节点的最大值。但是某个节点上第 k 大值不能通过 2 个子节点上第 k 大值获取）很特别的问题
线段树能快速解决 （leetcode 上求存水量的问题），但是没有 尺取法快
线段树 vs 树状数组
Advanced Topic
树套树
二分思想（线段树， 二叉树，跳表）
划分树
区间 Kth Number也可以用求区间内不同数的个数
输入参数 1 5 6 3 8 8 4 2 ， 求 2 ～6 区间有多少个不同的数？ 因为 2～6 区间第 4 大的数是 8， 第 5 大的数也是 8， 所以得出 2～6 区间有 4 个不同的数
这个用线段树或树状数组就可以做出来，为什么要用划分树这种难写的数据结构呢？
转载于:https://www.cnblogs.com/tmortred/p/7865467.html
