其实关于这个东西Seter已经讲的很清楚了。我就讲讲具体实现方法吧（非递归）。
先来看一道例题：poj2104
我们其实是要建n棵线段树，我们用root[i]代表第I棵线段树的根。从1到n建过去。
void update(int old,int l,int r,const int num,int &root){ root = Vc + 1;for (int mid;l != r;) { mid = (l + r) / 2; tree[++Vc] = tree[old]; ++tree[Vc].sum;if (num > mid) old = tree[old].rc,tree[Vc].rc = Vc + 1,l = mid + 1;else old = tree[old].lc,tree[Vc].lc = Vc + 1,r = mid;} tree[++Vc] = node(0,0,tree[old].sum + 1);}这个Update操作就是建第i棵线段树的操作，old为i-1棵线段树的根， l为线段树的左边界， r为右边界， num为要插入的数， fa为一个指针，为这棵线段树当前点的父节点，这样方便更新结点的儿子信息。 ，root为根。具体见代码。
可以这样调用（没有离散化等优化的情况下）：
root[0] = ++Vc;
for (int i = 1; i <= n; ++i)
update(root[i - 1],1,max_ai,a[i],root[i]);
询问其实跟普通线段树一样，用root[r]的值减掉root[l - 1]的值就可以得到a[l]...a[r]建出来的线段树的值了
int query(int l,int r,int rank) { int lb = 1,ub = tmp[0],t; for (; lb != ub; ) { int mid = (lb + ub) / 2; if ((t = tree[tree[r].lc].sum - tree[tree[l].lc].sum) < rank) { rank -= t,lb = mid + 1; l = tree[l].rc; r = tree[r].rc; }else { ub = mid; l = tree[l].lc; r = tree[r].lc; } } return tmp[lb]; }我直接用stl的函数了
std::sort(tmp + 1,tmp + 1 + n);
tmp[0] = std::unique(tmp + 1,tmp + 1 + n) - tmp - 1;
用的时候像这样
std::lower_bound(tmp + 1,tmp + 1 + tmp[0],seq[boundary]) - tmp
时间复杂度是O(N*logN),空间复杂度O(N*logN)
代码：
#include <cstdio> #include <algorithm> const int N = 100000 + 9; struct node { int lc,rc,sum; node(const int a = 0,const int b = 0,const int c = 0): lc(a),rc(b),sum(c){} }tree[N*18]; int tmp[N],n,m,root[N],Vc,a[N],seq[N]; void update(int old,int l,int r,const int num,int &root) { root = Vc + 1; for (int mid;l != r;) { mid = (l + r) / 2; tree[++Vc] = tree[old]; ++tree[Vc].sum; if (num > mid) old = tree[old].rc,tree[Vc].rc = Vc + 1,l = mid + 1; else old = tree[old].lc,tree[Vc].lc = Vc + 1,r = mid; } tree[++Vc] = node(0,0,tree[old].sum + 1); } int query(int l,int r,int rank) { int lb = 1,ub = tmp[0],t; for (; lb != ub; ) { int mid = (lb + ub) / 2; if ((t = tree[tree[r].lc].sum - tree[tree[l].lc].sum) < rank) { rank -= t,lb = mid + 1; l = tree[l].rc; r = tree[r].rc; }else { ub = mid; l = tree[l].lc; r = tree[r].lc; } } return tmp[lb]; } int main() { #ifndef ONLINE_JUDGE freopen("2104.in","r",stdin); freopen("2104.out","w",stdout); #endif scanf("%d%d",&n,&m); for (int i = 1; i <= n; ++i) { scanf("%d",seq + i); tmp[i] = seq[i]; } std::sort(tmp + 1,tmp + 1 + n); tmp[0] = std::unique(tmp + 1,tmp + 1 + n) - tmp - 1; root[0] = ++Vc; /*tree[Vc].lb = 1; tree[Vc].rb = tmp[0]*/; for (int x,y,z,boundary = 1; m--;) { scanf("%d%d%d",&x,&y,&z); if (boundary <= y) for (; boundary <= y; ++boundary) update(root[boundary - 1],1,n,a[boundary] ? a[boundary] : a[boundary] = \ std::lower_bound(tmp + 1,tmp + 1 + tmp[0],seq[boundary]) - tmp,root[boundary]); printf("%d\n",query(root[x - 1],root[y],z)); } }
还有一道题，也是借鉴了函数式编程的思想：bzoj3261: 最大异或和
也是运用了函数式编程的思想。这个我将另写题解。
转载于:https://www.cnblogs.com/lazycal/p/3251740.html
相关资源：JAVA上百实例源码以及开源项目