首先，Orz一下AHdoc神犇，本沙茶是看他的總結(jié)才搞懂劃分樹的。
原文地址劃分樹，就是每個結(jié)點(diǎn)代表一個序列，設(shè)這個序列的長度為len，若len>1，則序列中前l(fā)en/2（上取整，這里數(shù)學(xué)公式不好打，真囧）個元素被分到左子結(jié)點(diǎn)，左子結(jié)點(diǎn)代表的序列就是這些元素
按照根結(jié)點(diǎn)中的順序組成的序列，而剩下的元素被分到右子結(jié)點(diǎn)，右子結(jié)點(diǎn)代表的序列也就是剩下的元素按照根結(jié)點(diǎn)中的順序組成的序列；若len=1，則該結(jié)點(diǎn)為葉結(jié)點(diǎn)。劃分樹最重要的應(yīng)用就是找區(qū)間第K小（只是查找，不包括修改）。
寫劃分樹時主要有兩個函數(shù)：建樹和找區(qū)間第K小。由于后者AHdoc神犇已經(jīng)總結(jié)了，所以這里只總結(jié)建樹的函數(shù)。
設(shè)目前結(jié)點(diǎn)為[l..r]（l<r，就是目前的結(jié)點(diǎn)是原序列不斷劃分后得到[l..r]這一段，其實(shí)也就是a0[l..r]打亂順序后得到的，a0為原序列遞增排序后的序列）首先找到中值，就是a0[mid]，mid=l+r>>1。然后可以得到，[l..r]中小于中值的的元素一定被劃分到左子結(jié)點(diǎn)，[l..r]中大于中值的元素一定被劃分到右子結(jié)點(diǎn)，而[l..r]中等于中值的元素則不確定，有的被劃分到左子結(jié)點(diǎn)，有的被劃分到右子結(jié)點(diǎn)，這就需要先找到應(yīng)被劃分到左子結(jié)點(diǎn)的等于中值的元素個數(shù)sm（從mid開始不斷往左，直到找到邊界處或者找到一個小于中值的元素為止，或者說，sm就是a0[l..mid]中等于中值的元素個數(shù)），然后開始劃分，小于中值分到左子結(jié)點(diǎn)，大于中值分到右子結(jié)點(diǎn)，等于中值的，若目前還沒滿sm則分到左子結(jié)點(diǎn)否則分到右子結(jié)點(diǎn)。另外中間有兩個值需要記錄（找區(qū)間第K小時必須要用到）：sl和sr。sl[i]表示[l..i]中被分到左子結(jié)點(diǎn)的元素個數(shù)，sr[i]表示[l..i]中被分到右子結(jié)點(diǎn)的元素個數(shù)（這里l<=i<=r。顯然sl[i]+sr[i]=i-l+1，其實(shí)sr[i]可以不用記錄的，這里只是為了在找第K小操作中減少計(jì)算次數(shù)，起到空間換時間的作用）。
建樹代碼：
int mkt(int l, int r, int d)
{
T[++No].l = l; T[No].r = r; int mid = l + r >> 1; T[No].mid = mid;
if (l == r) return No;
int midv = a0[mid], sm = mid - l + 1; rre2(i, mid, l) if (a0[i] < midv) {sm = mid - i; break;}
int x = l, y = mid + 1;
if (a[d][l] < midv) {
a[d + 1][x++] = a[d][l]; sl[d][l] = 1; sr[d][l] = 0;
} else if (a[d][l] == midv && sm) {
a[d + 1][x++] = a[d][l]; sl[d][l] = 1; sr[d][l] = 0; sm--;
} else {
a[d + 1][y++] = a[d][l]; sl[d][l] = 0; sr[d][l] = 1;
}
re3(i, l+1, r) {
if (a[d][i] < midv) {
a[d + 1][x++] = a[d][i]; sl[d][i] = sl[d][i - 1] + 1; sr[d][i] = sr[d][i - 1];
} else if (a[d][i] == midv && sm) {
a[d + 1][x++] = a[d][i]; sl[d][i] = sl[d][i - 1] + 1; sr[d][i] = sr[d][i - 1]; sm--;
} else {
a[d + 1][y++] = a[d][i]; sl[d][i] = sl[d][i - 1]; sr[d][i] = sr[d][i - 1] + 1;
}
}
int No0 = No; T[No0].lch = mkt(l, mid, d + 1); T[No0].rch = mkt(mid + 1, r, d + 1); return No0;
}
這里a是每層劃分后的序列。
查找區(qū)間第K小的代碼：
int Find_Kth(int l, int r, int K)
{
int i = root, d = 0, l0, r0, mid0, s0, s1;
while (1) {
l0 = T[i].l, r0 = T[i].r; mid0 = T[i].mid;
if (l0 == r0) return a[d][l];
if (l == l0) s0 = l; else s0 = l0 + sl[d][l - 1]; s1 = l0 + sl[d][r] - 1;
if (K <= s1 - s0 + 1) {
i = T[i].lch; l = s0; r = s1; d++;
} else {
K -= (s1 - s0 + 1); if (l == l0) l = mid0 + 1; else l = mid0 + sr[d][l - 1] + 1;
r = mid0 + sr[d][r]; i = T[i].rch; d++;
}
}
}
【具體題目】
PKU2104、
PKU2761（兩道任選一道）