读了http://www.notonlysuccess.com/index.php的文章，受益匪浅，现在记下笔记，以后忘了可以在复习。
首先声明一下一些代码的含义：:
- maxn是题目给的最大区间,而节点数要开4倍,确切的来说节点数要开大于maxn的最小2x的两倍
- lson和rson分辨表示结点的左儿子和右儿子,由于每次传参数的时候都固定是这几个变量,所以可以用预定于比较方便的表示
- PushUP(int rt)是把当前结点的信息更新到父结点
- PushDown(int rt)是把当前结点的信息更新给儿子结点
- rt表示当前子树的根(root),也就是当前所在的结点
1.单点更新:最最基础的线段树,只更新叶子节点,然后把信息用PushUP(int r)这个函数更新上来
线段树功能:update:单点增减 query:区间求和
详见http://www.cnblogs.com/shen1000/archive/2012/07/26/2609545.html
线段树功能:update:单点替换 query:区间最值
详见http://www.cnblogs.com/shen1000/archive/2012/07/26/2609609.html
题意:求Inversion后的最小逆序数
思路:用O(nlogn)复杂度求出最初逆序数后,就可以用O(1)的复杂度分别递推出其他解
线段树功能:update:单点增减 query:区间求和
详见http://www.cnblogs.com/shen1000/archive/2012/07/26/2609755.html
题意：买票时有人插队，告诉xi你插在第pos个人后面，然后输出序列x
思路：逆向思维，想着最后一个人来了，要插在pos的后面，则前边应有pos的空格。这个想不明白的话，自己可以模拟着看看，然后就明白了
线段树功能：update：单点变为0.不要query。
详见：http://www.cnblogs.com/shen1000/archive/2012/07/27/2611986.html
这里需要知道一个知识：反素数。详见http://www.cnblogs.com/shen1000/archive/2012/07/29/2613877.html
有了反素数，我们就知道那个序号为最终答案了。
怎么求出那个序号是谁呢？对于这个，目前我只知道用模拟来找出。
思路:每次找出第几个需要要出队的人得位置，然后根据位置，找到下个需要出队的位置。
线段树功能:update:出队一个人，以及找到出队人的下标。 query:找出出对人的左边有多少未出队的人。
详见代码：http://www.cnblogs.com/shen1000/archive/2012/07/29/2613871.html
成段更新(通常这对初学者来说是一道坎),需要用到延迟标记(或者说懒惰标记),简单来说就是每次更新的时候不要更新到底,用延迟标记使得更新延迟到下次需要更新or询问到的时候