首页 > 代码库 > 函数式线段树的个人理解

函数式线段树的个人理解

这几天一直在搞这个东西,今天总算搞懂了,函数式线段树是一种解决离线算法的数据结构,我是这样理解的,它将所有数据离散化,再对每一个节点 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