AIOJ

Common Uses

In algorithm competitions, we sometimes need to maintain multidimensional information. In such cases, we often use a segment tree of segment trees to store the information.

How It Works

Let us consider how a segment tree of segment trees can support point updates and range queries on a two-dimensional plane. Consider the outer segment tree. The subtrees rooted at its bottom-level nodes $1$ through $n$ represent the segment trees for rows $1$ through $n$ , respectively. The parent nodes of these bottom-level nodes therefore represent the regions containing the subtrees of their two children.

Properties

Space Complexity

Normally, it is impossible to build an inner segment tree for every node of the outer segment tree, because the space requirement would be too large. A segment tree of segment trees generally uses dynamic node creation. A single update visits $\log{n}$ nodes of the outer segment tree, and the subtree of each such node involves $\log{n}$ nodes, so a single update uses at most $\log^2{n}$ additional space.

Time Complexity

For a query, we perform $\log{n}$ operations on the outer segment tree, and each operation performs $\log{n}$ operations on an inner segment tree. Therefore, the time complexity is $\log^2{n}$ . An update has the same complexity as a query, namely $\log^2{n}$ .

Classic Example

In Full Bloom sorts by the first dimension, then uses a segment tree of segment trees to maintain the second and third dimensions.

Example Code

Queries on the second dimension

int tree_query(int k, int l, int r, int x) {
  if (k == 0) return 0;
  if (1 <= l && r <= sec[x].y) return vec_query(ou_root[k], 1, p, 1, sec[x].z);
  int mid = l + r >> 1, res = 0;
  if (1 <= mid) res += tree_query(ou_ch[k][0], l, mid, x);
  if (sec[x].y > mid) res += tree_query(ou_ch[k][1], mid + 1, r, x);
  return res;
}

Updates on the second dimension

void tree_insert(int &k, int l, int r, int x) {
  if (k == 0) k = ++ou_tot;
  vec_insert(ou_root[k], 1, p, sec[x].z);
  if (l == r) return;
  int mid = l + r >> 1;
  if (sec[x].y <= mid)
    tree_insert(ou_ch[k][0], l, mid, x);
  else
    tree_insert(ou_ch[k][1], mid + 1, r, x);
}

Queries on the third dimension

int vec_query(int k, int l, int r, int x, int y) {
  if (k == 0) return 0;
  if (x <= l && r <= y) return data[k];
  int mid = l + r >> 1, res = 0;
  if (x <= mid) res += vec_query(ch[k][0], l, mid, x, y);
  if (y > mid) res += vec_query(ch[k][1], mid + 1, r, x, y);
  return res;
}

Updates on the third dimension

void vec_insert(int &k, int l, int r, int loc) {
  if (k == 0) k = ++tot;
  data[k]++;
  if (l == r) return;
  int mid = l + r >> 1;
  if (loc <= mid) vec_insert(ch[k][0], l, mid, loc);
  if (loc > mid) vec_insert(ch[k][1], mid + 1, r, loc);
}

For multidimensional problems, if the problem does not require forced online processing, we can also consider divide-and-conquer algorithms such as CDQ divide and conquer or overall binary search to avoid advanced data structures and reduce implementation difficulty.

Segment Tree of Segment Trees