Skip to content

Block Array

Building a Block Array

A block array divides an array into several blocks, where information within each block is stored collectively. When querying, if incomplete blocks are encountered at the boundaries, brute-force queries are performed directly. Typically, the block size is \(O(\sqrt{n})\). For a detailed analysis, refer to Xu Mingkuan's Preliminary Exploration of Unconventional Sized Block Algorithms in the 2017 National Training Team thesis.

Below is a direct implementation of building a block array.

Implementation 
 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;
}

Here, st[i] and ed[i] represent the start and end indices of a block, and size[i] is the size of the block.

Storing and Modifying Block Information

Example 1: The Magic of the Cult Leader

Two types of operations:

  1. Add \(z\) to every number in the interval \([x,y]\);
  2. Query the count of numbers greater than or equal to \(z\) in the interval \([x,y]\).

We need to query the count of numbers greater than or equal to a given value within a block, so a t array is used to sort the block, while a retains the original (unsorted) array. For modifications on entire blocks, a method similar to permanent marking is used, with a delta array recording the value added to the entire block. Let \(q\) be the total number of query and modification operations, then the time complexity is \(O(q\sqrt{n}\log n)\).

The delta array records the overall addition value for each block.

Implementation 
 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)  // If the interval lies within a single block, modify directly
  {
    for (int i = l; i <= r; i++) a[i] += c;
    Sort(x);
    return;
  }
  for (int i = l; i <= ed[x]; i++) a[i] += c;     // Directly modify the starting segment
  for (int i = st[y]; i <= r; i++) a[i] += c;     // Directly modify the ending segment
  for (int i = x + 1; i < y; i++) delta[i] += c;  // Mark the entire middle blocks
  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;
  // Use lower_bound to find the position of the first number >= c in each entire middle block
  return ans;
}

Example 2: Cold Night Ark

Two types of operations:

  1. Set every number in the interval \([x,y]\) to \(z\);
  2. Query the count of numbers less than or equal to \(z\) in the interval \([x,y]\).

The delta array records the value to which the entire block is currently set. When a block is not entirely set, a special value (e.g., 0x3f3f3f3f3f3f3f3fll) is used to indicate this. For edge blocks, a pushdown operation is required before querying to propagate the block's stored information to each individual element. After assignment, remember to sort the block again. Other aspects are similar to the previous problem.

Implementation 
 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)  // Use this value to mark that the block is not entirely set
    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;
}

Exercises

  1. Single Point Modification, Interval Query
  2. Interval Modification, Interval Query
  3. Template: Segment Tree 2
  4. 「Ynoi2019 Mock Contest」Yuno loves sqrt technology III
  5. 「Violet」Dandelion
  6. Poetry
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用