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

函数式线段树的个人理解

2024-07-11 13:26:42   221人阅读

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

 


联系
我们