Posted on 2011-06-27 20:54
Mato_No1 閱讀(2855)
評論(1) 編輯 收藏 引用 所屬分類:
經典問題的模型 、
其它高級數據結構
首先，Orz一下AHdoc神犇，本沙茶是看他的總結才搞懂劃分樹的。
原文地址劃分樹，就是每個結點代表一個序列，設這個序列的長度為len，若len>1，則序列中前len/2（上取整，這里數學公式不好打，真囧）個元素被分到左子結點，左子結點代表的序列就是這些元素
按照根結點中的順序組成的序列，而剩下的元素被分到右子結點，右子結點代表的序列也就是剩下的元素按照根結點中的順序組成的序列；若len=1，則該結點為葉結點。劃分樹最重要的應用就是找區間第K小（只是查找，不包括修改）。
寫劃分樹時主要有兩個函數：建樹和找區間第K小。由于后者AHdoc神犇已經總結了，所以這里只總結建樹的函數。
設目前結點為[l..r]（l<r，就是目前的結點是原序列不斷劃分后得到[l..r]這一段，其實也就是a0[l..r]打亂順序后得到的，a0為原序列遞增排序后的序列）首先找到中值，就是a0[mid]，mid=l+r>>1。然后可以得到，[l..r]中小于中值的的元素一定被劃分到左子結點，[l..r]中大于中值的元素一定被劃分到右子結點，而[l..r]中等于中值的元素則不確定，有的被劃分到左子結點，有的被劃分到右子結點，這就需要先找到應被劃分到左子結點的等于中值的元素個數sm（從mid開始不斷往左，直到找到邊界處或者找到一個小于中值的元素為止，或者說，sm就是a0[l..mid]中等于中值的元素個數），然后開始劃分，小于中值分到左子結點，大于中值分到右子結點，等于中值的，若目前還沒滿sm則分到左子結點否則分到右子結點。另外中間有兩個值需要記錄（找區間第K小時必須要用到）：sl和sr。sl[i]表示[l..i]中被分到左子結點的元素個數，sr[i]表示[l..i]中被分到右子結點的元素個數（這里l<=i<=r。顯然sl[i]+sr[i]=i-l+1，其實sr[i]可以不用記錄的，這里只是為了在找第K小操作中減少計算次數，起到空間換時間的作用）。
建樹代碼：
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是每層劃分后的序列。
查找區間第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（兩道任選一道）