Skip to content

Segment Tree in Balanced Tree

Common Applications

In algorithm competitions, we sometimes need to maintain multi-dimensional information. In such cases, we often require nested data structures like segment trees combined with balanced trees. When we need to maintain predecessor, successor, the k-th largest element, the rank of a certain value, or support insertion and deletion operations, we typically use balanced trees to meet our requirements, i.e., a segment tree of balanced trees.

Process

We take the "Erbi Balanced Tree" problem as an example to explain the implementation principle.

Regarding the construction of the nested tree structure, we build the outer segment tree normally. For each node of the segment tree, we build a balanced tree containing the sequence covered by that node. Specifically, during the operation, we can insert the sequence elements one by one. Whenever we pass through a segment tree node, we add the element to the balanced tree of that node.

Operation 1: Query the rank of a value in a certain interval. We operate normally on the outer segment tree. For the balanced trees of nodes within the interval, we return the number of elements smaller than the given value in the balanced tree. When merging intervals, we sum the counts of smaller elements. Finally, add 1 to the return value to obtain the rank of the value in the interval.

Operation 2: Query the value with rank k in a certain interval. We can adopt a binary search strategy. Since an element may appear multiple times, its rank is an interval, and some elements may not exist in the original sequence. Therefore, we use a similar approach as in Operation 1. We use the count of elements smaller than the value as a reference for binary search to obtain the solution.

Operation 3: Replace a number with another number. We simply delete the original number from all balanced trees containing it and then insert the new number. The outer segment tree operations remain normal.

Operation 4: Query the predecessor of a value in a certain interval. We operate normally on the outer segment tree. For the balanced trees of nodes within the interval, we return the predecessor of the value in that balanced tree. When merging the results from the segment tree intervals, we take the maximum value.

Properties

Space Complexity

Each element is added to \(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 involves \(O(\log{n})\) operations on an inner balanced tree, resulting in a time complexity of \(O(\log^2{n})\).
  • For operation 2, an additional binary search process is involved, leading to a time complexity of \(O(\log^3{n})\).

Classic Example

Erbi Balanced Tree uses an outer segment tree and inner balanced trees.

Implementation

For the balanced tree part of the code, please refer to other entries such as Splay.

Operation 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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:

1
2
3
4
5
6
7
8
9
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:

1
2
3
4
5
6
7
8
9
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:

1
2
3
4
5
6
7
8
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;
}

When facing problems with multi-dimensional information, if the problem does not require being online, we can also consider divide-and-conquer algorithms such as CDQ Divide and Conquer or Parallel Binary Search to avoid using advanced data structures and reduce implementation difficulty.

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