AIOJ

Common Uses

In algorithm competitions, we sometimes need to maintain multidimensional information. In such cases, a tree of trees is often used to record the information. When we need to maintain predecessors, successors, the $k$ -th largest element, the rank of a value, or support insertion and deletion, we generally use a balanced tree to meet these requirements—that is, a segment tree of balanced trees.

Process

We use the Second-tier Balanced Tree as an example to explain the implementation.

To build a tree of trees, build the outer segment tree normally. For each node of the segment tree, build a balanced tree containing the sequence covered by that node. In practice, insert the sequence elements one by one: whenever an element passes through a segment-tree node, insert it into that node's balanced tree.

Operation 1, finding the rank of a value in an interval: operate on the outer segment tree normally. For each balanced tree belonging to a node inside the interval, return the number of elements smaller than the value, and sum these counts when merging interval results. Finally, add $+1$ to the returned value to obtain the rank of the value in the interval.

Operation 2, finding the value whose rank in an interval is $k$ : use binary search. Because an element may occur multiple times, its rank may cover an interval, and some values may not occur in the original sequence, we use the number of elements smaller than the value as the reference for binary search, just as in Operation 1.

Operation 3, replacing a value with another value: delete the value from every balanced tree containing it, then insert the new value. The outer segment-tree operation remains standard.

Operation 4, finding the predecessor of a value in an interval: operate on the outer segment tree normally. For each balanced tree belonging to a node inside the interval, return the predecessor of the value in that balanced tree; when merging the segment-tree interval results, take the maximum.

Properties

Space Complexity

Each element is inserted into $O(\log n)$ balanced trees, so the space complexity is $O((n + q)\log{n})$ .

Time complexity

For Operations 1, 3, and 4, we perform $O(\log{n})$ operations on the outer segment tree, and each operation performs $O(\log{n})$ operations on an inner balanced tree, so the time complexity is $O(\log^2{n})$ .
Operation 2 has an additional binary-search process, giving $O(\log^3{n})$ .

Classic Example

Second-tier Balanced Tree: a segment tree on the outside and a balanced tree on the inside.

Implementation

For the balanced-tree code, see entries such as Splay.

Operation 1:

int vec_rank(int k, int l, int r, int x, int y, int t) {
  if (x <= l && r <= y) {
    return spy[k].chk_rank(t);
  }
  int mid = l + r >> 1;
  int res = 0;
  if (x <= mid) res += vec_rank(k << 1, l, mid, x, y, t);
  if (y > mid) res += vec_rank(k << 1 | 1, mid + 1, r, x, y, t);
  if (x <= mid && y > mid) res--;
  return res;
}

Operation 2:

int el = 0, er = 100000001, emid;
while (el != er) {
  emid = el + er >> 1;
  if (vec_rank(1, 1, n, tl, tr, emid) - 1 < tk)
    el = emid + 1;
  else
    er = emid;
}
printf("%d\n", el - 1);

Operation 3:

void vec_chg(int k, int l, int r, int loc, int x) {
  int t = spy[k].find(dat[loc]);
  spy[k].dele(t);
  spy[k].insert(x);
  if (l == r) return;
  int mid = l + r >> 1;
  if (loc <= mid) vec_chg(k << 1, l, mid, loc, x);
  if (loc > mid) vec_chg(k << 1 | 1, mid + 1, r, loc, x);
}

Operation 4:

int vec_front(int k, int l, int r, int x, int y, int t) {
  if (x <= l && r <= y) return spy[k].chk_front(t);
  int mid = l + r >> 1;
  int res = 0;
  if (x <= mid) res = max(res, vec_front(k << 1, l, mid, x, y, t));
  if (y > mid) res = max(res, vec_front(k << 1 | 1, mid + 1, r, x, y, t));
  return res;
}

For problems involving multidimensional information, if the problem does not require 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 Balanced Trees