首页 > 代码库 > 划分树
划分树
引用网上的一些介绍:
查找整序列的第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 }
划分树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。