AIOJ

Introduction

Under certain conditions, block decomposition with a Fenwick tree can perform some tasks that a tree-of-trees structure can perform. Compared with a tree of trees, its code is shorter and easier to implement.

A Simple Example

A simple example is querying the number of points inside a rectangular region of the two-dimensional plane.

Rectangular Region Queries

Given $n$ points $(x_i, y_i)$ in the two-dimensional plane, where $1 \le i \le n, 1 \le x_i, y_i \le n, 1 \le n \le 10^5$ , implement the following operations:

Given $a, b, c, d$ , query the number of points in the rectangular region whose upper-left corner is $(a, b)$ and lower-right corner is $c, d$ .
Given $x, y$ , change the vertical coordinate of the point whose horizontal coordinate is $x$ to $y$ .

The problem is online, and it is guaranteed that $x_i \ne x_j(1 \le i, j \le n, i \ne j)$ .

For operation 1, rectangle inclusion–exclusion reduces the problem to four two-dimensional partial-order queries. Since the problem is online, offline algorithms such as CDQ divide and conquer cannot be used, which suggests a tree-of-trees structure, such as a Fenwick tree of Treaps. This does solve the problem, but the code is too long and not especially easy to implement.

Notice that the problem additionally guarantees $x_i \ne x_j(1 \le i, j \le n, i \ne j)$ . Under this condition, block decomposition with a Fenwick tree can be used.

Initialization

First, each $x$ corresponds to exactly one $y$ , so an array can record this mapping. For example, let $Y_i$ denote the y-coordinate of the point whose x-coordinate is $i$ .

Then divide the x-coordinates into blocks of size $\sqrt n$ . Build a value Fenwick tree for each block. Let $T_i$ be the Fenwick tree corresponding to block $i$ , and let $T_{i, j}$ denote the number of points in block $i$ whose y-coordinates lie in $(j - lowbit(j), j]$ .

Queries

For operation 1, transform it into four two-dimensional partial-order queries. It remains only to solve the query: given $a, b$ , how many points satisfy $1 \le x_i \le a, 1\le y_i \le b$ ?

We now query the range of x-coordinates $[1, a]$ . Since the right end of the query range may leave a partial block, scan that segment by brute force, checking whether $Y_i \le b$ , and count the points in the segment that satisfy the condition.

Now only complete blocks need to be handled. Scan the preceding blocks by brute force, query in each block's Fenwick tree the number of values less than $b$ , and add them to the answer.

Is that all? No. Notice that handling complete blocks is actually equivalent to querying a prefix sum of $T$ . If updates also process $T$ using Fenwick-tree techniques, the query complexity becomes lower.

Updates

The ordinary method is to first find the block containing $x$ , then perform one decrement and one increment as two point updates in the value Fenwick trees, and finally set $Y_x$ to $y$ .

With the optimization described above, we also process $T$ through a Fenwick-tree update; each update likewise consists of one decrement and one increment in two value Fenwick-tree point updates.

The above steps can be modified: changing “decrement and increment” to only decrement deletes a point, while changing it to only increment adds a point. However, it must be remembered that a single $x$ can correspond to only one $y$ .

Space Complexity

There are $\sqrt n$ blocks, and each block has a Fenwick tree using $O(n)$ space, so the space complexity is $O(n \sqrt n)$ .

Time Complexity

For a query, traversing the partial block takes $O(\sqrt n)$ . Then $T$ is queried as a Fenwick tree, and each $T_i$ reached is also queried as a Fenwick tree; this step has complexity $O(\log (\sqrt n) \log n)$ . Therefore, the query time complexity is $O (\sqrt n + \log (\sqrt n) \log n)$ .

Updates have the same complexity as queries: $O (\sqrt n + \log (\sqrt n) \log n)$ .

Example 1

Intersection of Permutations

Given two permutations $a$ and $b$ , implement the following operations:

Given $l_a, r_a, l_b, r_b$ , query the number of elements that appear both in $a[l_a ... r_a]$ and in $b[l_b ... r_b]$ .
Given $x, y$ , perform $swap(b_x, b_y)$ .

The sequence length $n$ satisfies $2 \le n \le 2 \cdot 10^5$ , and the number of operations $q$ satisfies $1 \le q \le 2 \cdot 10^5$ .

For each value $i$ , let $x_i$ be its index in permutation $b$ , and let $y_i$ be its index in permutation $a$ . Then operation 1 becomes a query for the number of points in a rectangular region, while operation 2 can be regarded as two updates. Since these are permutations, each $x$ corresponds to one $y$ , so this problem can be solved with block decomposition plus a Fenwick tree.

Reference code (block decomposition with a Fenwick tree — 1s)

#include <cmath>
#include <cstdio>
using namespace std;
constexpr int N = 2e5 + 5;
constexpr int M = 447 + 5;  // 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;
}

Reference code (Fenwick tree of Treaps — TLE)

#include <cstdio>
#include <random>
using namespace std;
constexpr int N = 2e5 + 5;
mt19937 rng(random_device{}());

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

Example 2

Complicated Computations

Given a sequence $a$ , let $b$ be the array formed by the MEX values of all contiguous subsequences of $a$ . Find the MEX of $b$ . The MEX of a sequence is the smallest positive integer that does not occur in the sequence.

The sequence length $n$ satisfies $1 \le n \le 10^5$ .

Observation: A sequence has MEX $mex$ if and only if it contains every integer from $1$ through $mex-1$ , but does not contain $mex$ .

Check in order whether there is a contiguous subsequence with MEX $1$ through $n+1$ . If there is no contiguous subsequence with MEX $i$ , the answer is $i$ . If all of them exist, the answer is $n + 2$ .

When checking $i$ , view the sequence as multiple segments separated by zero or more occurrences of $i$ . If there is a segment containing $1$ through $i - 1$ but not containing $i$ , then there is a contiguous subsequence with value $i$ .

Use an array $Y_j$ to record the position of the previous element whose value is $a_j$ , taking $j$ as $x$ , $Y_j$ as $y$ , and $a_j$ as $z$ . Then determining whether a segment contains $1$ through $i - 1$ is a three-dimensional partial-order problem. Formally, determining whether the MEX of the segment $[l, r]$ is $i$ amounts to checking whether the number of points satisfying $l \le j \le r, Y_j \le l - 1, a_j \le i - 1$ is $i-1$ .

If the corresponding point is inserted only after checking the value $i$ , then, because the interval $[l, r]$ contains only elements with $a_j \le i - 1$ , the three-dimensional partial-order problem above can be converted into a two-dimensional partial-order problem.

Reference code (block decomposition with a Fenwick tree — 78ms)

#include <cmath>
#include <cstdio>
#include <vector>
using namespace std;
constexpr int N = 1e5 + 5;
constexpr int M = 316 + 5;  // sqrt(N) + 5

// Block decomposition
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: add point (p, v)
// d = -1: delete point (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;
}

// Query the number of points in [1, r] whose y-coordinate is at most 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;
}

// Query the number of points in [l, r] whose y-coordinate is at most 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;
}

// Add point (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);

  // Sentinel nodes are added to simplify the discussion
  // Since adding 0 to a Fenwick tree can cause an infinite loop, shift everything one position to the right
  // a_1 and a_{n+2} are sentinel nodes
  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);

  // Block decomposition
  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;
}

Reference code (segment tree of Treaps — 468ms)

#include <cstdio>
#include <random>
#include <vector>
using namespace std;
constexpr int N = 1e5 + 5;

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

mt19937 rng(random_device{}());

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 and a_{n+1} are sentinel nodes
  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;
}