单点更新
单点更新的问题似乎直接用树状数组也可以处理。基本思想就是先建树，更新到叶子节点的时候读入数据（注意是先左再右，以保证读入顺序），然后递归处理，递归之后别忘了PushUp，不然更新不了父亲节点的值。建树完成之后写Update函数，简单做法就是如果要更新的位置在左区间就从左区间递归，否则从右边区间递归。到了终点的时候直接修改数值并return，否则的话要记得递归完成之后也是要PushUp。
查询就很简单了，区间匹配的时候直接返回，不然就递归查询。注意求和/最大值之类题目的不同处理方法。
区间更新
区间更新的本质就是惰性标记的使用。惰性标记用以标识一个区间的子区间本来应该被更新成什么样子，但是在区间正好匹配的时候先“偷懒”不继续往下更新，而是做这么一个标记，所以被称为惰性标记。这个描述同样也体现了惰性标记的性质，即仅仅在PushDown操作中才会对它进行操作。
Update函数中，在区间刚好匹配的时候，由于有了惰性标记，我们就可以“偷懒”仅仅更新这个匹配的区间，记录下惰性标记，然后就可以返回了。显然PushDown操作仅仅在需要对子区间进行更新或者查询的时候才会用到。因为我们原本“偷懒”没有把属于子区间的信息也更新下去，而现在又要用到子区间的信息或者是要修改子区间的信息，所以就要PushDown更新下去，而更新过后自然就要去掉父区间的惰性标记，因为我们已经没有在这一层“偷懒”了，信息已经被传递下去了。
等到我们写完对子区间的递归更新之后，就要做一个PushUp操作，把属于父亲节点的新的信息再更新回来，这是因为我们只是修改了子区间的信息，回溯的时候要把父区间也修正过来。这时候我们就不用管惰性标记了，因为从上到下的父亲节点的惰性标记都已经清空了，而真实值则会从下到上更新回去。在更新的时候，如果是求和类型的更新，直接将父区间的值置为两个子区间的和即可；如果是两种类型需要合并（可能相同也可能不同），那么在类型不同的时候就要用特殊值做一个标记，说明这个父亲区间下面的两个区间标记不同，这样Query的时候就知道还要继续往下递归。
同样的道理，Query的时候，也得注意要有PushDown操作，因为我们需要子区间的信息。只是不用PushUp而已，因为我们并没有进行任何新的修改，只是把旧的修改传递下去了而已，所以从下往上不需要更新。
区间替换操作在处理坐标离散化的时候有一点需要特别注意，由于线段树本质上记录的是线段而不是整数位置的端点，所以如果直接把端点拿来离散化，就会造成区间少覆盖的情况。比如我们覆盖区间[1,4]、[1,3]和[4,5]之后，如果添加了一条线段[1,5]，那么实际上这条线段把前面三条都覆盖掉了。因此为了让线段树能够正确处理，在遇到这种情况的时候，需要把坐标值乘以2即可。除此之外，区间替换和区间加减的本质是一样的，只不过一个是记录增量，一个是记录替换值而已。
此外，区间更新还存在一类特殊的经典问题：询问“区间中不同元素”的个数，即染色问题。比如POJ_2528这道题，询问整个区间中有多少不同种类的元素。这类问题如果数据范围比较大，首先要考虑离散化；但是在离散化的过程中容易出问题，所以要在排序后的数组中加上一些处理，比如对于相邻元素差大于1的时候，应该随便再插入一个元素，比如[1,2,6,10]可以加成[1,2,3,6,7,10]，然后再建立线段树即可。而询问的时候还是先照常进行二分查找把区间范围映射过去。
这类问题的处理思路主要在于节点信息的记录，这里我们除了记录节点被覆盖的颜色，还要记录这个区间是否被同一种颜色所覆盖（is_FullFilled）。而对于颜色种类很少的染色问题，直接利用位运算来记录状态即可。在询问时，不仅要求区间匹配，同时也要求区间只有一种颜色时才进行处理并返回，否则继续递归。在处理时要注意只能访问未出现过的颜色（用标记数组记录状态），然后将答案加1后返回。由此可见，每次询问都需要清空颜色的标记数组，所以也就意味着如果颜色种类很多的话，题目中不可能出现很多的询问，比如POJ_2528只有一次询问，因为这个清空的开销太大了。
还有另一类“区间不同”问题，比如HDU_3333这道，询问区间中不同元素的和。这时就不能再用上述的思路了，而是要先区间离散化（目的是缩小值域，来记录每个元素出现的位置）；再读入所有询问，按照右边界排序后转换成离线处理。然后依次遍历每一个元素，保证在处理右边界为r的询问时，出现过的元素一定只出现在尽可能靠右且<=r的位置上，这时候用线段树或者树状数组所求的和就能保证是正确答案。维护方式是：如果一个元素先前未出现过，就将其加入到当前遍历到的位置；否则先删除它之前出现的位置的数值，再加入到当前所遍历的位置。
区间合并
这一类问题主要就是求区间的某种连续元素的最大长度，相比于一般的区间更新，其Update和Query方式都会发生一定变化，而PushUp和PushDown的逻辑会变得更为复杂一些。
对于PushDown操作，本质上和区间更新是一样的。如果父亲区间之前被更新过（未标记为非法值），PushDown的时候就要先将更新值保存到儿子节点上，然后将儿子节点的信息也一同更新掉，最后把父亲节点的更新值去掉（标记为非法），因为父亲区间的值将会在PushUp的时候被更新回来。而对于PushUp操作，需要合并几种造成连续的情况，分别更新区间左侧、右侧以及最大连续，这个具体可以看代码。
有了上述的PushUp和PushDown基本操作，那么接下来的Update就简单了，无非就是找到对应区间来更新而已，如果不是对应区间，就先PushDown，递归更新之后再PushUp。
而对于Query位置的这个操作，就稍微复杂一点。首先要判断是否存在满足条件的区间，这个很简单：如果根节点上记录的整个区间最大连续长度都不满足，那显然就找不到，否则就可以递归查询。如果查询到了叶子节点，就直接返回叶子的位置即可；如果左子树的最大长度满足需要的长度，就从左边进行查询；如果左子树的右边和右子树的左边的和满足，就计算一下对应的位置然后返回；上述都不满足，才会查询右子树。总而言之，只要进入了递归过程，就一定可以找到。
最后，对于“从叶子节点往上PushUp”这个基本操作，其实还有很多有意思的性质可以挖掘。比如HDU3308，题意是询问一个可以任意单点更新的区间上的最长连续上升子序列长度，就可以转化为利用线段树的性质，基于一个确定好的序列，自底向上PushUp信息来维护左右以及最大连续长度的一种操作。
扫描线
好久没有切过扫描线的题目了，留坑待填。