跳转至

劃分樹

引入

劃分樹是一種來解決區間第 \(K\) 大的一種數據結構，其常數、理解難度都要比主席樹低很多。同時，劃分樹緊貼「第 \(K\) 大」，所以是一種基於排序的一種數據結構。

建議先學完 主席樹 再看劃分樹哦

過程

建樹

劃分樹的建樹比較簡單，但是相對於其他樹來説比較複雜。

如圖，每一層都有一個看似無序的數組。其實，每一個被紅色標記的數字都是 要分配到左兒子的。而分配的規則是什麼？就是與 這一層的中位數 做比較，如果小於等於中位數，則分到左邊，否則分到右邊。但是這裏要注意一下：並不是嚴格的 小於等於就分到左邊，否則分到右邊。因為中位數可能有相同，而且與 \(N\) 的奇偶有一定關係。下面的代碼展示會有一個巧妙的運用，大家可以參照代碼。

我們不可能每一次都對每一層排序，這樣子不説常數，就算是理論複雜度也過不去。我們想，找中位數，一次排序就夠了。為什麼？比如，我們求 \(l,r\) 的中位數，其實就是在排完序過後的 num[mid]。

兩個關鍵數組：

tree[log(N),N]: 也就是樹，要存下所有的值，空間複雜度 \(O(n\log n)\)。 toleft[log(N),n]: 也就是每一層 1~i 進入左兒子的數量，這裏需要理解一下，這是一個前綴和。

實現 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
procedure Build(left,right,deep:longint); // left,right 表示區間左右端點,deep是第幾層
var
  i,mid,same,ls,rs,flag:longint; // 其中 flag 是用來平衡左右兩邊的數量的
begin
  if left=right then exit; // 到底層了
  mid:=(left+right) >> 1;
  same:=mid-left+1;
  for i:=left to right do 
    if tree[deep,i]<num[mid] then
      dec(same);

  ls:=left; // 分配到左兒子的第一個指針
  rs:=mid+1; // 分配到右兒子的第一個指針
  for i:=left to right do
  begin
    flag:=0;
    if (tree[deep,i]<num[mid])or((tree[deep,i]=num[mid])and(same>0)) then // 分配到左邊的條件
    begin
      flag:=1; tree[deep+1,ls]:=tree[deep,i]; inc(ls);
      if tree[deep,i]=num[mid] then // 平衡左右個數
        dec(same);
    end
    else
    begin
      tree[deep+1,rs]:=tree[deep,i]; inc(rs);
    end;
    toleft[deep,i]:=toleft[deep,i-1]+flag;
  end;
  Build(left,mid,deep+1); // 繼續
  Build(mid+1,right,deep+1);
end;

查詢

那我們先扯一下主席樹的內容。在用主席樹求區間第 \(K\) 小的時候，我們以 \(K\) 為基準，向左就向左，向右要減去向左的值，在劃分樹中也是這樣子的。

查詢難理解的，在於 區間縮小 這種東西。下圖，查詢的是 \(3\) 到 \(7\), 那麼下一層就只需要查詢 \(2\) 到 \(3\) 了。當然，我們定義 \([\text{left},\text{right}]\) 為縮小後的區間（目標區間），\([l,r]\) 還是所在節點的區間。那為什麼要標出目標區間呢？因為那是 判定答案在左邊還是右邊的基準。

實現 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
function Query(left,right,k,l,r,deep:longint):longint;
var
  mid,x,y,cnt,rx,ry:longint;
begin
  if left=right then // 寫成 l=r 也無妨,因為目標區間也一定有答案
    exit(tree[deep,left]);
  mid:=(l+r) >> 1;
  x:=toleft[deep,left-1]-toleft[deep,l-1]; // l 到 left 的去左兒子的個數
  y:=toleft[deep,right]-toleft[deep,l-1]; // l 到 right 的去左兒子的個數
  ry:=right-l-y; rx:=left-l-x; // ry 是 l 到 right 去右兒子的個數,rx 則是 l 到 left 去右兒子的個數
  cnt:=y-x; // left 到 right 左兒子的個數
  if cnt>=k then // 主席樹常識啦
    Query:=Query(l+x,l+y-1,k,l,mid,deep+1) // l+x 就是縮小左邊界,l+y-1 就是縮小右區間。對於上圖來説,就是把節點 1 和 2 放棄了。
  else
    Query:=Query(mid+rx+1,mid+ry+1,k-cnt,mid+1,r,deep+1); // 同樣是縮小區間,只不過變成了右邊而已。注意要將 k 減去 cnt。
end;

性質

時間複雜度 : 一次查詢只需要 \(O(\log n)\)，\(m\) 次詢問，就是 \(O(m\log n)\)。

空間複雜度 : 只需要存儲 \(O(n\log n)\) 個數字。

親測結果：主席樹 :\(1482 \text{ms}\)、劃分樹 :\(889 \text{ms}\)。（非遞歸，常數比較小）

劃分樹的應用

例題：Luogu P3157[CQOI2011] 動態逆序對

題意簡述：給定一個 \(n\) 個元素的排列（\(n\leq 10^5\)），有 m 次詢問（\(m\leq 5\times 10^4\)），每次刪去排列中的一個數，求刪去這個數之後排列的逆序對個數。

這題可以使用 CDQ 在 \(\Theta(n\log^2n)\) 的時間及 \(\Theta(n)\) 的空間內解決，並且 CDQ 的常數也很優秀。

如果這道題改為強制在線，則一般使用樹狀數組 + 主席樹的樹套樹解法解決，時間複雜度為 \(\Theta(n\log^2n)\)，空間複雜度為 \(\Theta(n\log^2n)\)，常數略大，同樣可以過此題。

而使用劃分樹的話就可以在 \(\Theta(n\log^2n)\) 的時間及 \(\Theta(n\log n)\) 的空間內在線解決本題，同時常數也比樹套樹解法少很多。（大致與 CDQ 相當。）

注意：為了編程實現方便，本文依照位置的中間值將大數組劃分為兩個小數組，即下文中的劃分樹相當於是歸併排序的過程，而非快速排序的過程。最頂層的大數組為有序數組，最底層為原數組。

對於每一個劃分樹中的節點，我們稱他為右節點當且僅當他在下一層會被劃分到右孩子，即原數組中位置比較靠後的那些數，相似的可以定義左節點。如果在建樹的過程中將最頂層排為有序的，類似於歸併排序求逆序對，可以發現一個數組的逆序對個數就是在每個左節點之前的右節點的個樹和。

再考慮刪除操作。刪除一個左節點會將整個數組的逆序對減少在他之前右結點的個數，而刪除一個右節點會減少在他之後的左節點個數。那麼可以考慮每次動態維護「每一個左節點之前的右結點個數」和「每一個右節點之後的左節點個數」。這可以使用樹狀數組簡單維護。

需要注意的是，在使用樹狀數組維護時只能計算在劃分樹中同一塊內的貢獻，而不能跳出塊。對於樹狀數組來説有一個較為巧妙的處理方式。

考慮劃分樹上每一塊的下標範圍肯定為 \([c\times 2^k+1,(c+1)\times 2^k]\) 的形式，列舉如下（由於代碼中不會涉及到劃分樹最底層的處理，因此只枚舉到倒數第二層）：

1
2
3
4
[0001 0010] [0011 0100] [0101 0110] [0111 1000] [1001 1010] [1011 1100] [1101 1110] [1111 10000]  lev=1
[0001 0010 0011 0100]   [0101 0110 0111 1000]   [1001 1010 1011 1100]   [1101 1110 1111 10000]    lev=2
[0001 0010 0011 0100 0101 0110 0111 1000]       [1001 1010 1011 1100 1101 1110 1111 10000]        lev=3
[0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 10000]                lev=4

回憶一下樹狀數組的原理，在向上跳的時候，我們每次 x += lowbit(x)。如果在向上跳的時候可以保證不跳出塊，就可以保證只會影響到塊內元素的值。向上查詢也類似。

而如果要在向上跳的同時保證不跳出塊，只需要保證在跳的時候滿足 \(lowbit(x)<2^{lev}\) 即可。

而向下跳則是完全不同的處理方式。每一塊的下標如果使用 0-index 表示的話，即為 \([c\times 2^k,(c+1)\times 2^k)\) 的形式。那麼，只需將某一個下標的值右位移 k，即可得出它在哪一塊中。在向下跳的時候時刻判斷是否跳出塊即可。

需要注意的是，按這一方法實現的樹狀數組會訪問到的最大下標是距離 n 最近的 2 的整次冪，因此數組下標不能開 n。

由於需要在 \(\log n\) 層修改，在第 \(k\) 層修改的時間複雜度為 \(\Theta(k)\)，最終時間複雜度即為 \(\Theta(n\log n+m\log^2n)\)。

附代碼：

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long lld;

int getint()  // 本题没有负数输入，因此快读不需判断负号。
{
  char ch;
  while ((ch = getchar()) < '!')
    ;
  int x = ch ^ '0';
  while ((ch = getchar()) > '!') x = (x * 10) + (ch ^ '0');
  return x;
}

void putll(lld x) {  // 输出long long
  if (x / 10) putll(x / 10);
  putchar((x % 10) ^ '0');
}

int ti[2][17][131073];

int lowbit(int x) { return x & (-x); }

void fixup(int k, int x) {
  for (; lowbit(x) < 1 << k; x += lowbit(x)) {
    ++ti[0][k - 1][x];
  }
  ++ti[0][k - 1][x];
}

void fixdown(int k, int x) {
  for (; ((x ^ lowbit(x)) - 1) >> k == (x - 1) >> k; x ^= lowbit(x)) {
    ++ti[1][k - 1][x];
  }
  ++ti[1][k - 1][x];
}

int queryup(int k, int x) {
  int res = 0;
  for (; lowbit(x) < 1 << k; x += lowbit(x)) {
    res += ti[1][k - 1][x];
  }
  return res + ti[1][k - 1][x];
}

int querydown(int k, int x) {
  int res = 0;
  for (; ((x ^ lowbit(x)) - 1) >> k == (x - 1) >> k; x ^= lowbit(x)) {
    res += ti[0][k - 1][x];
  }
  return res + ti[0][k - 1][x];
}

int ai[100005];
int tx[100005];

lld mgx(int* npi, int* nai, int* rxi, int* lxi, int al, int ar, int bl,
        int br) {
  int rx = 1;
  int lx = ar - al;
  lld res = 0;
  for (; al != ar || bl != br; ++npi, ++nai, ++rxi, ++lxi) {
    if (al != ar && (bl == br || tx[al] < tx[bl])) {
      --lx;
      *rxi = rx;
      *nai = tx[al];
      *npi = al;
      ++al;
    } else {
      ++rx;
      *lxi = lx;
      res += ar - al;
      *nai = tx[bl];
      *npi = bl;
      ++bl;
    }
  }
  return res;
}

int npi[1700005];
int nri[1700005];
int nli[1700005];

int main() {
  const int n = getint();
  const int m = getint();
  for (int i = 1; i <= n; ++i) {
    ai[i] = getint();
  }

  if (n == 1) {
    for (int i = 1; i <= m; ++i) {
      putchar('0');
      putchar('\n');
    }
    return 0;
  }

  const int logn = 31 - __builtin_clz(n - 1);

  lld ans = 0;
  for (int i = logn; i >= 0; --i) {
    memcpy(tx, ai, (n + 1) * sizeof(int));
    for (int j = 1; j <= n; j += 1 << (logn - i + 1)) {
      ans += mgx(npi + n * i + j, ai + j, nri + n * i + j, nli + n * i + j, j,
                 min(n + 1, j + (1 << (logn - i))),
                 min(n + 1, j + (1 << (logn - i))),
                 min(n + 1, j + (1 << (logn - i + 1))));
    }
  }

  putll(ans);
  putchar('\n');

  for (int asdf = 1; asdf < m; ++asdf) {
    int x = getint();
    for (int i = 0, p = 0; i <= logn; ++i, p += n) {
      if (nri[p + x]) {
        ans -= nri[p + x] - querydown(logn - i + 1, x) - 1;
        fixdown(logn - i + 1, x);
      } else {
        ans -= nli[p + x] - queryup(logn - i + 1, x);
        fixup(logn - i + 1, x);
      }
      x = npi[p + x];
    }
    putll(ans);
    putchar('\n');
  }
}

後記

參考博文 :傳送門。

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：Xarfa
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用