跳转至

分塊套樹狀數組

簡介

分塊套樹狀數組在特定條件下可以用來做一些樹套樹可以做的事情，但是相比起樹套樹，分塊套樹狀數組代碼編寫更加簡短，更加容易實現。

簡單的例子

一個簡單的例子就是二維平面中矩陣區域內點數的查詢。

矩形區域查詢

給出 \(n\) 個二維平面中的點 \((x_i, y_i)\)，其中 \(1 \le i \le n, 1 \le x_i, y_i \le n, 1 \le n \le 10^5\), 要求實現以下中操作：

  1. 給出 \(a, b, c, d\)，詢問以 \((a, b)\) 為左上角，\(c, d\) 為右下角的矩形區域內點的個數。
  2. 給出 \(x, y\)，將橫座標為 \(x\) 的點的縱座標改為 \(y\)。

題目 強制在線，保證 \(x_i \ne x_j(1 \le i, j \le n, i \ne j)\)。

對於操作 1，可以通過矩形容斥將其轉化為 4 個二維偏序的查詢去解決，然後因為強制在線，CDQ 分治之類的離線算法就解決不了，於是想到了樹套樹，比如樹狀數組套 Treap。這確實可以解決這個問題，但是代碼太長了，也不是特別好實現。

注意到，題目還額外保證了 \(x_i \ne x_j(1 \le i, j \le n, i \ne j)\)，這個時候就可以用分塊套樹狀數組解決。

初始化

首先，一個 \(x\) 只對應一個 \(y\)，所以可以用一個數組記錄這個映射關係，比如令 \(Y_i\) 表示橫座標為 \(i\) 的點的縱座標。

然後，以 \(\sqrt n\) 為塊大小對橫座標進行分塊。為每個塊建一棵權值樹狀數組。記 \(T_i\) 為第 \(i\) 個塊對應的樹狀數組，\(T_{i, j}\) 表示塊 \(i\) 裏縱座標在 \((j - lowbit(j), j]\) 內的點的個數。

查詢

對於操作 1，將其轉化為 4 個二維偏序的查詢。現在只需要解決給出 \(a, b\)，詢問有多少個點滿足 \(1 \le x_i \le a, 1\le y_i \le b\)。

現在要查詢橫座標的範圍為 \([1, a]\)。因為查詢範圍最右邊可能有一段不是完整的塊，所以暴力掃一遍這個段，看是否滿足 \(Y_i \le b\)，統計出這個段滿足要求的點的個數。

現在就只需要處理完整的塊。暴力掃一遍前面的塊，查詢每個塊對應的樹狀數組中值小於 \(b\) 的個數，累加到答案上。

這就完事了？不，注意到處理完整的塊的時候，其實相當於查詢 \(T\) 的前綴和，如果修改時也使用樹狀數組的技巧處理 \(T\)，那麼查詢時複雜度會更低。

修改

普通的做法就先找到點 \(x\) 所在的塊，然後一減一加兩個權值樹狀數組單點修改，再將 \(Y_x\) 置為 \(y\)。

如果用了上面説的優化，那就是對 \(T\) 也走一個樹狀數組修改的流程，每次修改也是一減一加兩個權值樹狀數組單點修改。

對上述步驟進行一定的改變，比如將一減一加改成只減，就是刪點；改成只加，就是加點。但是必須要注意一個 \(x\) 只能對應一個 \(y\)。

空間複雜度

分塊分了 \(\sqrt n\) 個塊，每個塊一顆線段樹 \(O (n)\) 的空間，所以空間複雜度為 \(O(n \sqrt n)\)。

時間複雜度

查詢的話，遍歷非完整塊的段 \(O(\sqrt n)\)。然後，對 \(T\) 走樹狀數組查詢，每個經歷到的 \(T_i\) 也走樹狀數組查詢，這一步是 \(O(\log (\sqrt n) \log n)\) 的複雜度。所以查詢的時間複雜度為 \(O (\sqrt n + \log (\sqrt n) \log n)\)。

修改和查詢一樣，複雜度為 \(O (\sqrt n + \log (\sqrt n) \log n)\)。

例題 1

Intersection of Permutations

給出兩個排列 \(a\) 和 \(b\)，要求實現以下兩種操作：

  1. 給出 \(l_a, r_a, l_b, r_b\)，要求查詢既出現在 \(a[l_a ... r_a]\) 又出現在 \(b[l_b ... r_b]\) 中的元素的個數。
  2. 給出 \(x, y\)，\(swap(b_x, b_y)\)。

序列長度 \(n\) 滿足 \(2 \le n \le 2 \cdot 10^5\)，操作個數 \(q\) 滿足 \(1 \le q \le 2 \cdot 10^5\)。

對於每個值 \(i\)，記 \(x_i\) 是它在排列 \(b\) 中的下標，\(y_i\) 是它在排列 \(a\) 中的下標。這樣，操作一就變成了一個矩形區域內點的個數的詢問，操作 2 可以看成兩個修改操作。而且因為是排列，所以滿足一個 \(x\) 對應一個 \(y\)，所以這題可以用分塊套樹狀數組來寫。

參考代碼（分塊套樹狀數組 - 1s） 
 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
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
const int M = sqrt(N) + 5;

int n, m, pa[N], pb[N];

int nn, block_size, block_cnt, block_id[N], L[N], R[N], T[M][N];

void build(int n) {
  nn = n;
  block_size = sqrt(nn);
  block_cnt = nn / block_size;
  for (int i = 1; i <= block_cnt; ++i) {
    L[i] = R[i - 1] + 1;
    R[i] = i * block_size;
  }
  if (R[block_cnt] < nn) {
    ++block_cnt;
    L[block_cnt] = R[block_cnt - 1] + 1;
    R[block_cnt] = nn;
  }
  for (int j = 1; j <= block_cnt; ++j)
    for (int i = L[j]; i <= R[j]; ++i) block_id[i] = j;
}

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

void add(int p, int v, int d) {
  for (int i = block_id[p]; i <= block_cnt; i += lb(i))
    for (int j = v; j <= nn; j += lb(j)) T[i][j] += d;
}

int getsum(int p, int v) {
  if (!p) return 0;
  int res = 0;
  int id = block_id[p];
  for (int i = L[id]; i <= p; ++i)
    if (pb[i] <= v) ++res;
  for (int i = id - 1; i; i -= lb(i))
    for (int j = v; j; j -= lb(j)) res += T[i][j];
  return res;
}

void update(int x, int y) {
  add(x, pb[x], -1);
  add(y, pb[y], -1);
  swap(pb[x], pb[y]);
  add(x, pb[x], 1);
  add(y, pb[y], 1);
}

int query(int la, int ra, int lb, int rb) {
  int res = getsum(rb, ra) - getsum(rb, la - 1) - getsum(lb - 1, ra) +
            getsum(lb - 1, la - 1);
  return res;
}

int main() {
  scanf("%d %d", &n, &m);
  int v;
  for (int i = 1; i <= n; ++i) scanf("%d", &v), pa[v] = i;
  for (int i = 1; i <= n; ++i) scanf("%d", &v), pb[i] = pa[v];

  build(n);
  for (int i = 1; i <= n; ++i) add(i, pb[i], 1);

  int op, la, lb, ra, rb, x, y;
  for (int i = 1; i <= m; ++i) {
    scanf("%d", &op);
    if (op == 1) {
      scanf("%d %d %d %d", &la, &ra, &lb, &rb);
      printf("%d\n", query(la, ra, lb, rb));
    } else if (op == 2) {
      scanf("%d %d", &x, &y);
      update(x, y);
    }
  }
  return 0;
}
參考代碼（樹狀數組套 Treap—TLE） 
  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
134
135
136
137
138
139
140
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, m, pa[N], pb[N];

// Treap
struct Treap {
  struct node {
    node *l, *r;
    int sz, rnd, v;

    node(int _v) : l(NULL), r(NULL), sz(1), rnd(rng()), v(_v) {}
  };

  int get_size(node*& p) { return p ? p->sz : 0; }

  void push_up(node*& p) {
    if (!p) return;
    p->sz = get_size(p->l) + get_size(p->r) + 1;
  }

  node* root;

  node* merge(node* a, node* b) {
    if (!a) return b;
    if (!b) return a;
    if (a->rnd < b->rnd) {
      a->r = merge(a->r, b);
      push_up(a);
      return a;
    } else {
      b->l = merge(a, b->l);
      push_up(b);
      return b;
    }
  }

  void split_val(node* p, const int& k, node*& a, node*& b) {
    if (!p)
      a = b = NULL;
    else {
      if (p->v <= k) {
        a = p;
        split_val(p->r, k, a->r, b);
        push_up(a);
      } else {
        b = p;
        split_val(p->l, k, a, b->l);
        push_up(b);
      }
    }
  }

  void split_size(node* p, int k, node*& a, node*& b) {
    if (!p)
      a = b = NULL;
    else {
      if (get_size(p->l) <= k) {
        a = p;
        split_size(p->r, k - get_size(p->l), a->r, b);
        push_up(a);
      } else {
        b = p;
        split_size(p->l, k, a, b->l);
        push_up(b);
      }
    }
  }

  void ins(int val) {
    node *a, *b;
    split_val(root, val, a, b);
    a = merge(a, new node(val));
    root = merge(a, b);
  }

  void del(int val) {
    node *a, *b, *c, *d;
    split_val(root, val, a, b);
    split_val(a, val - 1, c, d);
    delete d;
    root = merge(c, b);
  }

  int qry(int val) {
    node *a, *b;
    split_val(root, val, a, b);
    int res = get_size(a);
    root = merge(a, b);
    return res;
  }

  int qry(int l, int r) { return qry(r) - qry(l - 1); }
};

// Fenwick Tree
Treap T[N];

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

void ins(int x, int v) {
  for (; x <= n; x += lb(x)) T[x].ins(v);
}

void del(int x, int v) {
  for (; x <= n; x += lb(x)) T[x].del(v);
}

int qry(int x, int mi, int ma) {
  int res = 0;
  for (; x; x -= lb(x)) res += T[x].qry(mi, ma);
  return res;
}

int main() {
  scanf("%d %d", &n, &m);
  int v;
  for (int i = 1; i <= n; ++i) scanf("%d", &v), pa[v] = i;
  for (int i = 1; i <= n; ++i) scanf("%d", &v), pb[i] = pa[v];
  for (int i = 1; i <= n; ++i) ins(i, pb[i]);

  int op, la, lb, ra, rb, x, y;
  for (int i = 1; i <= m; ++i) {
    scanf("%d", &op);
    if (op == 1) {
      scanf("%d %d %d %d", &la, &ra, &lb, &rb);
      printf("%d\n", qry(rb, la, ra) - qry(lb - 1, la, ra));
    } else if (op == 2) {
      scanf("%d %d", &x, &y);
      del(x, pb[x]);
      del(y, pb[y]);
      swap(pb[x], pb[y]);
      ins(x, pb[x]);
      ins(y, pb[y]);
    }
  }
  return 0;
}

例題 2

Complicated Computations

給出一個序列 \(a\)，將 \(a\) 所有連續子序列的 MEX 構成的數組作為 \(b\)，問 \(b\) 的 MEX。一個序列的 MEX 是序列中最小的沒出現過的 正整數。

序列的長度 \(n\) 滿足 \(1 \le n \le 10^5\)。

觀察：一個序列的 MEX 為 \(mex\)，當且僅當這個序列包含 \(1\) 至 \(mex-1\)，但不包含 \(mex\)。

依次判斷是否存在 MEX 為 \(1\) 至 \(n+1\) 的連續子序列。如果沒有 MEX 為 \(i\) 的連續子序列，那麼答案即為 \(i\)。如果都存在，那麼答案為 \(n + 2\)。

在判斷 \(i\) 時，將序列視為由零或多個 \(i\) 分隔的多個段。如果存在一個段，這個段中包含 \(1\) 至 \(i - 1\)，但不包含 \(i\)，那麼就説明存在值為 \(i\) 的連續子序列。

用一個數組 \(Y_j\) 記錄上一個值為 \(a_j\) 的元素的位置，以 \(j\) 作為 \(x\)，\(Y_j\) 作為 \(y\)，\(a_j\) 作為 \(z\)。這樣，計算段內是否包含 \(1\) 至 \(i - 1\) 就是一個三維偏序的問題。形式化的説，判斷段 \([l, r]\) 的 MEX 值是否為 \(i\)，就是看滿足 \(l \le j \le r, Y_j \le l - 1, a_j \le i - 1\) 的點的個數是否為 \(i-1\)。

如果在判斷完值為 \(i\) 的元素之後再將對應的點插入，這時因為 \([l, r]\) 內只存在 \(a_j \le i - 1\) 的元素，所以上述三維偏序問題就可以轉換為二維偏序的問題。

參考代碼（分塊套樹狀數組 - 78ms） 
  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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int M = sqrt(N) + 5;

// 分塊
int nn, b[N], block_size, block_cnt, block_id[N], L[N], R[N], T[M][N];

void build(int n) {
  nn = n;
  block_size = sqrt(nn);
  block_cnt = nn / block_size;
  for (int i = 1; i <= block_cnt; ++i) {
    L[i] = R[i - 1] + 1;
    R[i] = i * block_size;
  }
  if (R[block_cnt] < nn) {
    ++block_cnt;
    L[block_cnt] = R[block_cnt - 1] + 1;
    R[block_cnt] = nn;
  }
  for (int j = 1; j <= block_cnt; ++j)
    for (int i = L[j]; i <= R[j]; ++i) block_id[i] = j;
}

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

// d = 1: 加點(p, v)
// d = -1: 刪點(p, v)
void add(int p, int v, int d) {
  for (int i = block_id[p]; i <= block_cnt; i += lb(i))
    for (int j = v; j <= nn; j += lb(j)) T[i][j] += d;
}

// 詢問[1, r]內，縱座標小於等於val的點有多少個
int getsum(int p, int v) {
  if (!p) return 0;
  int res = 0;
  int id = block_id[p];
  for (int i = L[id]; i <= p; ++i)
    if (b[i] && b[i] <= v) ++res;
  for (int i = id - 1; i; i -= lb(i))
    for (int j = v; j; j -= lb(j)) res += T[i][j];
  return res;
}

// 詢問[l, r]內，縱座標小於等於val的點有多少個
int query(int l, int r, int val) {
  if (l > r) return -1;
  int res = getsum(r, val) - getsum(l - 1, val);
  return res;
}

// 加點(p, v)
void update(int p, int v) {
  b[p] = v;
  add(p, v, 1);
}

int n, a[N];
vector<int> g[N];

int main() {
  scanf("%d", &n);

  // 為了減少討論，加了哨兵節點
  // 因為樹狀數組添加的時候，為0可能會死循環，所以整體往右偏移一位
  // a_1和a_{n+2}為哨兵節點
  for (int i = 2; i <= n + 1; ++i) scanf("%d", &a[i]);
  for (int i = 2; i <= n + 1; ++i) g[a[i]].push_back(i);

  // 分塊
  build(n + 2);

  int ans = n + 2, lst, ok;
  for (int i = 1; i <= n + 1; ++i) {
    g[i].push_back(n + 2);

    lst = 1;
    ok = 0;
    for (int pos : g[i]) {
      if (query(lst + 1, pos - 1, lst) == i - 1) {
        ok = 1;
        break;
      }
      lst = pos;
    }

    if (!ok) {
      ans = i;
      break;
    }

    lst = 1;
    g[i].pop_back();
    for (int pos : g[i]) {
      update(pos, lst);
      lst = pos;
    }
  }
  printf("%d\n", ans);
  return 0;
}
參考代碼（線段樹套 Treap-468ms） 
  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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;

vector<int> g[N];
int n, a[N];

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct Treap {
  struct node {
    node *l, *r;
    unsigned rnd;
    int sz, v;

    node(int _v) : l(NULL), r(NULL), rnd(rng()), sz(1), v(_v) {}
  };

  int get_size(node*& p) { return p ? p->sz : 0; }

  void push_up(node*& p) {
    if (!p) return;
    p->sz = get_size(p->l) + get_size(p->r) + 1;
  }

  node* root;

  node* merge(node* a, node* b) {
    if (!a) return b;
    if (!b) return a;
    if (a->rnd < b->rnd) {
      a->r = merge(a->r, b);
      push_up(a);
      return a;
    } else {
      b->l = merge(a, b->l);
      push_up(b);
      return b;
    }
  }

  void split_val(node* p, const int& k, node*& a, node*& b) {
    if (!p)
      a = b = NULL;
    else {
      if (p->v <= k) {
        a = p;
        split_val(p->r, k, a->r, b);
        push_up(a);
      } else {
        b = p;
        split_val(p->l, k, a, b->l);
        push_up(b);
      }
    }
  }

  void split_size(node* p, int k, node*& a, node*& b) {
    if (!p)
      a = b = NULL;
    else {
      if (get_size(p->l) <= k) {
        a = p;
        split_size(p->r, k - get_size(p->l), a->r, b);
        push_up(a);
      } else {
        b = p;
        split_size(p->l, k, a, b->l);
        push_up(b);
      }
    }
  }

  void insert(int val) {
    node *a, *b;
    split_val(root, val, a, b);
    a = merge(a, new node(val));
    root = merge(a, b);
  }

  int query(int val) {
    node *a, *b;
    split_val(root, val, a, b);
    int res = get_size(a);
    root = merge(a, b);
    return res;
  }

  int qry(int l, int r) { return query(r) - query(l - 1); }
};

// Segment Tree
Treap T[N << 2];

void insert(int x, int l, int r, int p, int val) {
  T[x].insert(val);
  if (l == r) return;
  int mid = (l + r) >> 1;
  if (p <= mid)
    insert(x << 1, l, mid, p, val);
  else
    insert(x << 1 | 1, mid + 1, r, p, val);
}

int query(int x, int l, int r, int L, int R, int val) {
  if (l == L && r == R) return T[x].query(val);
  int mid = (l + r) >> 1;
  if (R <= mid) return query(x << 1, l, mid, L, R, val);
  if (L > mid) return query(x << 1 | 1, mid + 1, r, L, R, val);
  return query(x << 1, l, mid, L, mid, val) +
         query(x << 1 | 1, mid + 1, r, mid + 1, R, val);
}

int query(int l, int r, int val) {
  if (l > r) return -1;
  return query(1, 1, n, l, r, val);
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  for (int i = 1; i <= n; ++i) g[a[i]].push_back(i);

  // a_0 和 a_{n+1}為哨兵節點
  int ans = n + 2, lst, ok;
  for (int i = 1; i <= n + 1; ++i) {
    g[i].push_back(n + 1);

    lst = 0;
    ok = 0;
    for (int pos : g[i]) {
      if (query(lst + 1, pos - 1, lst) == i - 1) {
        ok = 1;
        break;
      }
      lst = pos;
    }

    if (!ok) {
      ans = i;
      break;
    }

    lst = 0;
    g[i].pop_back();
    for (int pos : g[i]) {
      insert(1, 1, n, pos, lst);
      lst = pos;
    }
  }
  printf("%d\n", ans);
  return 0;
}
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用