AIOJ

Introduction

Block decomposition is an idea rather than a data structure.

Problems using block decomposition appear at every difficulty level, from NOIP through NOI to IOI.

The basic idea is to partition the original data appropriately and preprocess partial information for each block, thereby obtaining a better time complexity than a general brute-force algorithm.

The time complexity of block decomposition mainly depends on the block length. In general, the optimal block length and the corresponding complexity can be derived using the arithmetic-geometric mean inequality.

Block decomposition is very flexible. Compared with a Fenwick tree or a segment tree, its advantage is greater generality: it can maintain information that many Fenwick trees and segment trees cannot.

Its drawback, of course, is that its asymptotic complexity is not as good as that of a segment tree or a Fenwick tree.

Nevertheless, for most problems block decomposition remains a useful choice.

Here are several examples.

Range Sum

Example: LibreOJ 6280, Introduction to Sequence Block Decomposition 4

Given a sequence of length $n$ , $\{a_i\}$ , perform $n$ operations. There are two kinds of operations:

Add $x$ to every number between $a_l \sim a_r$ .
Compute $\sum_{i=l}^r a_i$ .

$1 \leq n \leq 5 \times 10^4$

Partition the sequence into blocks of $s$ elements each, and record the sum $b_i$ of every 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 because $n$ need not be a multiple of $s$ , but this has little effect on the discussion.

First consider a query:

If $l$ and $r$ are in the same block, sum the elements by 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 beginning at $l$ , several complete blocks in the middle, and the incomplete block ending at $r$ . Compute the incomplete blocks by brute force as above, and use the precomputed $b_i$ for the complete blocks. The worst-case complexity is $O(\dfrac{n}{s}+s)$ .

Now consider an update:

If $l$ and $r$ are in the same block, update directly. Since the block length is $s$ , the worst-case complexity is $O(s)$ .
If $l$ and $r$ are not in the same block, update three parts: the incomplete block beginning at $l$ , several complete blocks in the middle, and the incomplete block ending at $r$ . For incomplete blocks, update each element by brute force (and remember to update the block sum $b_i$ ); for complete blocks, update $b_i$ directly. The worst-case complexity is again $O(\dfrac{n}{s}+s)$ .

By the arithmetic-geometric mean inequality, a single operation is fastest when $\dfrac{n}{s}=s$ , namely $s=\sqrt n$ , giving complexity $O(\sqrt n)$ .

Reference implementation

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

// The a array stores the data, while the b array records the aggregate assignment for each block, similar to lazy_tag; s
// stores the sum of the elements in the block.
void add(int l, int r, long long x) {  // Range addition.
  int sid = id[l], eid = id[r];
  if (sid == eid) {  // Within a 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 the range-sum array (a complete block).
  for (int i = r; id[i] == eid; i--) a[i] += x, s[eid] += x;
  // For the two incomplete blocks above, simply sum directly; that's enough.
}

long long query(int l, int r, long long p) {  // Range query.
  int sid = id[l], eid = id[r];
  long long ans = 0;
  if (sid == eid) {  // Brute-force sum directly within a block.
    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;
  // The same idea as the range update above.
  return ans;
}

int main() {
  int n;
  cin >> n;
  len = sqrt(n);  // By the arithmetic-mean inequality, the optimal complexity is sqrt(n).
  for (int i = 1; i <= n; i++) {  // 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 preceding method has complexity $\Omega(1) , O(\sqrt{n})$ .

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

To answer queries in $O(1)$ time, we can maintain various prefix sums.

With updates, however, maintaining all of them is inconvenient, so we maintain prefix sums within each individual block.

We also maintain prefix sums whose unit is a complete block.

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

A query involves three parts, each of which can be obtained directly from prefix sums, so its complexity is $O(1)$ .

Block Decomposition of Queries

Consider the same problem with a sequence of length $n$ and $m$ operations.

If there are relatively few operations, we can record them and add their effects when answering a query.

Suppose we record at most $T$ operations. An update costs $O(1)$ and a query costs $O(T)$ .

After $T$ operations, recompute the prefix sums in $O(n)$ time.

The total complexity is $O(mT+n\frac{m}{T})$ .

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

Exercises

UVa - 12003 - Array Transformer
UVa - 11990 Dynamic Inversion
SPOJ - Give Away
Codeforces - Till I Collapse
Codeforces - Destiny
Codeforces - Holes
Codeforces - XOR and Favorite Number
Codeforces - Powerful array
SPOJ - DQUERY

This page is mainly translated from the blog post Sqrt-decomposition and the English edition Sqrt Decomposition. The Russian version is licensed under Public Domain + Leave a Link; the English version is licensed under CC-BY-SA 4.0.