AIOJ

Introduction

Weight Balanced Leafy Tree, hereafter WBLT, is a balanced tree. Compared with other balanced trees, its main advantages are simple implementation and small constants. It supports range operations and can be made persistent.

Weight Balanced Leafy Tree is, as its name suggests, a combination of Weight Balanced Tree and Leafy Tree.

Each node of a Weight Balanced Tree stores the size of the subtree rooted at that node, and the tree height is bounded by maintaining the sizes of its left and right subtrees within a certain ratio.

A Leafy Tree stores the original information only in the tree's leaf nodes. Non-leaf nodes are used only to maintain information about their children and the shape of the data structure. The familiar segment tree is a kind of Leafy Tree.

Throughout this article, a tree means a binary Leafy Tree, that is, each node has either $0$ or $2$ children. Here, $n$ denotes the number of leaf nodes in the tree. A tree with $n$ leaf nodes has $2n-1$ nodes in total; therefore, a WBLT occupies $\Theta(n)$ space.

Basic Structure and Balance Maintenance

This section introduces the basic structure of WBLT, defines the notion of an $\alpha$ ‑balanced tree, and explains how to maintain balance through rotations or merging.

Node Information

To implement a basic WBLT, we only need to record the following information for each node:

lc[x], rc[x]: the left and right children;
sz[x]: the number of leaf nodes in the subtree rooted at $x$ .

To implement a balanced tree with a WBLT, we also need to record key-related information at each node:

val[x]: the key value at node $x$ .

Because only leaf nodes actually store key values, the information stored at other nodes is obtained by combining the information of their children, making subsequent queries easier.

For example, a common way to combine two child nodes is to store the larger of their key values at the parent. Then each node stores the maximum key value among all leaf nodes in the subtree rooted at that node. Based on this, node information can be updated as follows:

Reference code

void push_up(int x) {
  sz[x] = sz[ch[x][0]] + sz[ch[x][1]];
  val[x] = val[ch[x][1]];
}

If necessary, a corresponding push_down(x) function can of course also be implemented.

Auxiliary Functions

In addition to maintaining basic node information, a WBLT usually needs the following auxiliary functions for memory management:

new_node(): create a new node;
del_node(x): delete node $x$ ;
new_leaf(v): create a leaf node whose key value is $v$ ;
join(x, y): join subtrees, with $x$ and $y$ as the left and right children, respectively, and create a new node $z$ ;
cut(x): split a subtree, obtaining the two children of node $x$ and deleting node $x$ .

If a WBLT implementation relies heavily on splitting and joining subtrees, it creates many new nodes and releases an equal number of old nodes. If obsolete nodes are not reclaimed in time, the space usage will no longer be linear. The following is an array-based implementation of these auxiliary functions:

Reference code

// Return a new empty node.
int new_node() {
  int x = top ? pool[--top] : ++id;
  sz[x] = val[x] = ch[x][0] = ch[x][1] = 0;
  return x;
}

// Release a node for later use.
void del_node(int& x) {
  pool[top++] = x;
  x = 0;
}

// Return a new leaf node of value v.
int new_leaf(int v) {
  int x = new_node();
  val[x] = v;
  sz[x] = 1;
  return x;
}

// Return a new node with subtrees x and y.
int join(int x, int y) {
  int z = new_node();
  ch[z][0] = x;
  ch[z][1] = y;
  push_up(z);
  return z;
}

// Return subtrees of x and release x.
auto cut(int& x) {
  int y = ch[x][0];
  int z = ch[x][1];
  del_node(x);
  return std::make_pair(y, z);
}

Once these auxiliary functions are encapsulated, array-based and pointer-based implementations are indistinguishable in the functions that follow.

The Notion of Balance

For a tree, its balance ratio at a non-leaf node $x$ can be defined as

\rho(x) = \dfrac{\min\{w(T_{\operatorname{left}(x)}),w(T_{\operatorname{right}(x)})\}}{w(T_x)}.

Here, $T_x$ denotes the subtree rooted at $x$ , $w(\cdot)$ denotes the weight of a subtree (the number of its leaf nodes), and $\operatorname{left}(x)$ and $\operatorname{right}(x)$ denote the left and right children of $x$ , respectively. At a leaf node, we specifically define $\rho(x)=1/2$ .

For $\alpha\in(0,1/2]$ , if the balance ratio at a node $x$ satisfies $\rho(x)\ge\alpha$ , the node is called $\alpha$ ‑balanced. If every node in a tree is $\alpha$ ‑balanced, the tree is called $\alpha$ ‑balanced. The set of such trees is denoted by $BB[\alpha]$ . A tree is $\alpha$ ‑balanced if and only if it is itself $\alpha$ ‑balanced and both of its subtrees are $\alpha$ ‑balanced, or it is a leaf node.

An obvious benefit of an $\alpha$ ‑balanced tree is that its height is $O(\log n)$ . This is because each step from a leaf toward the root increases the number of leaf nodes in the subtree by at least a factor of $1/(1-\alpha)$ , so there can be only $O(\log_{\frac{1}{1-\alpha}}n) = O(\log n)$ steps. This guarantees that a single query in an $\alpha$ ‑balanced tree always has strict $O(\log n)$ complexity, and the constant factor of the algorithm is positively correlated with $\log(1/(1-\alpha))$ (with base $2$ ). When $\alpha$ lies in the reasonable range given below, this constant is approximately $2\sim 3.5$ .

WBLT balance is usually maintained through rotations or merging. With either approach, a single insertion, deletion, or similar operation on a WBLT has strict $O(\log n)$ complexity. However, unlike a Treap with fixed priorities, a WBLT does not have a unique structure. Therefore, the structures produced by the two maintenance approaches are different, although this does not affect their use. Balance can of course also be maintained with a strategy similar to a Scapegoat Tree, using rebuilding to achieve amortized $O(\log n)$ complexity, but this sacrifices advantages of WBLT such as persistence and range operations, so it is not recommended.

The following sections introduce balance maintenance by rotations and by merging, and implement the corresponding balance-maintenance and merge functions. Once these functions are encapsulated, the two approaches to maintaining tree balance are indistinguishable in subsequent balanced-tree implementations. Moreover, regardless of the approach, a single balance-maintenance operation takes $O(1)$ time, and merging trees $T_1$ and $T_2$ takes $O\left(\left|\log\dfrac{w(T_1)}{w(T_2)}\right|\right)$ time.

Omitting weights in notation

To maintain tree balance, it is enough to retain the weights of subtrees. Thus, for convenience, the two sections below on balance maintenance will use tree and weight notation interchangeably. For example, the weight of subtree $x$ is also denoted by $x$ , rather than $w(x)$ . Similarly, the tree obtained by merging subtrees $x$ and $y$ is denoted by its weight, and written simply as tree $x+y$ .

Maintenance by Rotations

The rotation operation of a WBLT is exactly the same as the rotation operation of a Treap, so the same rotation strategy as for a Treap can be used. A rotation can also be viewed as redistributing subtree weights, and can therefore be implemented using subtree splitting and joining. The results of the two implementations are exactly the same, but the second implementation is more convenient for making a WBLT persistent.

Reference code

Without relying on join

// Rotate the subtree at x such that ch[x][r] is the new root.
void rotate(int& x, bool r) {
  int y = ch[x][r];
  ch[x][r] = ch[y][!r];
  ch[y][!r] = x;
  push_up(x);
  push_up(y);
  x = y;
}

Relying on join

// Rotate the subtree at x such that ch[x][r] is the new root.
void rotate(int& x, bool r) {
  int a, b, c, d;
  std::tie(a, b) = cut(x);
  if (r) {
    std::tie(c, d) = cut(b);
    x = join(join(a, c), d);
  } else {
    std::tie(c, d) = cut(a);
    x = join(c, join(d, b));
  }
}

Suppose that after a modification to a tree, we are restoring balance from the bottom up. The left and right subtrees $x$ and $y$ are no longer balanced with respect to each other, although each is balanced internally. Without loss of generality, suppose the right subtree $y$ is too light, namely $y<\alpha(x+y)$ . The tree then has the shape shown on the left in the figure.

A naive balance-maintenance strategy is to rotate $x$ up to the root. Its former right child $w$ then becomes, together with $y$ , the right subtree of the new tree, while its former left child $z$ becomes the left subtree of the new tree. This is equivalent to moving the weight of $w$ in the left tree of the original figure to its right side. If the weight of $w$ is appropriate, this operation restores balance. The resulting tree is shown on the right in the figure.

However, if $w$ itself is too heavy, this operation may move too much weight to the right subtree, making the left subtree of the new tree too light, namely $z<\alpha(x+y)$ . Here, because both subtrees $z$ and $y$ have weights that are too small, the only option is to split $w$ into two subtrees and join them with $z$ and $y$ , respectively, making them the two subtrees of the new tree. This is equivalent to first rotating node $w$ up to node $x$ , and then rotating it up to the root. We can likewise expect the resulting tree to be balanced; its shape is shown at the top of the figure.

These two rotation strategies are called single rotation and double rotation, respectively. The choice between them mainly depends on the weight of subtree $w$ relative to subtree $x$ : there is a threshold $\beta$ such that

when $w\le\beta x$ , the single-rotation strategy should be used;
when $w>\beta x$ , the double-rotation strategy should be used.

The difficult part is choosing the threshold $\beta$ , which requires some concrete calculations. Blum and Mehlhorn proved that for the parameters¹

\alpha\in\left(\dfrac{2}{11},1-\dfrac{\sqrt{2}}{2}\right]\approx(0.182,0.292],~\beta=\frac{1}{2-\alpha},

the balance of a WBLT made unbalanced by a single insertion or deletion can be maintained using the above combination of single and double rotations.

Proof

We need to prove that if a tree becomes unbalanced after a single insertion or deletion, the above strategy can restore its balance. Following the figure above, let

\rho_1 = \dfrac{y}{x+y}, ~\rho_2 = \dfrac{w}{x}, ~\rho_3 = \dfrac{v}{w}.

Then $\rho_1<\alpha\le\rho_2,\rho_3\le 1-\alpha$ . There is also an implicit condition on the range of $\rho_1$ :

If the imbalance is caused by inserting a single element, then
$\dfrac{y}{x-1+y} \ge \alpha \implies \rho_1 \ge \dfrac{\alpha y}{y+\alpha} \ge \dfrac{\alpha}{1+\alpha}.$
If the imbalance is caused by deleting a single element, then
$\dfrac{y+1}{x+y+1} \ge \alpha \implies \rho_1 \ge \dfrac{\alpha y}{y+1-\alpha} \ge \dfrac{\alpha}{2-\alpha}.$

Since for $0<\alpha<1/2$ we always have $\alpha/(2-\alpha)<\alpha/(1+\alpha)$ , deletion causes a more severe imbalance than insertion, especially for small trees.

The balance-restoration operation now has two cases:

Case 1:

w

is not too heavy; single rotation when

\rho_2\le\beta

First, $z$ and $w+y$ are balanced. This is because

\left(1-\dfrac{\alpha}{2-\alpha}\right)\alpha+\dfrac{\alpha}{2-\alpha} \le \dfrac{w+y}{x+y} = (1-\rho_1)\rho_2+\rho_1 < (1-\alpha)\dfrac{1}{2-\alpha}+\alpha.

For $\alpha\in(0,1)$ , the expression on the left is always greater than $\alpha$ , while for $\alpha\in(0,1-\sqrt{2}/2]$ , the expression on the right is always no greater than $(1-\alpha)$ .

Next, $w$ and $y$ are balanced. Similarly, consider

\dfrac{y}{w+y} = \dfrac{\rho_1}{(1-\rho_1)\rho_2+\rho_1}.

On the one hand, for every $\alpha\in(0,(3-\sqrt{5})/2)$ ,

\dfrac{y}{w+y} < \dfrac{\alpha}{(1-\alpha)\alpha+\alpha} < 1-\alpha.

On the other hand, for every $\alpha\in(0,1/3)$ , except when deletion occurs and $y=1$ , we have

\rho_1 \ge \min\left\{\dfrac{\alpha}{1+\alpha},\dfrac{2\alpha}{3-\alpha}\right\} = \dfrac{2\alpha}{3-\alpha},

and therefore

\dfrac{y}{w+y} \ge \dfrac{\dfrac{2\alpha}{3-\alpha}}{\left(1-\dfrac{2\alpha}{3-\alpha}\right)\dfrac{1}{2-\alpha}+\dfrac{2\alpha}{3-\alpha}} > \alpha.

Finally, consider the remaining case: deletion with $y=1$ . The most likely case to become unbalanced occurs when $x=\lfloor 2/\alpha\rfloor-2$ and $w=\lfloor\beta x\rfloor$ . The tree can be restored to balance if and only if

\dfrac{1}{1+\lfloor\beta x\rfloor}\ge\alpha \iff \lfloor\beta x\rfloor\le\dfrac{1}{\alpha}-1 \iff \beta x < \dfrac{1}{\alpha} \iff x < \dfrac{2}{\alpha}-1.

And this always holds. This completes the proof for this situation. Note that the proof of the last case uses the fact that weights are always integers, so it cannot be merged into the preceding discussion.

Case 2:

w

is too heavy; double rotation when

\rho_2>\beta

First, $z+u$ and $v+y$ are balanced. This is because

\dfrac{\alpha}{2-\alpha}+\left(1-\dfrac{\alpha}{2-\alpha}\right)\dfrac{1}{2-\alpha}\alpha < \dfrac{z+u}{x+y} = \rho_1+(1-\rho_1)\rho_2\rho_3 <\alpha+(1-\alpha)^3

For $\alpha\in(0,1)$ , the expression on the left is always greater than $\alpha$ , while for $\alpha\in(0,(3-\sqrt{5})/2)$ , the expression on the right is always less than $(1-\alpha)$ .

Next, $z$ and $u$ are balanced. For $\alpha\in(0,1)$ , we always have

\alpha=\dfrac{\dfrac{1}{2-\alpha}\alpha}{1-\dfrac{1}{2-\alpha}(1-\alpha)}<\dfrac{u}{z} = \dfrac{\rho_2(1-\rho_3)}{1-\rho_2\rho_3} <\dfrac{(1-\alpha)^2}{1-(1-\alpha)\alpha} < 1-\alpha.

Finally, $v$ and $y$ are balanced. As in the other cases, consider

\dfrac{y}{v+y} = \dfrac{\rho_1}{\rho_1+(1-\rho_1)\rho_2\rho_3}.

On the one hand, for every $\alpha\in(0,1-\sqrt{2}/2]$ , we have

\dfrac{y}{v+y} < \dfrac{\alpha}{\alpha+(1-\alpha)\dfrac{1}{2-\alpha}\alpha} \le 1-\alpha.

On the other hand,

\dfrac{y}{v+y} \ge \dfrac{\rho_1}{\rho_1+(1-\rho_1)(1-\alpha)^2}.

The expression on the right is no less than $\alpha$ if and only if

\rho_1 \ge \dfrac{\alpha(1-\alpha)}{1+\alpha(1-\alpha)}.

If the imbalance is caused by insertion, then $\rho_1\ge \alpha/(1+\alpha)$ , which clearly holds. Otherwise, the cases are somewhat more complicated:

When $y\ge 3$ , $\rho_1\ge 3\alpha/(4-\alpha)$ , and $3\alpha/(4-\alpha)\ge\alpha(1-\alpha)/(1+\alpha(1-\alpha))$ holds for every $\alpha\in[1-\sqrt{3}/2,1)$ ;
When $y=2$ , the most likely case to become unbalanced occurs when $x=\lfloor 3/\alpha\rfloor-3$ , $w=\lfloor(1-\alpha)x\rfloor$ , and $v=\lfloor(1-\alpha)w\rfloor$ ; in that situation, $v/(v+y)\ge\alpha$ holds for every $\alpha\in(3/22,1)$ ;
When $y=1$ , the most likely case to become unbalanced occurs when $x=\lfloor 2/\alpha\rfloor-2$ , $w=\lfloor(1-\alpha)x\rfloor$ , and $v=\lfloor(1-\alpha)w\rfloor$ ; in that situation, $v/(v+y)\ge\alpha$ holds for every $\alpha\in(2/11,1)$ .

The discussions of the last two cases likewise use the fact that all node weights are integers.

Combining the two cases, when $\alpha\in(2/11,1-\sqrt{2}/2]$ , the above combination of single and double rotations guarantees that the tree remains balanced.

This analysis shows that the most difficult situation for maintaining balance occurs when deleting a node from a small tree. Besides $\beta=1/(2-\alpha)$ , the correctness of other parameter choices can be proved by repeating the process above, with some inequalities adjusted accordingly.

Hirai and Yamamoto later used machine-assisted proof to completely determine the range of all feasible $(\alpha,\beta)$ , obtaining a rather complicated two-dimensional figure:

They recommend the following strategy for maintaining balance:

when $x>3y$ , determine that the tree is unbalanced;
when $w\le 2z$ , choose the single-rotation strategy; otherwise, choose the double-rotation strategy.

The reason is that this is the only strategy in the feasible parameter range that can be expressed with simple integers, thereby avoiding the efficiency loss caused by floating-point arithmetic. Their recommended strategy is equivalent to taking $(\alpha,\beta)=(1/4,2/3)$ . In practice, suitable parameters can be chosen according to the specific situation.

A reference implementation follows:

Reference code

// Check whether a subtree of weight SX is too heavy
//     in a tree of weight SX + SY.
bool too_heavy(int sx, int sy) {
  // or sx > sy * 3;
  return sy < ALPHA * (sx + sy);
}
// Check if ch[x][!r] is too heavy so that a double rotation is needed.
bool need_double_rotation(int x, bool r) {
  // or sz[ch[x][!r]] > sz[ch[x][r]] * 2;
  return sz[ch[x][!r]] > sz[x] / (2 - ALPHA);
}

// Balance the subtree at x;
void balance(int& x) {
  if (sz[x] == 1) return;
  bool r = sz[ch[x][1]] > sz[ch[x][0]];
  if (!too_heavy(sz[ch[x][r]], sz[ch[x][!r]])) return;
  if (need_double_rotation(ch[x][r], r)) {
    rotate(ch[x][r], !r);
  }
  rotate(x, r);
}

Once the balance-maintenance strategy is implemented, the algorithm for merging two trees is very simple. Again let $x>y$ ; the merge strategy is as follows:

if the right subtree $y$ is empty, return the left subtree $x$ directly;
if the left and right subtrees $x$ and $y$ are already balanced, that is, $y\ge\alpha(x+y)$ , join the two subtrees directly;
otherwise, merge $x$ 's right subtree $w$ with $y$ , join the left subtree $z$ with the result, and rebalance the new tree.

A reference implementation follows:

Reference code

// Merge two subtrees.
int merge(int x, int y) {
  if (!x || !y) return x | y;
  int a, b;
  if (too_heavy(sz[x], sz[y])) {
    std::tie(a, b) = cut(x);
    int z = join(a, merge(b, y));
    balance(z);
    return z;
  } else if (too_heavy(sz[y], sz[x])) {
    std::tie(a, b) = cut(y);
    int z = join(merge(x, a), b);
    balance(z);
    return z;
  } else {
    return join(x, y);
  }
}

It can be proved that this maintains the balance of the resulting tree, and that the complexity of the operation is $O(|\log(x/y)|)$ .

Proof of balance and complexity

We only need to consider the case where $y$ is too light, namely $y<\alpha(x+y)$ . First merge $w$ and $y$ , then join $z$ and $w+y$ . We need to prove that adjusting the balance at the root is enough to guarantee that the whole tree is balanced. Suppose the left and right subtrees of $w+y$ are $c$ and $d$ , respectively, and the left and right subtrees of $c$ are $a$ and $b$ , respectively. Adjusting balance at the root has three cases:

Case 1:

z

and

w+y

are already balanced, so no further adjustment is needed; that is,

z\ge\alpha(x+y)

By the definition of balance, the subtrees $z$ and $w+y$ are balanced, and they are also balanced with respect to each other, so the entire tree is balanced.

Case 2:

z

is too light and

c

is not too heavy, so balance can be restored by a single rotation; that is,

z<\alpha(x+y)

and

c\le\beta(w+y)

Since $z$ and $w$ are balanced, but $y$ is too light compared with $x = z+w$ , the weight of subtree $z$ satisfies

\alpha(1-\alpha)(x+y) < \alpha(z+w) \le z \le \alpha(x+y) .

The weight of $c$ satisfies

\alpha(w+y) \le c \le \beta(w+y).

Therefore, $z$ and $c$ are balanced with respect to each other provided that

\dfrac{\alpha}{1-\alpha}<\dfrac{1-\alpha}{\alpha}\alpha<\dfrac{c}{z}=\dfrac{w+y}{z}\dfrac{c}{w+y} < \dfrac{1-\alpha(1-\alpha)}{\alpha(1-\alpha)}\beta\le\dfrac{1-\alpha}{\alpha},

which requires

\beta\le \dfrac{(1-\alpha)^2}{1-\alpha(1-\alpha)}.

Also, $z+c$ and $d$ are balanced with respect to each other provided that

\alpha\le (1-\beta)(1-\alpha)\le \dfrac{d}{w+y}\dfrac{w+y}{x+y} = \dfrac{d}{x+y} < \dfrac{d}{c+d} \le 1-\alpha,

which requires

\beta \le \dfrac{1-2\alpha}{1-\alpha}.

Case 3:

z

is too light and

c

is too heavy, so balance can be restored by a double rotation; that is,

z<\alpha(x+y)

and

c>\beta(w+y)

As in Case 2,

\begin{aligned} \alpha(1-\alpha)(x+y) < z &\le \alpha(x+y),\\ \beta(w+y)<c &\le (1-\alpha)(w+y),\\ \alpha c\le a,b &\le (1-\alpha)c. \end{aligned}

Therefore, $z$ and $a$ are balanced with respect to each other provided that

\dfrac{\alpha}{1-\alpha}\le\dfrac{1-\alpha}{\alpha}\beta\alpha\le\dfrac{a}{z} = \dfrac{w+y}{z}\dfrac{a}{c+d} < \dfrac{1-\alpha(1-\alpha)}{\alpha(1-\alpha)}(1-\alpha)^2,

which requires

\beta\ge\dfrac{\alpha}{(1-\alpha)^2}.

Next, $b$ and $d$ are balanced with respect to each other provided that

\dfrac{\alpha}{1-\alpha}\le\dfrac{\beta}{1-\beta}\alpha \le \dfrac{b}{d} = \dfrac{c}{d}\dfrac{b}{c} \le \dfrac{1-\alpha}{\alpha}(1-\alpha) < \dfrac{1-\alpha}{\alpha},

which requires

\beta\ge\dfrac{1}{2-\alpha}.

Finally, $z+a$ and $b+d$ are balanced with respect to each other provided that

\alpha<(1-\alpha)(1-(1-\alpha)^2)\le\frac{b+d}{x+y} = \dfrac{w+y}{x+y}\dfrac{b+d}{w+y} < (1-\alpha(1-\alpha))(1-\beta\alpha) \le 1-\alpha,

which requires

\beta\ge\dfrac{\alpha}{1-\alpha+\alpha^2}.

Combining the three cases, as long as

0<\alpha\le 1-\dfrac{\sqrt{2}}{2},~\dfrac{1}{2-\alpha}\le\beta\le\dfrac{1-2\alpha}{1-\alpha},

the resulting tree can be adjusted to balance using the combination of single and double rotations. This clearly includes the parameter range given in the main text.

Finally, let us briefly explain why the complexity of this algorithm is $O(|\log(x/y)|)$ . During the merge, if $y$ is too light relative to $x$ , we try to merge it with the right subtree of $x$ . This continues until a subtree rooted at some descendant of $x$ is balanced with $y$ . Since each additional level down reduces the subtree weight by at least a factor of $(1-\alpha)$ , at most $\log_{\frac{1}{1-\alpha}}(x/y)$ iterations are needed to find a subtree balanced with $y$ . Thus this merge algorithm calls the balance algorithm $O(\log n)$ times², and its complexity is also $O(\log n)$ .

Although it is not obvious, this argument relies on the fact that while repeatedly taking the right subtree, $y$ cannot change in one iteration from being too light relative to the left subtree to being too heavy relative to it. This is because the range of subtree weights that can be balanced with $y$ lies between $\alpha y/(1-\alpha)$ and $(1-\alpha)y/\alpha$ . Therefore, if $y$ changed from being too light to $y$ being too heavy in one iteration, the weight of the subtree of $x$ would have to shrink during that iteration to at least $\alpha^2/(1-\alpha)^2$ times its original value. However, in a single iteration, the subtree weight can shrink to at most $\alpha$ times its original value; and in the above range of $\alpha$ , $\alpha>\alpha^2/(1-\alpha)^2$ . This shows that the assumed situation is impossible: after some iteration, $y$ must be balanced with a subtree of $x$ .

Maintenance by Merging

Merging two subtrees means constructing a new tree whose leaf information is exactly the union of the leaf information of the left and right subtrees, while ensuring that every key in the left subtree is no greater than every key in the right subtree and that the tree remains balanced.

For this purpose, use the following strategy³ (again let $x>y$ ):

if the right subtree $y$ is empty, return the left subtree $x$ directly;
if the left and right subtrees $x$ and $y$ are already balanced, that is, $y\ge\alpha(x+y)$ , join the two subtrees directly;
otherwise, the right subtree $y$ is too light, but if $x$ 's left subtree $z$ and $w+y$ can be balanced, that is, $z\ge\alpha(x+y)$ , first merge $w$ and $y$ , then merge $z$ with $w+y$ ;
otherwise, both $z$ and $y$ are too light. First merge $z$ with the left subtree of $w$ , $u$ , then merge the right subtree of $w$ , $v$ , with $y$ , and finally merge the results of the two merges into a new tree.

Comparing this strategy with the balance strategy above, the ways nodes are combined in the latter two cases resemble the results of the single and double balance rotations, respectively; the difference is that joins of subtrees are replaced by merges.

It can be proved that when

0<\alpha \le 1-\dfrac{\sqrt{2}}{2}\approx 0.292

the resulting tree is always balanced, and the complexity of the operation is $O(|\log(x/y)|)$ . In other words, the cost of merging two trees is independent of their absolute sizes and depends only on their relative sizes.

Proof of balance and complexity

Suppose that when merging two subtrees of weights $x$ and $y$ , the number of times the two subtrees must be joined directly is $\tau(x,y)$ . Strictly speaking, we need to prove that when $0<\alpha\le 1-\sqrt{2}/2$ , there is a constant $C>0$ such that for any $x>y>0$ ,

\tau(x,y) \le 1+C\log^+\dfrac{\alpha x}{(1-\alpha)^2y},

where $\log^+ x = \max\{0,\log x\}$ ; moreover, for all $x/y\le(1-\alpha)/\alpha$ , $\tau(x,y)=1$ . In fact, the constant in the expression can be taken as

C = -\dfrac{2}{\log(1-\alpha)}.

This shows that the complexity of the merge algorithm is $O(|\log(x/y)|)$ .

To prove that the tree produced by the merge algorithm is always balanced and that the above complexity bound holds, we use induction. For every lattice point $(x,y)\in\mathbf N^2_+$ in the first quadrant, assign the lexicographic order $(x+y,|x-y|)$ . This is clearly a well-order on the set, so induction can proceed along it. The base case is $(x,y)=(1,1)$ : both subtrees have one leaf node, so directly joining them necessarily produces a balanced subtree, and $\tau(x,y)=1$ , satisfying the bound. Now assume induction has reached $(x,y)$ and that the conclusion holds for every point preceding $(x,y)$ . There are three cases:

Case 1: trees

x

and

y

are balanced, that is,

y\ge\alpha(x+y)

The tree obtained by directly joining them is also balanced, and the tree-join algorithm is called only once, so $\tau(x,y)=1$ .

Case 2: tree

y

is too light but

z

is not too light, that is,

y<\alpha(x+y)\le z

First merge $w$ and $y$ , then merge $z$ and $w+y$ , so

\tau(x,y) = \tau(w,y) + \tau(z,w+y).

By the induction hypothesis, the subtree $w+y$ is already balanced. For the second merge, we can in fact directly prove that $z$ and $w+y$ are balanced:

\alpha \le \dfrac{z}{z+(w+y)} = \dfrac{z}{x+y} < \dfrac{z}{z+w} \le 1-\alpha.

Therefore, merging $z$ and $w+y$ simply joins the two subtrees directly, so $\tau(z,w+y) = 1$ . Thus the resulting tree is also balanced.

We now estimate $\tau(w,y)$ . Since $y>(\alpha/(1-\alpha))x$ and $\alpha x\le w\le(1-\alpha)x$ , scaling gives

\dfrac{\alpha}{1-\alpha}<1-\alpha=\dfrac{\alpha x}{(\alpha/(1-\alpha))x}< \dfrac{w}{y} \le \dfrac{(1-\alpha)x}{y}.

This means that $w$ and $y$ can be unbalanced only when $w>y$ , so

\begin{aligned} \tau(w,y) &\le 1+C\log^+\dfrac{\alpha w}{(1-\alpha)^2y} \le 1+C\log^+\dfrac{\alpha x}{(1-\alpha)y} \\ &= 1 + C\log(1-\alpha) + C\log^+\dfrac{\alpha x}{(1-\alpha)^2y}. \end{aligned}

The last equality holds because $x/y>(1-\alpha)/\alpha$ .

Therefore,

\tau(x,y) \le 2 + C\log(1-\alpha) + C\log^+\dfrac{\alpha x}{(1-\alpha)^2y}.

Case 3: trees

y

and

z

are both too light, that is,

y,z<\alpha(x+y)

First merge $z$ and $u$ , then merge $v$ and $y$ , and finally merge $z+u$ and $v+y$ . Therefore,

\tau(x,y) = \tau(z,u) + \tau(v,y) + \tau(z+u,v+y).

As in the preceding cases, we can estimate the weight ratios of the two subtrees at each merge.

Since $z,y<\alpha(x+y)$ , we have $w>(1-2\alpha)(x+y)$ . At the same time, by the balance condition, $\alpha\le z/x,w/x,u/w,v/w\le 1-\alpha$ . This gives

\begin{aligned} \dfrac{\alpha}{1-\alpha}<\dfrac{\alpha}{1-\alpha}\frac{1}{1-\alpha}\le \dfrac{z}{u} &= \dfrac{z}{w}\dfrac{w}{u} < \dfrac{\alpha}{1-2\alpha}\dfrac{1}{\alpha} \le \dfrac{1-\alpha}{\alpha},\\ \dfrac{\alpha}{1-\alpha}\le\alpha\dfrac{1-2\alpha}{\alpha}< \dfrac{v}{y} &= \dfrac{v}{w}\dfrac{w}{y} \le (1-\alpha)\dfrac{(1-\alpha)x}{y} = (1-\alpha)^2\dfrac{x}{y}. \end{aligned}

For the final term,

\dfrac{z+u}{v+y} = \dfrac{x+y}{v+y}-1 = \dfrac{x+y}{y}\dfrac{y}{v+y} - 1 < (1-\alpha)\left(\dfrac{x}{y}+1\right)-1 < (1-\alpha)\dfrac{x}{y}.

Conversely,

\dfrac{z+u}{v+y} = \dfrac{x+y}{v+y}-1 \ge \dfrac{x+y}{(1-\alpha)^2x+y}-1 > \dfrac{1}{(1-\alpha)^3+\alpha}-1 > \dfrac{\alpha}{1-\alpha}.

These inequalities show that the resulting tree is necessarily balanced. By the induction hypothesis, merging $z$ and $u$ , and merging $v$ and $y$ , both produce balanced trees. Moreover, the first merge, of $z$ and $u$ , is actually a direct join of the two trees. For merging $z+u$ and $v+y$ , there are two subcases:

If $z+u\le v+y$ , their weight ratio is strictly greater than $\alpha/(1-\alpha)$ , so they can be joined directly and the result is balanced;
otherwise, their weight ratio must be strictly less than $x/y$ . But $(z+u)+(v+y)=x+y$ , so $|(z+u)-(v+y)|<|x-y|$ . By the lexicographic ordering given above, the induction hypothesis applies in that situation as well, and the result is balanced.

Applying the induction hypothesis again gives

\begin{aligned} \tau(z,u) &= 1,\\ \tau(v,y) &\le 1+C\log^+\dfrac{\alpha x}{y},\\ \tau(z+u,v+y) &\le 1 + C\log^+\dfrac{\alpha x}{(1-\alpha)y}. \end{aligned}

Adding the three inequalities directly would make the coefficient of the logarithmic term become $2C$ , so the induction could not be completed. A more careful estimate is therefore needed here.

When $\max\{v/y,(z+u)/(v+y)\}\le(1-\alpha)/\alpha$ , at least one of $\tau(v,y)$ and $\tau(z+u,v+y)$ must be $1$ , so

\begin{aligned} \tau(v,y) + \tau(z+u,v+y) &\le 2 + C\log^+\dfrac{\alpha x}{(1-\alpha)y}\\ &= 2 + C\log(1-\alpha) + C\log^+\dfrac{\alpha x}{(1-\alpha)^2y}. \end{aligned}

Otherwise,

\begin{aligned} \tau(v,y) + \tau(z+u,v+y) &\le 2 + C\log^+\dfrac{\alpha v}{(1-\alpha)^2y} + C\log^+\dfrac{\alpha(z+u)}{(1-\alpha)^2(v+y)}\\ &= 2 + C\log\dfrac{\alpha}{(1-\alpha)^2} + C\log^+\dfrac{\alpha v(z+u)}{(1-\alpha)^2y(v+y)}. \end{aligned}

For $0<\alpha\le 1-\sqrt{2}/2$ , we have

\dfrac{\alpha}{(1-\alpha)^2} < 1-\alpha.

Moreover,

\begin{aligned} \dfrac{v(z+u)}{y(v+y)} &= \left(\dfrac{v+y}{y}-1\right)\left(\dfrac{x+y}{y}\dfrac{y}{v+y} - 1\right) \\ &= \dfrac{x+y}{y} + 1 -\dfrac{x+y}{y}\dfrac{y}{v+y}-\dfrac{v+y}{y} < \dfrac{x}{y}. \end{aligned}

Thus, in the latter case as well,

\tau(v,y) + \tau(z+u,v+y) < 2 + C\log(1-\alpha) + C\log^+\dfrac{\alpha x}{(1-\alpha)^2y}.

The overall merge complexity is

\tau(x,y) \le 3 + C\log(1-\alpha) + C\log^+\dfrac{\alpha x}{(1-\alpha)^2y}.

Combining all cases, we have

\tau(x,y) \le 3 + C\log(1-\alpha) + C\log^+\dfrac{\alpha x}{(1-\alpha)^2y}.

Therefore, the induction on complexity is completed by taking $2+C\log(1-\alpha)\le 0$ . An obvious choice is

C = -\dfrac{2}{\log(1-\alpha)}.

This constant means that when two trees are merged, the number of direct subtree joins is roughly no more than twice the difference in their heights.

A reference implementation follows:

Reference code

// Merge two subtrees.
int merge(int x, int y) {
  if (!x || !y) return x | y;
  int a, b, c, d;
  if (too_heavy(sz[x], sz[y])) {
    std::tie(a, b) = cut(x);
    if (too_heavy(sz[b] + sz[y], sz[a])) {
      std::tie(c, d) = cut(b);
      return merge(merge(a, c), merge(d, y));
    } else {
      return merge(a, merge(b, y));
    }
  } else if (too_heavy(sz[y], sz[x])) {
    std::tie(a, b) = cut(y);
    if (too_heavy(sz[a] + sz[x], sz[b])) {
      std::tie(c, d) = cut(a);
      return merge(merge(x, c), merge(d, b));
    } else {
      return merge(merge(x, a), b);
    }
  } else {
    return join(x, y);
  }
}

Using this merge strategy, tree balance can likewise be maintained very easily: whenever the tree is unbalanced, simply merge its left and right subtrees.

Reference code

// Balance the subtree at x;
void balance(int& x) {
  if (sz[x] == 1) return;
  if (too_heavy(sz[ch[x][0]], sz[ch[x][1]]) ||
      too_heavy(sz[ch[x][1]], sz[ch[x][0]])) {
    int a, b;
    std::tie(a, b) = cut(x);
    x = merge(a, b);
  }
}

Because the two trees that need rebalancing are always nearly balanced in size, maintaining balance takes $O(1)$ time.

Basic Balanced-Tree Operations

Using the functions implemented above, a WBLT supports all basic balanced-tree operations. This section uses a multiset as an example to discuss implementing a balanced tree with a WBLT.

Building the Tree

Building the tree is very similar to building a segment tree: recursively split the interval in half until the interval length is $1$ , place the information to be maintained in the leaf node, and combine the interval information while returning from the recursion.

Reference code

// Build the tree for the interval [ll, rr].
int build(int ll, int rr) {
  if (ll == rr) return new_leaf(ll);
  int mm = (ll + rr) / 2;
  return join(build(ll, mm), build(mm + 1, rr));
}

The time complexity is $O(n)$ .

Insertion and Deletion

For insertion, recurse downward from the root until finding the leaf with the smallest key value that is greater than or equal to the key being inserted. Then create two new nodes: one to store the newly inserted value, and the other to serve as the new parent of the two leaves, replacing the position of the selected leaf. Connect the two leaves to this parent. The tree balance must be maintained while returning from the recursion.

As shown in the figure, suppose we want to insert an element with value $4$ into the tree on the left. First find the leaf node with value $5$ , then create leaf node $4$ and the non-leaf node $\text{d}$ , and connect $4$ and $5$ to $\text{d}$ . This produces the tree on the right.

For deletion, consider the reverse of the process above. Find a leaf node whose key value equals the value to be deleted, delete it and its parent, and replace the parent's position with its other child. The tree balance must likewise be maintained while returning from the recursion.

A reference implementation follows:

Reference code

// Insert v to the subtree at x.
void insert(int& x, int v) {
  if (!x) {
    x = new_leaf(v);
  } else if (sz[x] == 1) {
    bool r = v >= val[x];
    ch[x][r] = new_leaf(v);
    ch[x][!r] = new_leaf(val[x]);
    push_up(x);
  } else {
    bool r = v > val[ch[x][0]];
    insert(ch[x][r], v);
    push_up(x);
    balance(x);
  }
}

// Insert v.
void insert(int v) { insert(rt, v); }

// Remove v from the subtree at x.
bool remove(int& x, int v) {
  if (!x) return false;
  if (sz[x] == 1) {
    if (val[x] == v) {
      del_node(x);
      return true;
    } else {
      return false;
    }
  } else {
    bool r = v > val[ch[x][0]];
    bool succ = remove(ch[x][r], v);
    if (!ch[x][r]) {
      x = ch[x][!r];
    } else {
      push_up(x);
      balance(x);
    }
    return succ;
  }
}

// Remove v.
bool remove(int v) { return remove(rt, v); }

Be careful to handle the empty-tree case. If you do not want to handle an empty tree, you can insert an $\infty$ element into the tree in advance.

Both operations have time complexity $O(\log n)$ .

Querying by Rank

Because the shape of a WBLT is very similar to that of a segment tree, rank queries can use a method similar to binary searching on a segment tree: if the maximum value of the left subtree is greater than or equal to the query value, move to the left child; otherwise, move to the right child and add the weight of the left subtree to the answer.

A reference implementation follows:

Reference code

// Count the number of nodes less than v in the subtree at x.
int count_less_than(int x, int v) {
  if (!x) return 0;
  int res = 0;
  while (sz[x] > 1) {
    if (val[ch[x][0]] < v) {
      res += sz[ch[x][0]];
      x = ch[x][1];
    } else {
      x = ch[x][0];
    }
  }
  return res + (val[x] < v ? 1 : 0);
}

// Find the rank of v.
int find_rank(int v) { return count_less_than(rt, v) + 1; }

The time complexity is $O(\log n)$ .

Querying by Rank

This still uses the idea of binary searching on a segment tree, except that the comparison is now based on node weights.

A reference implementation follows:

Reference code

// Find the k-th element in the subtree at x.
// It is guaranteed that such an element exists.
int find_kth(int x, int k) {
  while (sz[x] > 1) {
    if (sz[ch[x][0]] >= k) {
      x = ch[x][0];
    } else {
      k -= sz[ch[x][0]];
      x = ch[x][1];
    }
  }
  return val[x];
}

// Find the k-th element.
int find_kth(int k) { return k > sz[rt] || k <= 0 ? -1 : find_kth(rt, k); }

The time complexity is $O(\log n)$ .

Finding the Predecessor and Successor

The above two operations can be combined.

A reference implementation follows:

Reference implementation

// Find the predecessor of v.
int find_prev(int v) { return find_kth(find_rank(v) - 1); }

// Find the successor of v.
int find_next(int v) { return find_kth(find_rank(v + 1)); }

If you want to implement this directly, note that nodes with equal keys may be stored in multiple leaf nodes.

Splitting

Splitting a WBLT is similar to a non-rotating Treap: the subtree size or weight determines whether the recursion proceeds into the left or right subtree. Unlike a non-rotating Treap, however, WBLT needs to merge the subtrees produced by the split in order to maintain the balance of the final split trees.

A reference implementation for splitting by subtree size follows:

Reference implementation

// Split the subtree at x.
// The left half will have k elements.
std::pair<int, int> split(int x, int k) {
  if (!x) return {0, 0};
  if (!k) return {0, x};
  if (k == sz[x]) return {x, 0};
  int a, b;
  std::tie(a, b) = cut(x);
  if (k <= sz[a]) {
    int ll, rr;
    std::tie(ll, rr) = split(a, k);
    return {ll, merge(rr, b)};
  } else {
    int ll, rr;
    std::tie(ll, rr) = split(b, k - sz[a]);
    return {merge(a, ll), rr};
  }
}

The time complexity is $O(\log n)$ .

Complexity proof

The number of downward recursive levels is clearly no greater than the tree height, which is $O(\log n)$ . What remains to be proved is that merging the subtrees split off on the left and right sides has complexity $O(\log n)$ . We only need to consider the left-side subtree, since the right side is symmetric. Let the subtrees split off on the left side, from bottom to top, be $T_1,T_2,\cdots,T_\ell$ , where their number $\ell\in O(\log n)$ . The merge process can be described as follows: starting from $T'_1=T_1$ , merge $T'_{i-1}$ with $T_i$ to obtain $T'_i$ , recursively merging until all subtrees have been combined. The total complexity of the merge can be written as

\sum_{i=2}^\ell \tau(T_i,T'_{i-1}),

where $\tau(T_i,T'_{i-1})$ is the complexity of merging $T_i$ and $T'_{i-1}$ .

If we always have $w(T_i)\ge w(T'_{i-1})$ , then according to the complexity expression for merging two subtrees,

\tau(T_i,T'_{i-1}) \in O\left(\log\dfrac{w(T_i)}{w(T'_{i-1})}\right) \subseteq O\left(\log\dfrac{w(T'_i)}{w(T'_{i-1})}\right).

Since the constants in these big- $O$ terms are consistent, they can be added directly, and the terms telescope.

However, it should be noted that $w(T_i)\ge w(T'_{i-1})$ does not always hold, because $T'_{i-1}$ is split from the right subtree corresponding to $T_i$ in the original tree, and this right subtree may be larger than the left subtree $T_i$ . Nevertheless, even if $T'_{i-1}$ is larger than $T_i$ , as a part of the right subtree, its weight $w(T'_{i-1})$ does not exceed $(1-\alpha)/\alpha$ times $w(T_i)$ . This means that, in this case, $T'_{i-1}$ and $T_i$ must be balanced, so the merge complexity is $O(1)$ .

Combining these two cases, the complexity of a single merge can be written as

\tau(T_i,T'_{i-1}) \in O\left(\log\dfrac{w(T'_i)}{w(T'_{i-1})}\right) + O(1).

Therefore, the total merge complexity is

O\left(\sum_{i=2}^\ell\left( 1+\log\dfrac{w(T'_i)}{w(T'_{i-1})}\right) \right) \subseteq O(\ell+\log w(T'_\ell)) \subseteq O(\log n).

This also shows that the total complexity of the splitting algorithm is $O(\log n)$ .

Reference Implementation

This article has introduced how to use WBLT to implement the basic operations of a balanced tree. Below is an ordinary balanced tree template implemented with WBLT.

Reference implementation

#include <iostream>
#include <tuple>

// Change here to use different strategies to balance and to merge.
#define BALANCE_BY_ROTATING 1
#define ROTATE_BY_JOINING 0

constexpr int N = 2e6;
constexpr double ALPHA = 0.292;

int id, rt, ch[N][2], sz[N], val[N];
int pool[N], top;

// --8<-- [start:push-up]
void push_up(int x) {
  sz[x] = sz[ch[x][0]] + sz[ch[x][1]];
  val[x] = val[ch[x][1]];
}

// --8<-- [end:push-up]
// --8<-- [start:helper]
// Return a new empty node.
int new_node() {
  int x = top ? pool[--top] : ++id;
  sz[x] = val[x] = ch[x][0] = ch[x][1] = 0;
  return x;
}

// Release a node for later use.
void del_node(int& x) {
  pool[top++] = x;
  x = 0;
}

// Return a new leaf node of value v.
int new_leaf(int v) {
  int x = new_node();
  val[x] = v;
  sz[x] = 1;
  return x;
}

// Return a new node with subtrees x and y.
int join(int x, int y) {
  int z = new_node();
  ch[z][0] = x;
  ch[z][1] = y;
  push_up(z);
  return z;
}

// Return subtrees of x and release x.
auto cut(int& x) {
  int y = ch[x][0];
  int z = ch[x][1];
  del_node(x);
  return std::make_pair(y, z);
}

// --8<-- [end:helper]
// --8<-- [start:too-heavy]
// Check whether a subtree of weight SX is too heavy
//     in a tree of weight SX + SY.
bool too_heavy(int sx, int sy) {
  // or sx > sy * 3;
  return sy < ALPHA * (sx + sy);
}

// --8<-- [end:too-heavy]
#if BALANCE_BY_ROTATING

#if ROTATE_BY_JOINING

// --8<-- [start:rotate-by-joining]
// Rotate the subtree at x such that ch[x][r] is the new root.
void rotate(int& x, bool r) {
  int a, b, c, d;
  std::tie(a, b) = cut(x);
  if (r) {
    std::tie(c, d) = cut(b);
    x = join(join(a, c), d);
  } else {
    std::tie(c, d) = cut(a);
    x = join(c, join(d, b));
  }
}

// --8<-- [end:rotate-by-joining]
#else

// --8<-- [start:rotate-not-by-joining]
// Rotate the subtree at x such that ch[x][r] is the new root.
void rotate(int& x, bool r) {
  int y = ch[x][r];
  ch[x][r] = ch[y][!r];
  ch[y][!r] = x;
  push_up(x);
  push_up(y);
  x = y;
}

// --8<-- [end:rotate-not-by-joining]
#endif

// --8<-- [start:balance]
// Check if ch[x][!r] is too heavy so that a double rotation is needed.
bool need_double_rotation(int x, bool r) {
  // or sz[ch[x][!r]] > sz[ch[x][r]] * 2;
  return sz[ch[x][!r]] > sz[x] / (2 - ALPHA);
}

// Balance the subtree at x;
void balance(int& x) {
  if (sz[x] == 1) return;
  bool r = sz[ch[x][1]] > sz[ch[x][0]];
  if (!too_heavy(sz[ch[x][r]], sz[ch[x][!r]])) return;
  if (need_double_rotation(ch[x][r], r)) {
    rotate(ch[x][r], !r);
  }
  rotate(x, r);
}

// --8<-- [end:balance]
// --8<-- [start:merge-by-balancing]
// Merge two subtrees.
int merge(int x, int y) {
  if (!x || !y) return x | y;
  int a, b;
  if (too_heavy(sz[x], sz[y])) {
    std::tie(a, b) = cut(x);
    int z = join(a, merge(b, y));
    balance(z);
    return z;
  } else if (too_heavy(sz[y], sz[x])) {
    std::tie(a, b) = cut(y);
    int z = join(merge(x, a), b);
    balance(z);
    return z;
  } else {
    return join(x, y);
  }
}

// --8<-- [end:merge-by-balancing]
#else

// --8<-- [start:merge]
// Merge two subtrees.
int merge(int x, int y) {
  if (!x || !y) return x | y;
  int a, b, c, d;
  if (too_heavy(sz[x], sz[y])) {
    std::tie(a, b) = cut(x);
    if (too_heavy(sz[b] + sz[y], sz[a])) {
      std::tie(c, d) = cut(b);
      return merge(merge(a, c), merge(d, y));
    } else {
      return merge(a, merge(b, y));
    }
  } else if (too_heavy(sz[y], sz[x])) {
    std::tie(a, b) = cut(y);
    if (too_heavy(sz[a] + sz[x], sz[b])) {
      std::tie(c, d) = cut(a);
      return merge(merge(x, c), merge(d, b));
    } else {
      return merge(merge(x, a), b);
    }
  } else {
    return join(x, y);
  }
}

// --8<-- [end:merge]
// --8<-- [start:balance-by-merging]
// Balance the subtree at x;
void balance(int& x) {
  if (sz[x] == 1) return;
  if (too_heavy(sz[ch[x][0]], sz[ch[x][1]]) ||
      too_heavy(sz[ch[x][1]], sz[ch[x][0]])) {
    int a, b;
    std::tie(a, b) = cut(x);
    x = merge(a, b);
  }
}

// --8<-- [end:balance-by-merging]
#endif

// --8<-- [start:insert-remove]
// Insert v to the subtree at x.
void insert(int& x, int v) {
  if (!x) {
    x = new_leaf(v);
  } else if (sz[x] == 1) {
    bool r = v >= val[x];
    ch[x][r] = new_leaf(v);
    ch[x][!r] = new_leaf(val[x]);
    push_up(x);
  } else {
    bool r = v > val[ch[x][0]];
    insert(ch[x][r], v);
    push_up(x);
    balance(x);
  }
}

// Insert v.
void insert(int v) { insert(rt, v); }

// Remove v from the subtree at x.
bool remove(int& x, int v) {
  if (!x) return false;
  if (sz[x] == 1) {
    if (val[x] == v) {
      del_node(x);
      return true;
    } else {
      return false;
    }
  } else {
    bool r = v > val[ch[x][0]];
    bool succ = remove(ch[x][r], v);
    if (!ch[x][r]) {
      x = ch[x][!r];
    } else {
      push_up(x);
      balance(x);
    }
    return succ;
  }
}

// Remove v.
bool remove(int v) { return remove(rt, v); }

// --8<-- [end:insert-remove]
// --8<-- [start:rank]
// Count the number of nodes less than v in the subtree at x.
int count_less_than(int x, int v) {
  if (!x) return 0;
  int res = 0;
  while (sz[x] > 1) {
    if (val[ch[x][0]] < v) {
      res += sz[ch[x][0]];
      x = ch[x][1];
    } else {
      x = ch[x][0];
    }
  }
  return res + (val[x] < v ? 1 : 0);
}

// Find the rank of v.
int find_rank(int v) { return count_less_than(rt, v) + 1; }

// --8<-- [end:rank]
// --8<-- [start:kth-element]
// Find the k-th element in the subtree at x.
// It is guaranteed that such an element exists.
int find_kth(int x, int k) {
  while (sz[x] > 1) {
    if (sz[ch[x][0]] >= k) {
      x = ch[x][0];
    } else {
      k -= sz[ch[x][0]];
      x = ch[x][1];
    }
  }
  return val[x];
}

// Find the k-th element.
int find_kth(int k) { return k > sz[rt] || k <= 0 ? -1 : find_kth(rt, k); }

// --8<-- [end:kth-element]
// --8<-- [start:prev-next]
// Find the predecessor of v.
int find_prev(int v) { return find_kth(find_rank(v) - 1); }

// Find the successor of v.
int find_next(int v) { return find_kth(find_rank(v + 1)); }

// --8<-- [end:prev-next]
int main() {
  int n;
  std::cin >> n;
  for (; n; --n) {
    int op, x;
    std::cin >> op >> x;
    switch (op) {
      case 1:
        insert(x);
        break;
      case 2:
        remove(x);
        break;
      case 3:
        std::cout << find_rank(x) << '\n';
        break;
      case 4:
        std::cout << find_kth(x) << '\n';
        break;
      case 5:
        std::cout << find_prev(x) << '\n';
        break;
      case 6:
        std::cout << find_next(x) << '\n';
        break;
    }
  }
  return 0;
}

Using merge and split, it is also possible to implement an implicit balanced tree. Below is an implicit balanced tree template implemented with WBLT; lazy tags need to be pushed down when visiting nodes recursively.

Reference implementation

#include <iostream>
#include <tuple>

// Change here to use different strategies to balance and to merge.
#define BALANCE_BY_ROTATING 0
#define ROTATE_BY_JOINING 1

constexpr int N = 2e5;
constexpr double ALPHA = 0.292;

int id, rt, ch[N][2], sz[N], val[N], lz[N];
int pool[N], top;

void push_up(int x) { sz[x] = sz[ch[x][0]] + sz[ch[x][1]]; }

void lazy_reverse(int x) {
  if (!x) return;
  std::swap(ch[x][0], ch[x][1]);
  lz[x] ^= 1;
}

void push_down(int x) {
  if (lz[x]) {
    lazy_reverse(ch[x][0]);
    lazy_reverse(ch[x][1]);
    lz[x] = 0;
  }
}

// Return a new empty node.
int new_node() {
  int x = top ? pool[--top] : ++id;
  sz[x] = val[x] = ch[x][0] = ch[x][1] = 0;
  return x;
}

// Release a node for later use.
void del_node(int& x) {
  pool[top++] = x;
  x = 0;
}

// Return a new leaf node of value v.
int new_leaf(int v) {
  int x = new_node();
  val[x] = v;
  sz[x] = 1;
  return x;
}

// Return a new node with subtrees x and y.
int join(int x, int y) {
  int z = new_node();
  ch[z][0] = x;
  ch[z][1] = y;
  push_up(z);
  return z;
}

// Return subtrees of x and release x.
auto cut(int& x) {
  push_down(x);
  int y = ch[x][0];
  int z = ch[x][1];
  del_node(x);
  return std::make_pair(y, z);
}

// Check whether a subtree of weight SX is too heavy
//     in a tree of weight SX + SY.
bool too_heavy(int sx, int sy) {
  // or sx > sy * 3;
  return sy < ALPHA * (sx + sy);
}

#if BALANCE_BY_ROTATING

#if ROTATE_BY_JOINING

// Rotate the subtree at x such that ch[x][r] is the new root.
void rotate(int& x, bool r) {
  int a, b, c, d;
  std::tie(a, b) = cut(x);
  if (r) {
    std::tie(c, d) = cut(b);
    x = join(join(a, c), d);
  } else {
    std::tie(c, d) = cut(a);
    x = join(c, join(d, b));
  }
}

#else

// Rotate the subtree at x such that ch[x][r] is the new root.
void rotate(int& x, bool r) {
  int y = ch[x][r];
  ch[x][r] = ch[y][!r];
  ch[y][!r] = x;
  push_up(x);
  push_up(y);
  x = y;
}

#endif

// Check if ch[x][!r] is too heavy so that a double rotation is needed.
bool need_double_rotation(int x, bool r) {
  // or sz[ch[x][!r]] > sz[ch[x][r]] * 2;
  return sz[ch[x][!r]] > sz[x] / (2 - ALPHA);
}

// Balance the subtree at x;
void balance(int& x) {
  if (sz[x] == 1) return;
  push_down(x);
  bool r = sz[ch[x][1]] > sz[ch[x][0]];
  if (!too_heavy(sz[ch[x][r]], sz[ch[x][!r]])) return;
  push_down(ch[x][r]);
  if (need_double_rotation(ch[x][r], r)) {
    push_down(ch[ch[x][r]][!r]);
    rotate(ch[x][r], !r);
  }
  rotate(x, r);
}

// Merge two subtrees.
int merge(int x, int y) {
  if (!x || !y) return x | y;
  int a, b;
  if (too_heavy(sz[x], sz[y])) {
    std::tie(a, b) = cut(x);
    int z = join(a, merge(b, y));
    balance(z);
    return z;
  } else if (too_heavy(sz[y], sz[x])) {
    std::tie(a, b) = cut(y);
    int z = join(merge(x, a), b);
    balance(z);
    return z;
  } else {
    return join(x, y);
  }
}

#else

// Merge two subtrees.
int merge(int x, int y) {
  if (!x || !y) return x | y;
  int a, b, c, d;
  if (too_heavy(sz[x], sz[y])) {
    std::tie(a, b) = cut(x);
    if (too_heavy(sz[b] + sz[y], sz[a])) {
      std::tie(c, d) = cut(b);
      return merge(merge(a, c), merge(d, y));
    } else {
      return merge(a, merge(b, y));
    }
  } else if (too_heavy(sz[y], sz[x])) {
    std::tie(a, b) = cut(y);
    if (too_heavy(sz[a] + sz[x], sz[b])) {
      std::tie(c, d) = cut(a);
      return merge(merge(x, c), merge(d, b));
    } else {
      return merge(merge(x, a), b);
    }
  } else {
    return join(x, y);
  }
}

// Balance the subtree at x;
void balance(int& x) {
  if (sz[x] == 1) return;
  if (too_heavy(sz[ch[x][0]], sz[ch[x][1]]) ||
      too_heavy(sz[ch[x][1]], sz[ch[x][0]])) {
    int a, b;
    std::tie(a, b) = cut(x);
    x = merge(a, b);
  }
}

#endif

// --8<-- [start:split]
// Split the subtree at x.
// The left half will have k elements.
std::pair<int, int> split(int x, int k) {
  if (!x) return {0, 0};
  if (!k) return {0, x};
  if (k == sz[x]) return {x, 0};
  int a, b;
  std::tie(a, b) = cut(x);
  if (k <= sz[a]) {
    int ll, rr;
    std::tie(ll, rr) = split(a, k);
    return {ll, merge(rr, b)};
  } else {
    int ll, rr;
    std::tie(ll, rr) = split(b, k - sz[a]);
    return {merge(a, ll), rr};
  }
}

// --8<-- [end:split]
// Reverse the interval [l, r].
void reverse(int l, int r) {
  int ll, rr;
  std::tie(rt, rr) = split(rt, r);
  std::tie(ll, rt) = split(rt, l - 1);
  lazy_reverse(rt);
  rt = merge(ll, merge(rt, rr));
}

// Output the subtree at x.
void print(int x) {
  if (sz[x] == 1) {
    std::cout << val[x] << ' ';
  } else {
    push_down(x);
    print(ch[x][0]);
    print(ch[x][1]);
  }
}

// Output the tree.
void print() {
  print(rt);
  std::cout << '\n';
}

// --8<-- [start:build]
// Build the tree for the interval [ll, rr].
int build(int ll, int rr) {
  if (ll == rr) return new_leaf(ll);
  int mm = (ll + rr) / 2;
  return join(build(ll, mm), build(mm + 1, rr));
}

// --8<-- [end:build]
int main() {
  int n, m;
  std::cin >> n >> m;
  rt = build(1, n);
  for (; m; --m) {
    int l, r;
    std::cin >> l >> r;
    reverse(l, r);
  }
  print();
  return 0;
}

Note that WBLT requires twice the space. When split and merge are involved, pay attention to garbage collection and promptly reclaim unused nodes; otherwise, the space complexity will not be linear.

References and Notes

Weight-balanced tree - Wikipedia
Nievergelt, J.; Reingold, E. M. (1973). "Binary Search Trees of Bounded Balance". SIAM Journal on Computing. 2: 33–43.
Blum, Norbert; Mehlhorn, Kurt (1980). "On the average number of rebalancing operations in weight-balanced trees". Theoretical Computer Science. 11 (3): 303–320.
Hirai, Y.; Yamamoto, K. (2011). "Balancing weight-balanced trees". Journal of Functional Programming. 21 (3): 287.
Blelloch, Guy E.; Ferizovic, Daniel; Sun, Yihan (2016), "Just Join for Parallel Ordered Sets", Symposium on Parallel Algorithms and Architectures, Proc. of 28th ACM Symp. Parallel Algorithms and Architectures (SPAA 2016), ACM, pp. 253–264.
Straka, Milan. (2011). "Adams’Trees Revisited: Correctness Proof and Efficient Implementation." International Symposium on Trends in Functional Programming. Berlin, Heidelberg: Springer Berlin Heidelberg.

Footnotes

The parameter range $\alpha < 1-\dfrac{\sqrt{2}}{2},~\beta=\dfrac{1-2\alpha}{1-\alpha}$ given in the original paper by Nievergelt and Reingold is incorrect. Hirai and Yamamoto's paper provides a corresponding counterexample. The problem mainly occurs in some very small trees, invalidating the induction proof as a whole. Of course, in actual algorithm competitions, it is difficult to construct data that exposes these incorrect parameters, so there may not be much practical impact. ↩
Since a single balancing operation is equivalent to joining two subtrees at most twice, and one additional call to the subtree-joining algorithm is needed once the two subtrees are already balanced, if we count the number of calls to the subtree-joining algorithm, the constants of the merge operation based on balancing and the direct merge operation described below are the same. ↩
The proof below shows that $z$ and $w+y$ are always balanced in the third case, while $z$ and $u$ are always balanced in the fourth case. They can both be joined directly without merging. ↩