线段树是一种重要的数据结构，它主要的优势体现在对段的处理上，用于对数据的更新和查询。适用范围比树状数组更广。关于它的函数和离散化可以自己去搜索一下。
例题：POJ - 2182（http://poj.org/problem?id=2182）
题目大意：有N个牛编号1~N，乱序排成一列，现输入N，以及第2~N个位置上的牛前面有多少头牛小于它的编号，然后正序输出1~N位置上每头牛的编号。如样例：输入5 1 2 1 0。表示五头牛，2~5的位置上分别有1、2、1、0头牛小于位置上牛的编号。输出1~5位置上牛的编号：2 4 5 3 1。
题目思路：倒着判断，有x头牛编号小于某牛，则这个牛编号就应该位于剩余位置的x+1个位置上，找到该编号，删除，重复上述操作。我们可以在纸上写一下，每个位置的读入的a[i] 为：0 1 2 1 0，现在有1 2 3 4 5这几个位置，然后从后开始读，a[5]是0，位于第1个位置即编号为1，删除编号，剩余编号：2 3 4 5；下一个数a[4]=1，位于第2个位置即编号3，删除编号，剩余：2 4 5；重复，a[3]=2，编号为5，剩余：2 4；a[2] = 1，编号为4，剩余2；a[1]=0，编号为2。于是正序输出：2 4 5 3 1。
此题可用线段树，若区间长度大于等于查找的位置，则递归左子树，否则递归右子树，直到叶子结点，结点值就是初始编号。
代码：http://paste.ubuntu.com/16505572/
1 #include <iostream> 2 #include <algorithm> 3 #include <cstdio> 4 using namespace std; 5 int a[9000],ans[9000]; 6 struct node 7 { 8 int l,r,len; 9 }s[30000]; 10 void build(int root,int l,int r) 11 { 12 s[root].l = l; 13 s[root].r = r; 14 s[root].len = r - l + 1; 15 if(l==r) return; 16 build(2*root,l,(l+r)/2); 17 build(2*root+1,(l+r)/2+1,r); 18 } 19 int query(int root,int k) 20 { 21 s[root].len--; 22 if(s[root].l == s[root].r) return s[root].l; 23 if(k<=s[2*root].len) 24 query(2*root,k); 25 else 26 query(2*root+1,k-s[2*root].len); 27 } 28 int main() 29 { 30 int n,i; 31 scanf("%d",&n); 32 for(i=2;i<=n;i++) 33 scanf("%d",&a[i]); 34 a[1]=0; 35 build(1,1,n); 36 for(i=n;i>=1;i--) 37 ans[i] = query(1,a[i]+1); 38 for(i=1;i<=n;i++) 39 printf("%d ",ans[i]); 40 }