Skip to content

Block Decomposition Idea

Introduction

In fact, block decomposition is a concept, not a data structure.

From NOIP to NOI to IOI, block decomposition ideas appear at various difficulty levels.

The basic idea of block decomposition is to appropriately partition the original data and preprocess partial information on each block, thereby achieving a better time complexity compared to general brute-force algorithms.

The time complexity of block decomposition mainly depends on the block size. Generally, the optimal block size for a given problem, along with the corresponding time complexity, can be derived using the AM-GM inequality.

Block decomposition is a flexible concept. Compared to Fenwick trees and segment trees, its advantage lies in better generality, as it can maintain many types of information that Fenwick trees and segment trees cannot.

Of course, the downside of block decomposition is its asymptotic complexity, which is not as good as that of segment trees and Fenwick trees.

However, for most problems, block decomposition remains a good choice.

Here are a few examples.

Range Sum

Example LibreOJ 6280 Sequence Blocking Basics 4

Given a sequence \(\{a_i\}\) of length \(n\), perform \(n\) operations. There are two types of operations:

  1. Add \(x\) to all numbers between \(a_l \sim a_r\);

  2. Find \(\sum_{i=l}^r a_i\).

    \(1 \leq n \leq 5 \times 10^4\)

We divide the sequence into blocks of \(s\) elements each and record the sum \(b_i\) of each block.

\[ \underbrace{a_1, a_2, \ldots, a_s}_{b_1}, \underbrace{a_{s+1}, \ldots, a_{2s}}_{b_2}, \dots, \underbrace{a_{(s-1) \times s+1}, \dots, a_n}_{b_{\frac{n}{s}}} \]

The last block may be incomplete (since \(n\) is likely not a multiple of \(s\)), but this does not significantly affect our discussion.

First, consider the query operation:

  • If \(l\) and \(r\) are in the same block, simply sum directly via brute force. Since the block length is \(s\), the worst-case complexity is \(O(s)\).
  • If \(l\) and \(r\) are not in the same block, the answer consists of three parts: the incomplete block starting at \(l\), several complete blocks in the middle, and the incomplete block ending at \(r\). For incomplete blocks, we still use brute force. For complete blocks, we directly use the precomputed \(b_i\) sums. In this case, the worst-case complexity is \(O(\dfrac{n}{s}+s)\).

Next, consider the update operation:

  • If \(l\) and \(r\) are in the same block, update directly via brute force. Since the block length is \(s\), the worst-case complexity is \(O(s)\).
  • If \(l\) and \(r\) are not in the same block, we need to update three parts: the incomplete block starting at \(l\), several complete blocks in the middle, and the incomplete block ending at \(r\). For incomplete blocks, we still update each element via brute force (remember to update the block sum \(b_i\)). For complete blocks, we directly update \(b_i\). In this case, the worst-case complexity remains \(O(\dfrac{n}{s}+s)\).

Using the AM-GM inequality, we find that when \(\dfrac{n}{s}=s\), i.e., \(s=\sqrt n\), the time complexity per operation is optimal at \(O(\sqrt n)\).

Reference Code 

 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
```cpp
#include <cmath>
#include <iostream>
using namespace std;
int id[50005], len;
// id represents block number, len = sqrt(n), i.e., s in the above solution, sqrt gives optimal time complexity
long long a[50005], b[50005], s[50005];

// a array stores the data, b array records the overall assignment for each block, similar to lazy_tag, s stores the sum of elements in each block
void add(int l, int r, long long x) {  // interval addition
  int sid = id[l], eid = id[r];
  if (sid == eid) {  // within the same block
    for (int i = l; i <= r; i++) a[i] += x, s[sid] += x;
    return;
  }
  for (int i = l; id[i] == sid; i++) a[i] += x, s[sid] += x;
  for (int i = sid + 1; i < eid; i++)
    b[i] += x, s[i] += len * x;  // update interval sum array (complete blocks)
  for (int i = r; id[i] == eid; i--) a[i] += x, s[eid] += x;
  // The above two lines handle incomplete blocks by simple summation, that's OK
}

long long query(int l, int r, long long p) {  // interval query
  int sid = id[l], eid = id[r];
  long long ans = 0;
  if (sid == eid) {  // within the same block, directly sum by brute force
    for (int i = l; i <= r; i++) ans = (ans + a[i] + b[sid]) % p;
    return ans;
  }
  for (int i = l; id[i] == sid; i++) ans = (ans + a[i] + b[sid]) % p;
  for (int i = sid + 1; i < eid; i++) ans = (ans + s[i]) % p;
  for (int i = r; id[i] == eid; i--) ans = (ans + a[i] + b[eid]) % p;
  // Same principle as the interval modification above
  return ans;
}

int main() {
  int n;
  cin >> n;
  len = sqrt(n);  // From the mean inequality, the optimal complexity is sqrt(n)
  for (int i = 1; i <= n; i++) {  // as required by the problem statement
    cin >> a[i];
    id[i] = (i - 1) / len + 1;
    s[id[i]] += a[i];
  }
  for (int i = 1; i <= n; i++) {
    int op, l, r, c;
    cin >> op >> l >> r >> c;
    if (op == 0)
      add(l, r, c);
    else
      cout << query(l, r, c + 1) << endl;
  }
  return 0;
}

/*
https://loj.ac/s/1151495
 */
```

Range Sum 2

The complexity of the previous approach is \(\Omega(1) , O(\sqrt{n})\).

Here we introduce an algorithm with \(O(\sqrt{n}) - O(1)\) complexity.

To achieve \(O(1)\) queries, we can maintain various prefix sums.

However, under updates, maintaining prefix sums is inconvenient, so we only maintain prefix sums within individual blocks.

Additionally, we maintain prefix sums treating each whole block as a unit.

Each update takes \(O(T+\frac{n}{T})\).

Queries involve three parts, each of which can be obtained directly via prefix sums, with time complexity \(O(1)\).

Blocking Queries

Consider the same problem, but now the sequence length is \(n\), and there are \(m\) operations.

If the number of operations is small, we can record the operations and apply their effects during queries.

Assume we record at most \(T\) operations. Then updates take \(O(1)\), and queries take \(O(T)\).

After \(T\) operations, we recompute the prefix sums in \(O(n)\).

Total complexity: \(O(mT+n\frac{m}{T})\).

When \(T=\sqrt{n}\), the total complexity is \(O(m \sqrt{n})\).

Other Problems

Block decomposition can also be applied to other integer-related problems: counting zero elements, finding the first non-zero element, counting elements satisfying a certain property, etc.

Some other problems can be solved via block decomposition, such as maintaining a set that allows adding or deleting numbers, checking whether a number belongs to the set, and finding the \(k\)-th largest number. To solve this, numbers must be stored in increasing order and divided into blocks, each containing \(\sqrt{n}\) numbers. Each time a number is added or deleted, re-blocking must be performed by moving numbers across adjacent block boundaries.

A well-known offline algorithm, Mo's algorithm, is also based on block decomposition.

Practice Problems

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