用劃分樹來解決選定區間內的第K大值，其實也就兩步！一步是建樹，另一步則是查詢。
先說我對建樹的理解吧！
建樹的過程很簡單：兩步就OK了！
第一步：找到序列的中位數，把大於中位數的扔到中位數的左邊，小於中位數的扔到數的右邊。這樣整個序列就被分成了兩個區間。
第二步：對每個子區間，也分別執行第一步操作，直到序列中只有一個元素為止。
可以看出，建樹是一個遞歸的過程，與線段樹的建樹有相似之處。
劃分樹的建樹需要注意以下幾點：
第一：建樹是分層的，所以代碼中用的是二維數組tree[20][M]。一般10W級別的數據，20層已經夠了。
第二：建樹劃分的標准是中位數，所以需要排序。而且只排一次序就OK了，為什麼只排一次就OK了，我很久都沒明白這一點。其實是這樣的：對於任意序列： 劃分後，左邊的數據永遠不會大於右邊的數據。那麼對左邊數據單獨排序與整體排序的結果是一樣的，所以排一次序就OK了！
第三：劃分樹劃分好的數據永遠在存放在下一層。比如數據：
tree[0][M]=1 5 2 6 3 7 4
排序後為：1 2 3 4 5 6 7
中位數為：4
劃分後的結果為：tree[1][M]=1 2 3 4 5 6 7(這組數據有點特殊，劃分後來就已經是排好序的了)紅黑色字體都仍按原未排順序排列
（紅色表示劃分到中位數的左邊，黑色表示劃分到中位數的右邊）
接著劃分：tree[2][M]=1 2 3 4 5 6 7
再接著分：tree[3][M]=1 2 3 4 5 6 0
到這裡已經分完了，為什麼最後是0呢？在第2層（tree[2][M]）,7已經分完了，所以不用再分
第四：劃分到最後，實際上已經對序列進行排序了。
劃分的時候還有一點需要處理：如果有多個數據相同怎麼辦呢？通過一種特殊的處理：盡量使左右兩邊平均分配相同的數。這個特殊處理是這樣的：
在沒分之前，先假設中位數左邊的數據suppose都已經分到左邊了，所以suppose=mid-left+1;然後如果真的分在左邊，即if(tree[level][i]<sorted[mid])
suppose--；suppose就減一！到最後，如果suppos=1，則說明中位數左邊的數都小於中位數，如果有等於中位數的，則suppose大於1。
最後分配的時候，把suppose個數，分到左邊就可以了，剩下的分到右邊！因為suppose的初值是mid-left+1,這樣就能保證中位數左邊和右邊的數平衡了！
第五：劃分的過程，需要把每層的數據記錄：toLeft[20][M]。toLeft[i][j]定義為：第i層[1,j]之間有多
模板：
[cpp]
#include<stdio.h>
#include<algorithm>
using namespace std;
#define M 100005
int tree[20][M],sorted[M];
int toLeft[20][M];
void build(int level,int left,int right){
if(left==right)return ;
int mid=(left+right)>>1;
int i;
int suppose;//假設在中位數sorted[mid]左邊的數都全部小於sorted[mid]
suppose=mid-left+1;
for(i=left;i<=right;i++){
if(tree[level][i]<sorted[mid]){
suppose--;
}
}
//如果suppose==1，則說明數組中值為sorted[mid]只有一個數。比如序列：1 3 4 5 6，sorted[mid]=4
/*如果suppose>1，則說明數組中左半邊值為sorted[mid]的不止一個數,為mid-suppose。比如序列：1 4 4 4 6，sorted[mid]=4
*/
int lpos=left,rpos=mid+1;
for(i=left;i<=right;i++){
if(i==left){//這裡是預處理，相當與初始化
toLeft[level][i]=0;
}else{
toLeft[level][i]=toLeft[level][i-1];
}
if(tree[level][i]<sorted[mid]){//劃分到中位數左邊
toLeft[level][i]++;
tree[level+1][lpos++]=tree[level][i];
}else if(tree[level][i]>sorted[mid]){//劃分到中位數右邊
tree[level+1][rpos++]=tree[level][i];
}else{//這裡，suppose大於0的數劃分到中位數的左邊
if(suppose!=0){//這裡的處理太巧妙了！帥氣！
suppose--;
toLeft[level][i]++;
tree[level+1][lpos++]=tree[level][i];
}else{//表示
tree[level+1][rpos++]=tree[level][i];
}
}
}
build(level+1,left,mid);
build(level+1,mid+1,right);
}
//在[left,right]數據中查詢[qleft,qright]中第k大的數據
int query(int level,int left,int right,int qleft,int qright,int k){
if( qleft==qright)
return tree[level][qleft];
int s;//代表[left,qleft)之間有多個個元素被分到左邊
int ss;//[qleft, qright]內將被劃分到左子樹的元素數目
int mid=(left+right)>>1;
if(left==qleft){
s=0;
ss=toLeft[level][qright];
}else{
s=toLeft[level][qleft-1];
ss=toLeft[level][qright]-s;
}
int newl,newr;
if(k<=ss){//查詢左邊
newl=left+s;
newr=left+s+ss-1;
return query(level+1,left,mid,newl,newr,k);
}else{//查詢右邊
newl=mid-left+1+qleft-s;
newr=mid-left+1+qright-s-ss;
return query(level+1,mid+1,right,newl, newr,k - ss);
}
}
int main(){
int n,m;
while(scanf("%d %d",&n,&m)!=EOF)
{
int i;
for(i=1;i<=n;i++){
scanf("%d",&tree[0][i]);
sorted[i]=tree[0][i];
}
sort(sorted+1,sorted+n+1);
build(0,1,n);
for(i=0;i<n;i++){
for(int j=1;j<=n;j++){
printf("%d ",toLeft[i][j]);
}
printf("\n");
}
int ql,qr,k;
for(i=0;i<m;i++){
scanf("%d %d %d",&ql,&qr,&k);
printf("%d\n",query(0,1,n,ql,qr,k));
}
}
return 0;
} 個數據被分到了左邊（注意這裡用的是閉區間）。
The Famous ICPC Team Again
Time Limit: 30000/15000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 558 Accepted Submission(s): 260
Problem Description
When Mr. B, Mr. G and Mr. M were preparing for the 2012 ACM-ICPC World Final Contest, Mr. B had collected a large set of contest problems for their daily training. When they decided to take training, Mr. B would choose one of them from the problem set. All the problems in the problem set had been sorted by their time of publish. Each time Prof. S, their coach, would tell them to choose one problem published within a particular time interval. That is to say, if problems had been sorted in a line, each time they would choose one of them from a specified segment of the line.
Moreover, when collecting the problems, Mr. B had also known an estimation of each problem’s difficultness. When he was asked to choose a problem, if he chose the easiest one, Mr. G would complain that “Hey, what a trivial problem!”; if he chose the hardest one, Mr. M would grumble that it took too much time to finish it. To address this dilemma, Mr. B decided to take the one with the medium difficulty. Therefore, he needed a way to know the median number in the given interval of the sequence.
Input
For each test case, the first line contains a single integer n (1 <= n <= 100,000) indicating the total number of problems. The second line contains n integers xi (0 <= xi <= 1,000,000,000), separated by single space, denoting the difficultness of each problem, already sorted by publish time. The next line contains a single integer m (1 <= m <= 100,000), specifying number of queries. Then m lines follow, each line contains a pair of integers, A and B (1 <= A <= B <= n), denoting that Mr. B needed to choose a problem between positions A and B (inclusively, positions are counted from 1). It is guaranteed that the number of items between A and B is odd.
Output
For each query, output a single line containing an integer that denotes the difficultness of the problem that Mr. B should choose.
Sample Input
5
5 3 2 4 1
3
1 3
2 4
3 5
5
10 6 4 8 2
3
1 3
2 4
3 5
Sample Output
Case 1:
3
3
2
Case 2:
6
6
4
題意： 輸入n 以及n個數 然後輸入m個區間 問每個區間中的中間大的數是哪個
[cpp]
#include<stdio.h>
#include<algorithm>
using namespace std;
#define M 100005
int tree[20][M],sorted[M];
int toLeft[20][M];
void build(int level,int left,int right){
if(left==right)return ;
int mid=(left+right)>>1;
int i;
int suppose;//假設在中位數sorted[mid]左邊的數都全部小於sorted[mid]
suppose=mid-left+1;
for(i=left;i<=right;i++){
if(tree[level][i]<sorted[mid]){
suppose--;
}
}
//如果suppose==1，則說明數組中值為sorted[mid]只有一個數。比如序列：1 3 4 5 6，sorted[mid]=4
/*如果suppose>1，則說明數組中左半邊值為sorted[mid]的不止一個數,為mid-suppose。比如序列：1 4 4 4 6，sorted[mid]=4
*/
int lpos=left,rpos=mid+1;
for(i=left;i<=right;i++){
if(i==left){//這裡是預處理，相當與初始化
toLeft[level][i]=0;
}else{
toLeft[level][i]=toLeft[level][i-1];
}
if(tree[level][i]<sorted[mid]){//劃分到中位數左邊
toLeft[level][i]++;
tree[level+1][lpos++]=tree[level][i];
}else if(tree[level][i]>sorted[mid]){//劃分到中位數右邊
tree[level+1][rpos++]=tree[level][i];
}else{//這裡，suppose大於0的數劃分到中位數的左邊
if(suppose!=0){//這裡的處理太巧妙了！帥氣！
suppose--;
toLeft[level][i]++;
tree[level+1][lpos++]=tree[level][i];
}else{//表示
tree[level+1][rpos++]=tree[level][i];
}
}
}
build(level+1,left,mid);
build(level+1,mid+1,right);
}
//在[left,right]數據中查詢[qleft,qright]中第k大的數據
int query(int level,int left,int right,int qleft,int qright,int k){
if( qleft==qright)
return tree[level][qleft];
int s;//代表[left,qleft)之間有多個個元素被分到左邊
int ss;//[qleft, qright]內將被劃分到左子樹的元素數目
int mid=(left+right)>>1;
if(left==qleft){
s=0;
ss=toLeft[level][qright];
}else{
s=toLeft[level][qleft-1];
ss=toLeft[level][qright]-s;
}
int newl,newr;
if(k<=ss){//查詢左邊
newl=left+s;
newr=left+s+ss-1;
return query(level+1,left,mid,newl,newr,k);
}else{//查詢右邊
newl=mid-left+1+qleft-s;
newr=mid-left+1+qright-s-ss;
return query(level+1,mid+1,right,newl, newr,k - ss);
}
}
int main(){
int n,m,cas=0;
while(scanf("%d",&n)!=EOF)
{
cas++;
printf("Case %d:\n",cas);
int i;
for(i=1;i<=n;i++){
scanf("%d",&tree[0][i]);
sorted[i]=tree[0][i];
}
sort(sorted+1,sorted+n+1);
build(0,1,n);
scanf("%d",&m);
int ql,qr,k;
for(i=0;i<m;i++){
scanf("%d %d",&ql,&qr);
k=(qr-ql)/2+1;
printf("%d\n",query(0,1,n,ql,qr,k));
}
}
return 0;
}
