劃分樹是一種基于線段樹的數據結構。主要用于快速求出(在log(n)的時間復雜度內）序列區間的第k大值。

先看下圖已經建好的劃分樹是什么樣子的，原始數組是[1,5,2,3,6,4,7,3,0,0]，并把它作為樹的第0層，然后把這些數中較小的數再組成[1,2,3,0,0]，順序還是遵照原數組的順序，同樣將較大的數再組成[5,6,4,7,3]。把這兩個數組作為樹的第二層，它們的父親則是第一層的原始數組，這樣一直往下建立，就把劃分樹建好了。

那么到底如何建立這個劃分樹呢？例如如何將[1,5,2,3,6,4,7,3,0,0]分為[1,2,3,0,0]和[5,6,4,7,3]兩部分？

設[1,5,2,3,6,4,7,3,0,0]為數組A，長度為len。

首先預處理將數組A排序：[0,0,1,2,3,3,4,5,6,7]，然后在A中分別找到“0,0,1,2,3”這(len/2)個數，并按數組A的順序放到下一層[1,2,3,0,0]。可以發現，這一操作的復雜度是O(len)。

下面看如何查詢在某一區間內的第k小的數。仍然觀察下圖，要查找區間[3,9]中第2小的數，先標記在原數組A中[3,9]這個區間（數組下標從1開始），即val[0]層涂上黃色背景的部分，現在我們如何知道這個黃色背景的部分在下一層如何分布呢？這里就需要用到一個數組toleft[ ][ ] ，toleft[dep][i]表示下標小于等于i的數中在第dep層中分在其左孩子的個數。

比如圖中val[0]這一層中，toleft[0][1]=1,toleft[0][2]=1,toleft[0][3]=2…..。這樣的話就可以利用toleft數組來確定黃色背景區域在下一層如何分布了。可以確定[3,9]區間在左孩子的有left[0][9]-left[0][3]=3個，所以最終結果肯定在左孩子中找了。當然在這個左孩子中，要排除掉藍色背景部分的1,0，就順利得到下一步要在第二層查找的是：區間[2,4]的第2小的數。依次類推，得到最終結果。

圖片摘自http://www.cnblogs.com/pony1993/archive/2012/07/17/2594544.html

/* * 劃分樹（查詢區間第k大） */ const int MAXN = 100010; int tree[20][MAXN];//表示每層每個位置的值 int sorted[MAXN];//已經排序好的數 int toleft[20][MAXN];//toleft[p][i]表示第i層從1到i有數分入左邊 void build(int l,int r,int dep) 上海大學 ACM 模板 by kuangbin 40 / 152 ACM 模板 kuangbin {if(l == r)return;int mid = (l+r)>>1;int same = mid - l + 1;//表示等于中間值而且被分入左邊的個數for(int i = l; i <= r; i++) //注意是l,不是oneif(tree[dep][i] < sorted[mid])same--;int lpos = l;int rpos = mid+1;for(int i = l; i <= r; i++){if(tree[dep][i] < sorted[mid])tree[dep+1][lpos++] = tree[dep][i];else if(tree[dep][i] == sorted[mid] && same > 0){tree[dep+1][lpos++] = tree[dep][i];same--;}elsetree[dep+1][rpos++] = tree[dep][i];toleft[dep][i] = toleft[dep][l-1] + lpos - l;}build(l,mid,dep+1);build(mid+1,r,dep+1); } //查詢區間第k大的數,[L,R]是大區間，[l,r]是要查詢的小區間 int query(int L,int R,int l,int r,int dep,int k) {if(l == r)return tree[dep][l];int mid = (L+R)>>1;int cnt = toleft[dep][r] - toleft[dep][l-1];if(cnt >= k){int newl = L + toleft[dep][l-1] - toleft[dep][L-1];int newr = newl + cnt - 1;return query(L,mid,newl,newr,dep+1,k);}else{int newr = r + toleft[dep][R] - toleft[dep][r];int newl = newr - (r-l-cnt);return query(mid+1,R,newl,newr,dep+1,k-cnt);} } int main() {int n,m;while(scanf("%d%d",&n,&m)==2){memset(tree,0,sizeof(tree));for(int i = 1; i <= n; i++){scanf("%d",&tree[0][i]);sorted[i] = tree[0][i];}sort(sorted+1,sorted+n+1);build(1,n,0);int s,t,k;while(m--){scanf("%d%d%d",&s,&t,&k);printf("%d\n",query(1,n,s,t,0,k));}}return 0; }

轉載于:https://www.cnblogs.com/lastone/p/5275860.html

總結

以上是生活随笔為你收集整理的[数据结构-划分树小结]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。