代碼測試通過那一刻，我心都碎了。 昨天晚上開始學習劃分樹，花了大概一個小時左右弄清楚了劃分樹的原理（自以為弄清楚了）。然後在網上找了一份代碼對照著學習。我喜歡在學習別人代碼之前先對那些代碼做一些修改，改成我比較習慣的風格。結果不知道是不是我的改動引發了不知名的bug，原代碼測試通過之後測試依然能通過，但是我對照著學習卻是舉步維艱啊！ 在上午我自以為已經掌握劃分樹的情況下，我突然發現我有一個小地方沒有弄清楚，一上午的忙活就白瞎了。下午我又重新找了一份代碼學習，這次比較順利，總算是在晚飯之前把自己寫了一遍測試通過了。 對照著線段樹來描述一下劃分樹吧：線段樹第一層每一層的節點數是不一樣的，每一層最大節點的數量是2^(n-1)，所有葉節點的數量是n。線段樹的這些節點存儲了我們需要查詢的信息。但是劃分樹不同，我們看劃分樹建樹實際上是開了幾個數組而不是聲明一個結構體，存儲信息的數組是一個二維數組。可以這樣理解，劃分樹的每一層都存儲了數組中所有數據的信息。線段樹中的節點存儲的信息是我們希望查詢的由它的兩個子節點的信息加合而來的信息。信息的傳遞是從下往上，劃分樹的信息傳遞則是從上往下。 劃分樹的原理：劃分樹用一個數組（在我的代碼中是數組a）存儲原數組，需要注意的是a數組的每一層都包含了整個原數組的值，只不過是順序不同。劃分樹先對數組進行排序，獲得數組從小到大的一個比較數組（代碼中是b），然後再每一次遞歸中調換數組中值的位置。以中間值b[mid]為標准，比b[mid]小的數字存入mid左邊，比b[mid]大的數值存入右邊，在num[i]中記錄到a[t][i]（t表示當前數組的層數）時，有多少個a[t]（這是個數組）中的值存入了mid的左邊，有多少個值存入了右邊。建樹的操作非常簡單，麻煩的是查詢。 查詢的時候需要的是查詢區間所在的大區間（這個大區間就是線段樹中的子樹存的區間，這個區間更新的方式和線段樹完全一樣），需要查詢的區間，查詢區間的第k值，以及當前查詢操作在劃分樹的第t層。查詢的時候，首先是看查詢區間內有多少值在下一層中被分到了左邊，如果這個值比需要查詢的k值大，說明我們希望得到的查詢結果被分配到了左邊的區間，如果比k值小，說明結果被分配在了右邊。確定了查詢結果在哪個區間，然後就是更新在下一層中，在我們查詢得到的大區間內，小區間的邊界的值。好像說得特別拗口，對照著代碼理解吧。同樣的操作逐層查詢，一直查詢到x和y值相等，鎖定我們想要的結果然後返回輸出。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 100005
int a[31][N],b[N],num[31][N];
int cmp(const void *a,const void *b)
{
return *(int *)a-*(int *)b;
}
void CreatTree(int x,int y,int t)
{
if(x==y)
return ;
int mid=(x+y)/2;
int i;
int lp=x;
int rp=mid+1;
for(i=x;i<=y;i++)
{
num[t][i]=num[t][i-1];
if(lp<=mid&&a[t][i]<=b[mid])
{
num[t][i]++;
a[t+1][lp++]=a[t][i];
}
else
a[t+1][rp++]=a[t][i];
}
CreatTree(x,mid,t+1);
CreatTree(mid+1,y,t+1);
return ;
}
int FindTree(int x,int y,int k,int l,int r,int t)
{
if(x==y)
return a[t][x];
int mid=(l+r)/2;
int s1,t1;
s1=num[t][x-1]-num[t][l-1];
t1=num[t][y]-num[t][x-1];
if(t1>=k)
return FindTree(l+s1,l+s1+t1-1,k,l,mid,t+1);
int s2,t2;
s2=x-l-s1;
t2=y-x+1-t1;
return FindTree(mid+1+s2,mid+s2+t2,k-t1,mid+1,r,t+1);
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
int i;
for(i=1;i<=n;i++)
{
scanf("%d",&a[0][i]);
b[i]=a[0][i];
}
qsort(b+1,n,sizeof(b[0]),cmp);
CreatTree(1,n,0);
while(m--)
{
int x,y,k;
scanf("%d%d%d",&x,&y,&k);
printf("%d\n",FindTree(x,y,k,1,n,0));
}
}
return 0;
}
