首页 > 代码库 > 函数式线段树的个人理解
函数式线段树的个人理解
这几天一直在搞这个东西,今天总算搞懂了,函数式线段树是一种解决离线算法的数据结构,我是这样理解的,它将所有数据离散化,再对每一个节点 N 建一颗(1,N)的线段树,这是它的思路,当然如果真正的去建这么多线段树,内存肯定爆了,所以这个就是函数式线段树的高级的地方,它从分利用前缀和的思想,后一颗树和前一棵树分享了一半的节点,什么意思呢,若现在我们得到了T[N],也就是(1,N)这些节点的线段树,我们要建(1,N+1)这颗线段树T[N+1],这样我们只需要在T[N]的基础上加入a[N+1]这个节点,如果a[N+1]被放入T[N+1]的左子树,那么T[N+1]将和T[N]公用右子树,同理,若a[N+1]被放入右子树,T[N+1]将和T[N]公用左子树,这样就能减少太多内存的消耗了。而建好这颗树之后我们就可以用它的性质去解决一些题目,特别是区间第k大数,可同属处理动态和静态的问题,对于静态的若要查询(L,R,K),只需看看R的左子树和L-1的左子树之差,若大于K,继续向他们的左子树查找第K大值,若小于K,则要向他们的右子树查找K-他们的差,这样直到到叶子节点,就是我们要的答案了。而对于动态的,我们可以用树状数组来套这颗函数式线段树,即树状数组的每个节点都是一颗线段树,这样来处理,下面给出一个静态的程序
POJ 2104
#include<map>#include<set>#include<stack>#include<queue>#include<cmath>#include<vector>#include<cstdio>#include<string>#include<cstring>#include<cstdlib>#include<iostream>#include<algorithm>#define inf 0x0f0f0f0fusing namespace std;const double pi=acos(-1.0);const double eps=1e-8;typedef pair<int,int>pii;const int maxn=200000+10;const int N=maxn*30;int a[maxn],b[maxn],Ls[N],Rs[N],T[maxn],sum[N],n,m,tot;void init(){ sort(b+1,b+n+1); m=unique(b+1,b+n+1)-b-1; for (int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+m+1,a[i])-b;}int build(int x,int y){ int root=tot++; sum[root]=0; if (x==y) return root; int mid=x+(y-x)/2; Ls[root]=build(x,mid); Rs[root]=build(mid+1,y);}int insert(int root,int x,int v){ int newroot=tot++,temp=newroot; sum[newroot]=sum[root]+v; int L=1,R=m; while(L<R) { int mid=L+(R-L)/2; if (x<=mid) { Ls[newroot]=tot++; Rs[newroot]=Rs[root]; newroot=Ls[newroot]; root=Ls[root]; R=mid; } else { Ls[newroot]=Ls[root]; Rs[newroot]=tot++; newroot=Rs[newroot]; root=Rs[root]; L=mid+1; } sum[newroot]=sum[root]+v; } return temp;}int get_K_num(int Lroot,int Rroot,int k){ int L=1,R=m; while(L<R) { int mid=L+(R-L)/2; int t=sum[Ls[Rroot]]-sum[Ls[Lroot]]; if (t>=k) { R=mid; Rroot=Ls[Rroot]; Lroot=Ls[Lroot]; } else { L=mid+1; Rroot=Rs[Rroot]; Lroot=Rs[Lroot]; k-=t; } } return L;}int main(){ int q,x,y,k; while(scanf("%d%d",&n,&q)!=EOF) { tot=0; for (int i=1;i<=n;i++) { scanf("%d",&a[i]); b[i]=a[i]; } init(); T[0]=build(1,m); for (int i=1;i<=n;i++) T[i]=insert(T[i-1],a[i],1); while(q--) { scanf("%d%d%d",&x,&y,&k); printf("%d\n",b[get_K_num(T[x-1],T[y],k)]); } } return 0;}
作者 chensunrise
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。