平衡树

平衡树是一种二叉数据结构，满足所谓的“BST 性质”：

1. 空树是 BST；
2. 若 BST 的左子树不为空，则其左子树上所有点的附加权值均小于其根节点的值；
3. 若 BST 的右子树不为空，则其右子树上所有点的附加权值均大于其根节点的值；
4. BST 的左右子树均为 BST；
5. BST 集合是满足 1、2、3、4 的最小二叉树集。

笔者通常使用 FHQ 来实现平衡树。

例题

刷基础 I

[2023 钉耙编程 1] Easy Problem II

Portal。维护权值平衡树，找到比 $x$ 大、小的分别打标记，打完之后依然满足平衡树的性质。用分块来支持区间操作即可。代码。

刷综合

[Ynoi E2015] 人人本着正义之名

Portal.

首先看一看操作 $3\sim 6$ 是个什么东西。

将 $[l,r-1]$ 中的数 $a_i$ 同时变为 $a_i$ 与 $a_{i+1}$ 按位或的值？简单，就是所有极长 $0$ 段最右边一个 $0$ 变成 $1$。

搞一个平衡树，打一个标记表示左右端点的移动量。只有两个问题：

• 如何保证区间极长？区间染色时向左右拓展一下即可。
• 如何保证没有空区间？区间数量是 $O(n+m)$ 的，维护最短 01 区间长度，暴力找，然后将其左右区间合并即可。

本质上不难，但代码比较壮观，需要使用指针实现平衡树进行卡常，代码。