前奏
當然這裡暫且不表，尚不說劃分樹思想的神奇，就是線段樹的結構，一般沒有ACM基礎的人也都覺得難以了解。是以，這裡提供一個時間效率尚可，空間代價還要略小的巧妙解法—伴随數組。
第一節、尋找給定區間内的第k小（大）的元素
1、排序，快速排序。我們知道，快速排序平均所費時間為n*logn，從小到大排序這n個數，然後再周遊序列中後k個元素輸出，即可，總的時間複雜度為O（n*logn+k）=O（n*logn）。 2、排序，選擇排序。用選擇或交換排序，即周遊n個數，先把最先周遊到得k個數存入大小為k的數組之中，對這k個數，利用選擇或交換排序，找到k個數中的最大數kmax（kmax設為k個元素的數組中最大元素），用時O（k）（你應該知道，插入或選擇排序查找操作需要O（k）的時間），後再繼續周遊後n-k個數，x與kmax比較：如果x<kmax，則x代替kmax，并再次重新找出k個元素的數組中最大元素kmax‘（多謝jiyeyuran 提醒修正）；如果x>kmax，則不更新數組。這樣，每次更新或不更新數組的所用的時間為O（k）或O（0），整趟下來，總的時間複雜度平均下來為：n*O（k）=O（n*k）。 3、維護k個元素的最大堆，原理與上述第2個方案一緻，即用容量為k的最大堆存儲最先周遊到的k個數，并假設它們即是最小的k個數，建堆費時O（k），有k1<k2<...kmax（kmax設為最大堆中的最小元素）。繼續周遊數列，每次周遊一個元素x，與堆頂元素比較，若x<kmax，則更新堆（用時logk），否則不更新堆。這樣下來，總費時O（k+（n-k）*logk）=O（N*logK）。此方法得益于在堆中，查找等各項操作時間複雜度均為logk（不然，就如上述思路2所述：直接用數組也可以找出最大的k個元素，用時O（n*k））。
下面我們給出伴随數組解法，首先，定義一個結構體，一個是數組元素，另一個是數組原來的标号，記錄每個數在數組的原順序。
我們以下面的測試資料舉例（紅體部分表示下标為2~5之間的數5,2,6,3，淺色部分表示數組中的數各自對應的數組下标，淡藍色部分為給定的下标區間，注，這裡，我們讓數組下标從1開始）：
a[i].data 1 5 2 6 3 7 4
a[i].num 1 2 3 4 5 6 7
現在，題目給定了下标區間，如在原序列中下标2~5（即下标為2、3、4、5）區間找到第3小的數。問題亦相當于要你找原序列裡給定下标區間即第2個數到第5個數之中（5 2 6 3）第3小的數（當然，答案很明顯，第3小的數就是5）。
那麼對原數組進行排序，然後得到的序列應該是（注：原下标始終保持不變）：
a [i].data 1 2 3 4 5 6 7
a [i].num 1 3 5 7 2 4 6
如上，既然資料現在已經從小到大排好了，那麼，我們隻需要進行一次檢索，從最小的數到最大的數，我們找第k(k=3)小的數，當我們發現下标a[i].num等于原給定下标區間在2~5中，即a[i].num==2 || 3 || 4 || 5的時候，k--，那麼當k==0的時候，我們也就找到了第k(3)小的數了。如下（紅色部分表示原給定下标區間中的數，淺色部分依然是原各數對應的下标，淡藍色部分為原來給定的下标區間所對應的索引）：
a [i].data 1 2 3 4 5 6 7
a [i].num 1 3 5 7 2 4 6
k 3 2 1 1 0
故下标索引為2~5之間第k（3）小的數是5。
程式的構造與解釋：由于排序後，我們能保證原序列已經從小到大的排好序了，是以，當周遊或掃描到原序列給定下标區間中的數時，則k--，最終能在k==0時，找到第k小的數，且這個數是在原來給定下标區間中的某一個數。
而這個伴随數組，或者說原序列各數的索引則幫我們或者說是幫電腦記下了原來的數，已讓我們後來周遊時能識别排序後序列中的數是否是給定下标區間中的某一個數。如果是原給定下标區間中的數，則k--，否則k不變。
第二節、采用伴随數組方案的實作
上述采用伴随數組的方法巧妙且簡單，也很好了解和實作，關鍵 就是在于題目要求是在給定下标區間中找尋第k小（大）的元素，是以，基本上在排序n*logn完了之後，總能 在O（n）的時間内找到想找的數。源代碼如下：
//copyright@ 水 && July
//總的時間複雜度為O（N*logN+N）=O（N*logN）。
//July、updated，2011.05.28.淩晨。
#include<iostream>
#include<algorithm>
using namespace std;
struct node{
int num,data;
bool operator < (const node &p) const
{
return data < p.data;
}
};
node p[100001];
int main()
{
int n=7;
int i,j,a,b,c;//c：flag;
for(i=1;i<=n;i++)
scanf("%d",&p[i].data);
p[i].num = i;
sort(p+1,p+1+n); //調用庫函數sort完成排序，複雜度n*logn
scanf("%d %d %d",&a,&b,&c);
for(i=1;i<=n;i++) //掃描一遍，複雜度n
if(p[i].num>=a && p[i].num<=b)
c--;
if(c == 0)
break;
printf("%d/n",p[i].data);
return 0;
}
程式測試：輸入的第1行數字1 5 2 6 3 7 4代表給定的數組，第二行的數字中，2 5代表給定的下标區間2~5，3表示要在給定的下标區間2~5中尋找第3小的數，第三行的5表示找到的第3小的數。程式運作結果如下：
水原來寫的代碼（上面我的改造，是為了達到後來掃描時O（N）的視覺效果）： //copyright@ 水 int n,m,i,j,a,b,c;//c：flag; while(scanf("%d %d",&n,&m)!=EOF) for(i=1;i<=n;i++) { scanf("%d",&p[i].data); p[i].num = i; } sort(p+1,p+1+n); for(j=1;j<=m;j++) scanf("%d %d %d",&a,&b,&c); for(i=1;i<=n;i++) { if(p[i].num>=a && p[i].num<=b) c--; if(c == 0) break; } printf("%d/n",p[i].data);
第三節、直接排序給定下标區間的數
你可能會忽略一個重要的事實，不知讀者是否意識到。題目是要求我們在數組中求給定下标區間内某一第k小的數，即我們隻要找到這個第k小的數，就夠了。但上述程式顯示的一個弊端，就是它先對整個數組進行了排序，然後采用伴随數組的解法尋找到第k小的數。而事實是，我們不需要對整個數組進行排序，我們隻需要對我們要尋找的那個數的數組中給定下标區間的數進行部分排序，即可。
對，事情就是這麼簡單。我們摒棄掉伴随數組的方法，隻需要直接對數組中給定的那部分下标區間中的數進行排序，而不是對整個數組進行排序。如此的話，算法的時間複雜度降到了L*logK。其中，L=|b-a+1|，L為給定下标區間的長度，相對整個數組的程度n，L<=n。程式代碼如下。
//copyright@ 蒼狼
//直接對給定區間的數進行排序，沒必要用伴随數組。
#include<iostream>
#include<algorithm>
using namespace std;
struct node{
int data;
bool operator < (const node &p) const
{
return data < p.data;
}
};
node p[100001];
int main()
{
int n=7;
int i,a,b,c;//c：flag;
for(i=1;i<=n;i++)
scanf("%d",&p[i].data);
scanf("%d%d%d", &a, &b, &c); //b，a為原數組的下标索引
sort(p+a, p+b+1); //直接對給定區間進行排序，|b-a+1|*log（b-a+1）
printf("The number is %d/n", p[a-1+c].data);
return 0;
程式測試：我們同樣采取第二節的測試用例。輸入的第1行數字1 5 2 6 3 7 4代表給定的數組，第二行的數字中，2 5代表給定的下标區間2~5，3表示要在給定的下标區間2~5中的數，即從a[2]~a[5]中尋找第3小的數，第三行的5表示找到的第3小的數。程式運作結果如下。
貌似上述直接對給定區間内的數進行排序，效率上較第二節的伴随數組方案更甚一籌。既然如此，那麼伴随數組是不是多此一舉呢?其實不然，@水：假如，我對2-5之間進行了排序，那麼資料就被摧毀了，怎麼進行2次的操作？就是現在的2位置已經不是初始的2位置的資料了。也就是說，快排之後下标直接定位的方法明顯隻能用一次。
ok，更多請看下文第四節中的“百家争鳴”與“經典對白”。
第四節、伴随數組的優勢所在
百家争鳴
@July：不用看我了，基本上同意上述水的觀點。雨翔之是以認為伴随數組不可取，是因為沒有考慮到水提出的問題，即如果要多次或不斷的從數組中不同的下标區間中尋找第k小的數的情況。這時，伴随數組的優勢就展現出來了。ok，讀者還可以繼續看下面的經典對白。相信，你能找到你想要的答案。
經典對白
查找a[0]~a[n-1]内第K小，然後再找a[1]~a[n]内第K小，依次往複，找個幾次就優勢明顯了。其實是比較采取伴随數組解法n log n +m*n的代價（m為給定不同區間的個數）和直接排序m*(L*log L )（L為給定下标區間的長度）的代價，哪個更低。其中，采用伴随數組查找最差情況是nlogn + m（n-1），而直接排序代價，最差情況為m*（（n-1）*log（n-1））。當m>>0且n>>0時，排序時間-伴随時間=m*n*logn-n*logn-mn =（m-1）n*logn -mn恒正，結論：即在需要不斷的從不同給定下标區間中尋找第k小數的情況下，當資料規模大的時候伴随數組效果恒優于每次都直接對給定的下标區間的部分數進行排序。
是的，好比我現在給定不同的另外一個下标區間，要你從中查找第k小的數，你總不能每次都排序吧。而采取伴随數組的方案的話，由于伴随數組記下了各自給定的下标區間對應的數。是以，第二次在不同的下标區間中查找第k小的數時，還是隻要掃描一遍即可找到，複雜度還是 O（N）。進而，給定不同的下标區間查找第k小的數，複雜度為m*N加上之前排序預處理的複雜度，N*logN，總的時間複雜度為O（N*logN+m*N）（m為給定不同區間的個數）。而直接對給定下标區間中的數進行排序的代價則為l1*logl1+l2*logl2+...+li*logli。當m>>0且n>>0時，哪個複雜度誰大誰小，一眼就看出來了伴随數組所展現的巨大優勢。
恩，實際樣例是這樣的，我們有每天超過100萬次點選的網頁，我們常見的來源有n種，然後，我們要确定每天的每個時段和一周乃至整個月的點選來源地分析。資料庫的庫存資料量龐大，copy花銷很大，内排序花銷更大，如果要做出這樣的統計圖，我擦淚，如果每次都排序，玩死了。
原例重制
ok，說了這麼多，你可能還根本就不明白到底是怎麼一回事。讓我們從第一節舉的那個例子說起。我們要找給定下标區間2~5的數中第3小的數，誠然，此時，我們有兩種選擇，1、如上第一節、第二節所述的伴随數組，2、直接對下标區間2-5的數進行排序。下面，隻回顧下伴随數組的方案。
伴随數組
第一次排序後：
伴随數組方案查找：
好的，那麼現在，如果題目要求你在之前數組的下标區間3~6的數中找第3小的數呢（答案很明顯，為6）?
a[i].data 1 5 2 6 3 7 4
a[i].num 1 2 3 4 5 6 7
直接排序麼?ok，退萬一步講，假設有的讀者可能還是會依然選擇直接排序下标3~6之間的數。但你是否可曾想到，每次對不同的下标區間所對應的數進行排序，你不但破壞了原有的資料，而且如果區間有覆寫的話，那麼将使得我們無法再能依靠原有的直接的下标定位找到原來的資料，且每進行一次排序，都要花費平均時間複雜度為N*logN的時間開銷。如上面的經典對白所述，這樣下去的開銷将非常大，将為l1*logl1+l2*logl2+...+li*logli。
那麼，如果是采取伴随數組的方法，我們要怎麼做呢?如下所示，我們在k=0的時候，同樣找到了第3小的數6，如此是不是隻要在之前的一次排序，以後不論是換各種不同的下标區間時都能掃描一遍O（N）搞定?複雜度為O（N*logN+m*N）（m為給定不同的下标區間的區間數）。
由上面的經典對白裡面的内容，我們已經知道，當m>>0且n>>0時（m為給定不同的下标區間的區間數，n為數組大小），排序時間-伴随時間=m*n*logn-n*logn-mn =（m-1）n*logn -mn恒正。yeah，相信，你已經明白了。
原第一次排序後：
再次掃描，直接O（N）搞定：
a [i].data 1 2 3 4 5 6 7
a [i].num 1 3 5 7 2 4 6
k 3 2 1 1 1 0
（而之前有的讀者意識不到伴随數組的意義，是因為一般的人隻考慮找一次，不會想到第二次或多次查找）
程式設計獨白
給你40分鐘的時間，你可以思考十分鐘，然後用三十分鐘的時間來寫代碼，最後浪費在無謂的調試上；你也可以思考半個小時，徹底弄清問題的本質與程式的脈絡，然後用十分鐘的時間來編寫代碼，體會代碼如行雲流水而出的感覺。