划分树

逃离我推掉我的手 2022-08-02 14:41 218阅读 0赞

划分树，从网上看到的代码的风格主要有两种。

下面的介绍直接是从网上找的看的懂的贴了份过来，其中有些修改。

## 划分树的定义 ##

划分树定义为，它的每一个节点保存区间\[lft,rht\]所有元素，元素顺序与原数组（输入）相同，但是，两个子树的元素为该节点所有元素排序后(rht-lft+1)/2个进入左子树，其余的到右子树，同时维护一个num域，num\[i\]表示lft->i这个点有多少个进入了左子树。

## 划分树的Sample ##

![1349421076_8607.png][]

如果由下而上看这个图，我们就会发现它和归并排序的（归并树）的过程很类似，或者说正好相反。归并树是由下而上的排序，而它确实是由上而下的排序（观察’4’的运动轨迹，我们可以猜到，划分树的排序也是一种稳定的排序方法，这里不是说明的重点，不予证明），但这正是它可以用来解决第k大元素的理由所在。（具体的理由，写完再补）

l  划分树的存储结构（采用层次存储结构（由下而上，由左到右，每层两个孩子，见上图））

constint N=1e5+5;
    int sorted[N];            //对原来集合中的元素排序后的值
    struct node
    {
             int valu[N];       //val记录第k层当前位置元素的值
             int num[N];                //num记录元素所在区间的当前位置之前进入左孩子的个数
             LL sum[N];        //sum记录比当前元素小的元素的和
    }t[20];

l  划分树的建立build

划分树的建立和普通的二叉树的建立过程差不多，仍然采取中序的过程（先根节点，然后左右孩子）。

树的建立相对比较简单，我们依据的是已经排好序的位置进行建树，所以先用快排将原集合还序。要维护每个节点的num域。  
版本一：

void build(int lft,int rht,int ind)
    {
    	if(lft==rht) return;
    	int mid=lft+(rht-lft)>>1;
    	int isame=mid-lft+1,same=0;
    	/* isame用来标记和中间值val_mid相等的，且分到左孩子的数的个数 
    	   初始时，假定当前区间[lft,rht]有mid-lft+1个和valu_mid相等。
    	   先踢掉中间值小的，剩下的就是要插入到左边的
    	 */
    	for(int i=lft;i<=rht;i++)
    		if(t[ind].valu[i]<sorted[mid]) isame--;
    	int ln=lft,rn=mid+1;
    	for(int i=lft;i<=rht;i++)
    	{
    		if(i==lft)		//初始一个子树
    		{
    			t[p].num[i]=0;
    			t[p].sum[i]=0;
    		}
    		else 			//初始区间下一个节点
    		{
    			t[p].num[i]=t[p].num[i-1];
    			t[p].sum[i]=t[p].sum[i-1];
    		}
    		/* 如果大于，肯定进入右孩子，否则判断是否还有相等的应该进入左孩子的，
    		   没有，直接进入右孩子，否则进入左孩子，同时更新节点的sum域和num域
    		 */
    		if(t[p].val[i]<sorted[mid])
    		{
    			t[p].num[i]++;
    			t[p].sum[i]+=t[p].valu[i];
    			t[p+1].valu[ln++]=t[p].valu[i];
    		}
    		else if(t[p].valu[i]>sorted[mid])
    			t[p+1].valu[rn++]=t[p].valu[i];
    		else 
    		{
    			if(same<isame)
    			{
    				same++;
    				t[p].num[i]++;
    				t[p].sum[i]+=t[p].valu[i];
    				t[p+1].valu[ln++]=t[p].valu[i];
    			}
    			else 
    			{
    				t[p+1].valu[rn++]=t[p].valu[i];
    			}
    		}
    	}
    	build(lft,mid,ind+1);
    	build(mid+1,rht,ind+1);
    }

可以看出在版本一里，每个区间的起点的num\[ind\]\[lft\]和sum\[ind\]\[lft\]都会被赋值为0。另一种方式在建立这棵树的时候，并没有这么做，而是在前面的基础上继续。也就是说只有将num\[ind\]\[0\]和sum\[ind\]\[0\]赋值为0。另外这个版本里我将排序后的数组是order而不是sorted

版本二：

void build(int lft,int rht,int ind)
    {
    	if(lft==rht) return;
    	int mid=MID(lft,rht);
    	int same=mid-lft+1,ln=lft,rn=mid+1;
    	for(int i=lft;i<=rht;i++)
    		if(valu[ind][i]<order[mid]) same--;
    	for(int i=lft;i<=rht;i++)
    	{
    		int flag=0;
    		if((valu[ind][i]<order[mid])||valu[ind][i]==order[mid]&&same>0)
    		{
    			flag=1;
    			valu[ind+1][ln++]=valu[ind][i];
    			if(valu[ind][i]==order[mid]) same--;
    			lsum[ind][i]=lsum[ind][i-1]+valu[ind][i];
    		}
    		else
    		{
    			lsum[ind][i]=lsum[ind][i-1];
    			valu[ind+1][rn++]=valu[ind][i];
    		}
    		toLft[ind][i]=toLft[ind][i-1]+flag;
    	}
    	build(lft,mid,ind+1);
    	build(mid+1,rht,ind+1);
    }

l  划分树的查找

在区间\[a,b\]上查找第k大的元素，同时返回它的位置和区间小于\[a,b\]的所有数的和。

1.      如果t\[p\].num\[b\]-t\[p\].num\[a-1\]>=k，即，进入左孩子的个数已经超过k个，那么就往左孩子里面查找，同时更新\[a,b\]=>\[lft+t\[p\].num\[a-1\]，lft+t\[p\].num\[b\]-1\]

2.      如果t\[p\].num\[b\]-t\[p\].num\[a-1\]<k，即，进入p的左孩子的个数小于k个，那么就要往右孩子查找第k-s(s表示进入左孩子的个数)个元素。同时更新sum域，因而这样求出的sum只是严格小于在\[a,b\]区间中第k大的数的和。

详细过程见代码和注释：  
/\*在区间\[a,b\]上查找第k大元素，同时sum返回区间\[a,b\]中小于第k大元素的和\*/

int query(int a,int b,int k,int p,int lft,int rht)
    {
    	if(lft==rht) return t[p].valu[a];
    	/*到达叶子结点就找到该元素，返回
    	S 记录区间[a,b]中进入左孩子的元素的个数
    	SS 记录区间[lft,a-1]中进入左孩子的元素的个数
    	SSS 记录区间[a,b]中小于第k大的元素的值和
    	B2 表示[lft,a-1]中分到右孩子的个数
    	BB 表示[a,b]中分到右孩子的个数
    */
    	int s,ss,b2,bb,mid=lft+(rht-lft)/2;
    	double sss=0;
    	if(a==lft)//端点重合的情况，单独考虑
    	{
    		s = t[p].num[b]; 
    		ss = 0; 
    		sss = t[p].sum[b];
    	}
    	else 
    	{
    		s = t[p].num[b] - t[p].num[a-1];
    		ss = t[p].num[a-1]; 
    		sss = t[p].sum[b] - t[p].sum[a-1];
    	}
    	if(s>=k)	//进入左孩子，同时更新区间端点值。
    	{
    		a = lft + ss;// 
    		b = lft + ss + s - 1; 
    		return query(a, b, k, p+1, lft, mid);
    	}
    	else 
    	{
    		bb = a - lft - ss;
    		b2 = b - a - 1 - s; 
    		a = mid + bb + 1; 
    		b = mid + bb + b2; 
    		sum += sss;
    		return query(a,b,k-s,p+1,mid+1,rht);
    	}
    }

版本二：

int query(int st,int ed,int k,int lft,int rht,int ind)
    {
    	if(lft==rht) return valu[ind][lft];
    	/*
    	  	lx表示从lft到st-1这段区间内有多少个数进入左子树
    		ly表示从st到ed这段区间内有多少个数进入左子树
    		rx表示从lft到st-1这段区间内有多少个数进入右子树
    		ry表示从st到ed这段区间内有多少个数进入右子树
    	 */
    	int mid=MID(lft,rht);
    	int lx=toLft[ind][st-1]-toLft[ind][lft-1];
    	int ly=toLft[ind][ed]-toLft[ind][st-1];
    	int rx=st-1-lft+1-lx;
    	int ry=ed-st+1-ly;
    	if(ly>=k) return query(lft+lx,lft+lx+ly-1,k,lft,mid,ind+1);
    	else
    	{
    		isum+=lsum[ind][ed]-lsum[ind][st-1];
    		st=mid+1+rx;
    		ed=mid+1+rx+ry-1;
    		return query(st,ed,k-ly,mid+1,rht,ind+1);
    	}
    }

下面给出POJ  2104 K-th Number的两种风格的代码。

风格一：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    #define MID(a,b) (a+((b-a)>>1))
    const int N=1e5+5;
    struct node
    {
    	int valu[N],num[N];
    };
    struct P_Tree
    {
    	int n,order[N];
    	node t[20];
    	void init(int len)
    	{
    		n=len;
    		for(int i=1;i<=n;i++)
    		{
    			scanf("%d",&order[i]);
    			t[0].valu[i]=order[i];
    		}
    		sort(order+1,order+1+n);
    		build(1,n,0);
    	}
    	void build(int lft,int rht,int ind)
    	{
    	    //cout<<lft<<" "<<rht<<endl;
    	    if(lft==rht) return;
    		int mid=MID(lft,rht);
    		int lsame=mid-lft+1,same=0,ln=lft,rn=mid+1;
    		for(int i=lft;i<=rht;i++)
    			if(t[ind].valu[i]<order[mid]) lsame--;
    		for(int i=lft;i<=rht;i++)
    		{
    			if(i==lft) t[ind].num[i]=0;
    			else t[ind].num[i]+=t[ind].num[i-1];
    
    			if(t[ind].valu[i]<order[mid])
    				t[ind].num[i]++,t[ind+1].valu[ln++]=t[ind].valu[i];
    			else if(t[ind].valu[i]>order[mid])
    				t[ind+1].valu[rn++]=t[ind].valu[i];
    			else
    			{
    				same++;
    				if(lsame>=same)
    					t[ind].num[i]++,t[ind+1].valu[ln++]=t[ind].valu[i];
    				else t[ind+1].valu[rn++]=t[ind].valu[i];
    			}
    		}
    		build(lft,mid,ind+1);
    		build(mid+1,rht,ind+1);
    	}
    	int query(int st,int ed,int k,int lft,int rht,int ind)
    	{
    		if(lft==rht) return t[ind].valu[lft];
    		int lx,ly,rx,ry,mid=MID(lft,rht);
    		if(st==lft) lx=0,ly=t[ind].num[ed];
    		else lx=t[ind].num[st-1],ly=t[ind].num[ed]-t[ind].num[st-1];
    		if(ly>=k)
    		{
    			st=lft+lx;
    			ed=lft+lx+ly-1;
    			return query(st,ed,k,lft,mid,ind+1);
    		}
    		else
    		{
    			rx=st-1-lft+1-lx;
    			ry=ed-st+1-ly;
    			st=mid+1+rx;
    			ed=mid+1+rx+ry-1;
    			return query(st,ed,k-ly,mid+1,rht,ind+1);
    		}
    	}
    }tree;
    int main()
    {
    	int n,m;
    	while(scanf("%d%d",&n,&m)!=EOF)
    	{
    		tree.init(n);
    		for(int i=0;i<m;i++)
    		{
    			int a,b,c;
    			scanf("%d%d%d",&a,&b,&c);
    			int res=tree.query(a,b,c,1,n,0);
    			printf("%d\n",res);
    		}
    	}
    	return 0;
    }

风格二：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    #define MID(a,b) (a+((b-a)>>1))
    typedef long long LL;
    const int N=1e5+5;
    struct P_Tree
    {
    	int n,order[N];
    	int valu[20][N],num[20][N];
    	LL sum[N],lsum[20][N],isum;
    	void init(int len)
    	{
    		n=len;	sum[0]=0;
    		for(int i=0;i<20;i++) valu[i][0]=0,num[i][0]=0,lsum[i][0]=0;
    		for(int i=1;i<=n;i++)
    		{
    			scanf("%d",&order[i]);
    			valu[0][i]=order[i];
    			sum[i]=sum[i-1]+order[i];
    		}
    		sort(order+1,order+1+n);
    		build(1,n,0);
    	}
    	void build(int lft,int rht,int ind)
    	{
    		if(lft==rht) return;
    
    		int mid=MID(lft,rht);
    		int same=mid-lft+1,ln=lft,rn=mid+1;
    		for(int i=lft;i<=rht;i++)
    			if(valu[ind][i]<order[mid]) same--;
    		for(int i=lft;i<=rht;i++)
    		{
    			int flag=0;
    			if((valu[ind][i]<order[mid])||(valu[ind][i]==order[mid]&&same))
    			{
    				flag=1;
    				valu[ind+1][ln++]=valu[ind][i];
    				lsum[ind][i]=lsum[ind][i-1]+valu[ind][i];
    				if(valu[ind][i]==order[mid]) same--;
    			}
    			else 
    			{
    				valu[ind+1][rn++]=valu[ind][i];
    				lsum[ind][i]=lsum[ind][i-1];
    			}
    			num[ind][i]=num[ind][i-1]+flag;
    		}
    		build(lft,mid,ind+1);
    		build(mid+1,rht,ind+1);
    	}
    	int query(int st,int ed,int k,int lft,int rht,int ind)
    	{
    		if(lft==rht) return valu[ind][lft];
    
    		int mid=MID(lft,rht);
    		int lx=num[ind][st-1]-num[ind][lft-1];
    		int ly=num[ind][ed]-num[ind][st-1];
    		int rx=st-1-lft+1-lx;
    		int ry=ed-st+1-ly;
    		if(ly>=k) return query(lft+lx,lft+lx+ly-1,k,lft,mid,ind+1);
    		else 
    		{
    			isum+=lsum[ind][ed]-lsum[ind][st-1];
    			st=mid+1+rx;
    			ed=mid+1+rx+ry-1;
    			return query(st,ed,k-ly,mid+1,rht,ind+1);
    		}
    	}
    }tree;
    int main()
    {
    	int n,m;
    	while(scanf("%d%d",&n,&m)!=EOF)
    	{
    		tree.init(n);
    		for(int i=0;i<m;i++)
    		{
    			int a,b,c;
    			scanf("%d%d%d",&a,&b,&c);
    			int res=tree.query(a,b,c,1,n,0);
    			printf("%d\n",res);
    		}
    	}
    	return 0;
    }

[1349421076_8607.png]: https://img-my.csdn.net/uploads/201210/05/1349421076_8607.png