见闻
我感觉线段树是现在比赛里经常遇见、也很明显的一类问题。它用于解决给定一个大数组，然后对其中区间进行反复查询，也可能涉及求值、修改等操作，题目描述里查询次数超过105。是牺牲空间换取时间的方法。
要掌握这个需要先学习树与堆的相关知识。如果问题规模不大，我们可以使用树状数组的方式实现；如果问题规模很大，我们需要使用离散化，挺难的。这个讲的很好。
相关练习
6.2.1 Lost Cows (2182)
题目描述：
n头牛编号为1…n，打乱顺序排成一列，除去队首的牛之外，给出每头牛在队列中前面编号比它小的牛的数量，求队列中每头牛的编号。
我们推一下样例输入：
5（一共 5 头牛，后面四行为牛牛打乱顺序后的随机排列）
1（第 2 头牛，前面编号比它小的数量为 1 。即第 1 头牛编号比它小）
2（第 3 头牛，前面编号比它小的数量为 2 。即 1 、2 头牛编号都比它小）
1（第 4 头牛，前面编号比它小的数量为 1 。它前面只有一头牛编号比它小）
0（第 5 头牛，前面编号比它小的数量为 0 。它比前面所有的牛牛编号都小，他是第 1 头牛牛）
即，[5] [1] [4] [2] [3]
0 1 1 2
经过输入后面小括号内一系列的描述，可以得出随机排列时牛牛们的原本编号：
2
4
5
3
1
题目分析：
通过对样例的分析，我们不难得出（用 low 指代输入所表示的前面编号比它小的牛的数量）：
最后一个位置的牛的编号为：low + 1
中间位置的牛的编号为：随机排序后面的牛在它前面的数量 + low + 1
然后我们用一个数组确定状态，根据输入逆推即可，据说这样暴力也可以过。
但是，这题我们 应该这样 练习吗？——不应该（三里三气）