跳转至

塊狀數組

建立塊狀數組

塊狀數組，即把一個數組分為幾個塊，塊內信息整體保存，若查詢時遇到兩邊不完整的塊直接暴力查詢。一般情況下，塊的長度為 \(O(\sqrt{n})\)。詳細分析可以閲讀 2017 年國家集訓隊論文中徐明寬的《非常規大小分塊算法初探》。

下面直接給出一種建立塊狀數組的代碼。

實現 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
num = sqrt(n);
for (int i = 1; i <= num; i++)
  st[i] = n / num * (i - 1) + 1, ed[i] = n / num * i;
ed[num] = n;
for (int i = 1; i <= num; i++) {
  for (int j = st[i]; j <= ed[i]; j++) {
    belong[j] = i;
  }
  size[i] = ed[i] - st[i] + 1;
}

其中 st[i] 和 ed[i] 為塊的起點和終點，size[i] 為塊的大小。

保存與修改塊內信息

例題 1：教主的魔法

兩種操作：

  1. 區間 \([x,y]\) 每個數都加上 \(z\)；
  2. 查詢區間 \([x,y]\) 內大於等於 \(z\) 的數的個數。

我們要詢問一個塊內大於等於一個數的數的個數，所以需要一個 t 數組對塊內排序，a 為原來的（未被排序的）數組。對於整塊的修改，使用類似於標記永久化的方式，用 delta 數組記錄現在塊內整體加上的值。設 \(q\) 為查詢和修改的操作次數總和，則時間複雜度 \(O(q\sqrt{n}\log n)\)。

用 delta 數組記錄每個塊的整體賦值情況。

實現 
 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
void Sort(int k) {
  for (int i = st[k]; i <= ed[k]; i++) t[i] = a[i];
  sort(t + st[k], t + ed[k] + 1);
}

void Modify(int l, int r, int c) {
  int x = belong[l], y = belong[r];
  if (x == y)  // 區間在一個塊內就直接修改
  {
    for (int i = l; i <= r; i++) a[i] += c;
    Sort(x);
    return;
  }
  for (int i = l; i <= ed[x]; i++) a[i] += c;     // 直接修改起始段
  for (int i = st[y]; i <= r; i++) a[i] += c;     // 直接修改結束段
  for (int i = x + 1; i < y; i++) delta[i] += c;  // 中間的塊整體打上標記
  Sort(x);
  Sort(y);
}

int Answer(int l, int r, int c) {
  int ans = 0, x = belong[l], y = belong[r];
  if (x == y) {
    for (int i = l; i <= r; i++)
      if (a[i] + delta[x] >= c) ans++;
    return ans;
  }
  for (int i = l; i <= ed[x]; i++)
    if (a[i] + delta[x] >= c) ans++;
  for (int i = st[y]; i <= r; i++)
    if (a[i] + delta[y] >= c) ans++;
  for (int i = x + 1; i <= y - 1; i++)
    ans +=
        ed[i] - (lower_bound(t + st[i], t + ed[i] + 1, c - delta[i]) - t) + 1;
  // 用 lower_bound 找出中間每一個整塊中第一個大於等於 c 的數的位置
  return ans;
}

例題 2：寒夜方舟

兩種操作：

  1. 區間 \([x,y]\) 每個數都變成 \(z\)；
  2. 查詢區間 \([x,y]\) 內小於等於 \(z\) 的數的個數。

用 delta 數組記錄現在塊內被整體賦值為何值。當該塊未被整體賦值時，用一個特殊值（如 0x3f3f3f3f3f3f3f3fll）加以表示。對於邊角塊，查詢前要 pushdown，把塊內存的信息下放到每一個數上。賦值之後記得重新 sort 一遍。其他方面同上題。

實現 
 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
void Sort(int k) {
  for (int i = st[k]; i <= ed[k]; i++) t[i] = a[i];
  sort(t + st[k], t + ed[k] + 1);
}

void PushDown(int x) {
  if (delta[x] != 0x3f3f3f3f3f3f3f3fll)  // 用該值標記塊內沒有被整體賦值
    for (int i = st[x]; i <= ed[x]; i++) a[i] = t[i] = delta[x];
  delta[x] = 0x3f3f3f3f3f3f3f3fll;
}

void Modify(int l, int r, int c) {
  int x = belong[l], y = belong[r];
  PushDown(x);
  if (x == y) {
    for (int i = l; i <= r; i++) a[i] = c;
    Sort(x);
    return;
  }
  PushDown(y);
  for (int i = l; i <= ed[x]; i++) a[i] = c;
  for (int i = st[y]; i <= r; i++) a[i] = c;
  Sort(x);
  Sort(y);
  for (int i = x + 1; i < y; i++) delta[i] = c;
}

int Binary_Search(int l, int r, int c) {
  int ans = l - 1, mid;
  while (l <= r) {
    mid = (l + r) / 2;
    if (t[mid] <= c)
      ans = mid, l = mid + 1;
    else
      r = mid - 1;
  }
  return ans;
}

int Answer(int l, int r, int c) {
  int ans = 0, x = belong[l], y = belong[r];
  PushDown(x);
  if (x == y) {
    for (int i = l; i <= r; i++)
      if (a[i] <= c) ans++;
    return ans;
  }
  PushDown(y);
  for (int i = l; i <= ed[x]; i++)
    if (a[i] <= c) ans++;
  for (int i = st[y]; i <= r; i++)
    if (a[i] <= c) ans++;
  for (int i = x + 1; i <= y - 1; i++) {
    if (0x3f3f3f3f3f3f3f3fll == delta[i])
      ans += Binary_Search(st[i], ed[i], c) - st[i] + 1;
    else if (delta[i] <= c)
      ans += size[i];
  }
  return ans;
}

練習

  1. 單點修改，區間查詢
  2. 區間修改，區間查詢
  3. 【模板】線段樹 2
  4. 「Ynoi2019 模擬賽」Yuno loves sqrt technology III
  5. 「Violet」蒲公英
  6. 作詩
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用