最近學習了一下劃分樹，下面總結一下。
我們在求區間最值的時候，一般可以用線段樹解決，但是如果要求區間第k小或者第k大值的話線段樹就有點力不從心了，這是我們可以用劃分樹來解決。劃分樹利用了快速排序的思想，首先是建樹，我們設當前區間的中位數為mid，(為了能快速找到區間的中位數，我們一般先對原序列做一次排序)則我們將區間中比mid小的放入左子樹，將區間中比mid大數的放入右子樹中，和mid相等的要討論一下，有些需要放到左子樹中，其他的放到右子樹中，注意我們將數字放入子樹的時候其相對順序是不變的。這樣我們一層一層下去，每次區間都減半，則空間消耗為O（nlogn）。下面看一個例子。
假設序列長度為9，依次為 3 5 7 3 4 9 4 2 5，怎我們看看建樹完成後是什麼樣子。
sort[ ][2 3 3 4 4 5 5 7 9]
tree[0][3 5 7 3 4 9 4 2 5]
tree[1][3 3 4 4 2][5 7 9 5]
tree[2][3 3 2][4 4][5 5][7 9]
tree[3][3 2][3][4][4][5][5][7][9]
tree[4][2][3][3][4][4][5][5][7][9]
好了，樹建完了，接下來就是最關鍵的查詢了，我們設函數query（p,l,r,s,t,k）表示在第p層子樹區間范圍在[l,r]的子樹中查找區間[s,t]中的第k小值。我們在每一顆子樹中設sum[i]表示區間[l,i]范圍內有多少個數字被放到了左子樹中，那麼我們容易得到，sum[t]-sum[s-1]表示在區間[s,t]有多少個樹被放入了左子樹中，我們不妨設這個值為num，若k<=num，我們就可以知道我們要找的數一定在左子樹中，否則一定在右子樹中，我們接下來只要繼續往下遍歷，當l==r的時候我們就可以確定我們要找的數，容易知道這一步驟的復雜度為O(log n)，現在關鍵的一點就是如何再往下便利的時候確定ls,t的值。這個其實自己畫畫圖就很容易推出來的，下面只寫結論，這裡先設區間[l,s-1]中被放入左子樹的數有snum個,當前區間的中點為mid，
則若k<=num,我們返回query(p+1,l,mid,l+snum,l+sum[t]-1,k),(要找的數在左子樹上)
否則，我們返回query(p+1,mid+1,r,mid+1-l+s-snum,mid+1-l+t-sum[t],k-num);（要找的數在右子樹上）
下面再舉個例子，數和上面一樣
我們現在要找到區間[2,7]中的第3小數。
sort[ ][2 3 3 4 4 5 5 7 9]
tree[0][3 5 7 3 4 9 4 2 5]
tree[1][3 3 4 4 2][5 7 9 5]
tree[2][3 3 2][4 4][5 5][7 9]
tree[3][3 2][3][4][4][5][5][7][9]
tree[4][2][3][3][4][4][5][5][7][9]
以上橙黃色背景的數字即為我們要求的范圍。
我們首先在第一層樹上尋找，即query(0,1,9,2,7,3),我們發現在[2,7]區間中有3個數被放入了左子樹，滿足k<=num，所以我們往左子樹中找，調用query(1,1,5,2,4,3)。
在第二層樹中我們發現區間[2,4]只有一個數被放入左子樹，所以我們要找的數一定在右子樹中，調用query(2,4,5,4,5,2)。
在第三層樹中，我們發現區間[4,5]只有一個數被放入左子樹，同理我們應該往右子樹找，調用query(3,5,5,5,5,1)。現在可以發現l==r，則我們可以確定已經找到了要找的數，則返回4即可，我們可知在區間[2,7]上第3小的數為4。
基礎的劃分樹就到這裡，下面給出我的代碼：
[cpp]
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#define maxn 100010
#define mid ((l+r)>>1)
using namespace std;
int t[20][maxn],sum[20][maxn];
int a[maxn],as[maxn];
//以下為查找區間第k小劃分樹
void build(int p,int l,int r)
{
int lm=0,i,ls=l,rs=mid+1;//lm表示應被放入左子樹且與中位數相等的數有多少個，ls為左子樹的起始位置，rs為右子樹的起始位置
for(i=mid;i>=l;i--) //求lm
{
if(as[i]==as[mid])
lm++;
else
break;
}
for(i=l;i<=r;i++)
{
if(i==l)//這裡要特殊討論
sum[p][i]=0;
else
sum[p][i]=sum[p][i-1];
if(t[p][i]==as[mid])//若與中位數相等則判斷是否應該被放入左子樹
{
if(lm)
{
lm--;
sum[p][i]++;
t[p+1][ls++]=t[p][i];
}
else
t[p+1][rs++]=t[p][i];
}
else if(t[p][i]<as[mid])//查找區間第K大即為>
{
sum[p][i]++;
t[p+1][ls++]=t[p][i];
}
else
t[p+1][rs++]=t[p][i];
}
if(l==r)
return;
build(p+1,l,mid);
build(p+1,mid+1,r);
}
int query(int p,int l,int r,int ql,int qr,int k)
{
int s,ss;//s表示l到ql-1的區間內放入左子樹的個數，ss表示區間[ql,qr]被放入左子樹的個數
if(l==r)//找到所求的數
return t[p][l];
if(ql==l)
s=0,ss=sum[p][qr];
else
s=sum[p][ql-1],ss=sum[p][qr]-s;
if(k<=ss)//要找的數在左子樹中
return query(p+1,l,mid,l+s,l+sum[p][qr]-1,k);
else//要找的數在右子樹中
return query(p+1,mid+1,r,mid+1-l+ql-s,mid+1-l+qr-sum[p][qr],k-ss);
}
