Processing math: 100%
09月04, 2014

记录一下对归并树和划分树的理解

注意:这是一篇从旧博客恢复的文章。

原地址:http://freemeepo.com/acm/1410.html


归并树:在nlogn的时间内离线处理一个序列,在log3n的时间查询[l, r]区间内的第K大数。

其原理就是利用归并排序+线段树。

记录下归并排序的过程,可以得到logn个长度为n的序列,把这logn个序列纵向展开,按照线段树的形式分解区间,每个序列是一棵线段树,但是第i个序列只保留其展开成线段树的第i层,这样我们就得到了logn个线段树的logn层,即一个新线段树。(第一个序列是排完序的序列,第logn个序列是未排序的序列。)

或者说是用归并排序分割出来的区间可以正好建成一棵线段树,如下:

  • [1, 2, 3, 4, 5, 6, 7, 8]
  • [1, 3, 5, 7][2, 4, 6, 8]
  • [3, 5][1, 7][2, 4][6, 8]
  • [5][3][1][7][4][2][8][6]
json

3个 logn是这么来的:

  1. 在线段树的一个节点里,找到数x是第几大数可以二分。

  2. 在线段树中找[l, r]区间需要找logn个线段树区间,这些区间的信息合起来就可以知道某个数在[l, r]里是第几大数。

  3. 现在我们已经可以在log2n内找到某个数在[l, r]区间里是第几大数,接着我们1,n二分下标,用排好序的数组的下标为mid的元素,进行上面两个操作即可。

归并树是在归并排序的过程中建好树的,而划分树正相反。

划分树:在nlogn的时间内离线处理一个序列,在logn的时间查询[l, r]区间内的第K大数。划分树的建树依赖一个排好序的数组来辅助建树。

设初始数组为a,先对数组排好序,设排好序的数组为b,这样我们就可以知道任何一个区间[l, r]的中间值。于是我们现在对初始序列a进行建树,很显然初始序列的a[1, n]区间的中间值必然是排好序的数组的b[1, n]区间的b[n/2]的值,我们用这个值,把初始序列a分成两部分,左边都是小于等于这个值的,右边是大于这个值的。接着再对这两个区间重复上面的操作,即可得到一棵线段树。很显然,线段树的最下面一层是个有序序列,如下:

  • [5, 3, 1, 7, 4, 2, 8, 6]
  • [3, 1, 4, 2][5, 7, 8, 6]
  • [1, 2][3, 4][5, 6][7, 8]
  • [1][2][3][4][5][6][7][8]
json

同时,我们在处理每个区间的时候,用一个sum数组记录i左边有多少个元素进入了左区间。例如线段树第一层sum[4]记录的是第四个数左边有多少个数进入了左区间,有3、1两个数所以是2。

所以我们在查询某个区间[L, R]的时候,只需要查询sum[R]-sum[L-1]就可以知道这整个区间有多少个数进入了左边,如果数量大于等于要查询的K(要查的是第K大数的值),说明必定要去左区间继续找K,否则去右区间找K-(sum[R]-sum[L-1])。需要注意的是,查询的区间[L, R]也要相应修改。例如:设线段树区间是l和r。如果此时将要继续查询的是左区间,那么查询的区间[L, R]要修改成[l+sum[rt][L-1], l+sum[rt][R]-1],因为有sum[rt][L-1]个数跑到了左区间的最左边,而这sum[rt][L-1]个数并不在我们要查询的[L, R]区间内。右区间同理要改成[mid+1+L-l-sum[rt][L-1], mid+1+R-l-sum[rt][R]]。而且这样的写法能够保证查询的[L, R]一定在线段树的区间[l, r]之内。

值得注意的是,在建树时要对有重复元素的情况处理一下,因为如果值为b[n/2]的元素有多个的话,必然要出现其中一部分在左区间,另一部分在右区间的情况,必须处理好这种情况而不能直接按“小于等于b[n/2]的放左边其他在右边”来处理。解决方法是先找一下有多少个元素是小于b[n/2]的,于是就可以知道剩下多少个位置是留给恰好等于b[n/2]的元素的了。

于是,我们可以在logn的时间内完成查询操作。

模板在此:(POJ2761 POJ2104

  • #include<cstdio>
  • #include<cstdlib>
  • #include<cstring>
  • #include<cmath>
  • #include<ctime>
  • #include<cassert>
  • #include<climits>
  • #include<iostream>
  • #include<algorithm>
  • #include<string>
  • #include<vector>
  • #include<deque>
  • #include<list>
  • #include<set>
  • #include<map>
  • #include<stack>
  • #include<queue>
  • #include<numeric>
  • #include<iomanip>
  • #include<bitset>
  • #include<sstream>
  • #include<fstream>
  • #define debug puts("-----")
  • #define pi (acos(-1.0))
  • #define eps (1e-8)
  • #define inf (1<<30)
  • #define INF (1ll<<62)
  • using namespace std;
  • const int NV=100005;
  • int a[NV],sum[20][NV],s[20][NV];
  • void build(int l,int r,int rt=0)
  • {
  • int mid=l+r>>1;
  • int ln=l,rn=mid+1;
  • int x=a[mid];
  • sum[rt][l]=0;
  • int cnt=mid-l+1;
  • for (int i=l;i<=r;i++)
  • if (s[rt][i]<x) cnt--;
  • for (int i=l; i<=r; i++)
  • {
  • if (i>l) sum[rt][i]=sum[rt][i-1];
  • if (ln<=mid&&(s[rt][i]<x||s[rt][i]==x&&cnt-->0))
  • s[rt+1][ln++]=s[rt][i],sum[rt][i]++;
  • else s[rt+1][rn++]=s[rt][i];
  • }
  • if (l<mid) build(l,mid,rt+1);
  • if (mid+1<r) build(mid+1,r,rt+1);
  • }
  • int query(int k,int L,int R,int l,int r,int rt=0)
  • {
  • if (l==r) return s[rt][l];
  • int mid=l+r>>1;
  • int lsum=0;
  • if (L>l) lsum=sum[rt][L-1];
  • int t=sum[rt][R]-lsum;
  • if (t>=k) return query(k,l+lsum,l+sum[rt][R]-1,l,mid,rt+1);
  • else return query(k-t,mid+1+L-l-lsum,mid+1+R-l-sum[rt][R],mid+1,r,rt+1);
  • }
  • void init(int n)
  • {
  • for (int i=0; i<20; i++) sum[i][0]=0;
  • for (int i=1; i<=n; i++) s[0][i]=a[i];
  • sort(a+1,a+n+1);
  • build(1,n);
  • }
  • int main()
  • {
  • int n,m;
  • cin>>n>>m;
  • for (int i=1; i<=n; i++)
  • scanf("%d",&a[i]);
  • init(n);
  • while(m--)
  • {
  • int l,r,k;
  • scanf("%d%d%d",&l,&r,&k);
  • printf("%d\n",query(k,l,r,1,n));
  • }
  • return 0;
  • }
autoit

本文链接:https://debug.fanzheng.org/post/merger-tree-and-parti-tree.html

-- EOF --

Comments

评论加载中...

注:如果长时间无法加载,请针对 disq.us | disquscdn.com | disqus.com 启用代理。