首页 > 代码库 > 划分树

划分树

2024-07-25 02:14:00   220人阅读

引用网上的一些介绍：

查找整序列的第k大值往往采用快速查找法。然而此方法会破坏原序列，并且需要O(n)的时间复杂度。抑或使用二叉平衡树进行维护，此方法每次查找时间复杂度仅为O(logn)。然而此方法丢失了原序列的顺序信息，无法查找出某区间内的第k大值。
划分树的基本思想就是对于某个区间，把它划分成两个子区间，左边区间的数小于右边区间的数。查找的时候通过记录进入左子树的数的个数，确定下一个查找区间，最后范围缩小到1，就找到了。
 
个人理解：划分树其实就是将快排的过程保存在数组里面、如果要查找某一区间第K大的值、我们只需要记录在他之前的所有左子树的大小、类似前缀和的思想、然后根据子树的划分、寻找对应的区间、直到找到要找的那个值、
 
 
模板：（学习kuangbin大牛）
 1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5  6 const int MAXN = 100010; 7 int tree[20][MAXN];//表示每层每个位置的值 8 int sorted[MAXN];//已经排序好的数 9 int toleft[20][MAXN];//toleft[p][i]表示第p层从1到i有多少数分入左边10 void build(int l,int r,int dep)11 {12     if(l == r)return;13     int mid = (l+r)>>1;14     int same = mid  - l + 1;//表示等于中间值而且被分入左边的个数15     for(int  i = l; i <= r; i++)  //注意是l,不是one16     if(tree[dep][i] < sorted[mid])17     same--;18     int lpos = l;19     int rpos = mid+1;20     for(int i = l;i <= r;i++)21     {22         if(tree[dep][i] < sorted[mid])23             tree[dep+1][lpos++] = tree[dep][i];24         else if(tree[dep][i] == sorted[mid] && same > 0)25         {26             tree[dep+1][lpos++] =  tree[dep][i];27             same--;28         }29         else30             tree[dep+1][rpos++] = tree[dep][i];31         toleft[dep][i] = toleft[dep][l-1] + lpos  - l;32     }33     build(l,mid,dep+1);34     build(mid+1,r,dep+1);35 }36 37 int query(int L,int R,int l,int r,int dep,int k)38 {39     if(l==r)return tree[dep][l];40     int mid=(L+R)>>1;41     int cnt=toleft[dep][r]-toleft[dep][l-1];42     if(k<=cnt)43     {44         int newl=L+toleft[dep][l-1]-toleft[dep][L-1];45         int newr=newl+cnt-1;46         return query(L,mid,newl,newr,dep+1,k);47     }48     else49     {50         int newr=r+toleft[dep][R]-toleft[dep][r];51         int newl=newr-(r-l-cnt);52         return query(mid+1,R,newl,newr,dep+1,k-cnt);53     }54 }55 int main()56 {57     int n,m;58     while(scanf("%d%d",&n,&m)!=EOF)59     {60         memset(tree,0,sizeof(tree));61         for(int i = 1;i <= n;i++)62         {63             scanf("%d",&tree[0][i]);64             sorted[i] = tree[0][i];65         }66         sort(sorted+1,sorted+n+1);67         build(1,n,0);68         int s,t,k;69         while(m--)70         {71             scanf("%d%d%d",&s,&t,&k);72             printf("%d\n",query(1,n,s,t,0,k));73         }74     }75     return 0;76 }

 

划分树


联系
我们