什么是增强型平衡树？如何在平衡树上维护额外信息？

简化版

增强型平衡树是在 AVL、红黑树等平衡 BST 节点上额外维护信息，如 size、sum、maxEnd。关键原则是：额外字段必须能由当前节点和左右子树字段 O(1) 重新计算，并且每次插入、删除、旋转后都要更新。

详细版

常见增强字段：

size：子树节点数，支持第 K 小和排名；
sum：子树 key 或 value 总和，支持区间求和；
maxEnd：区间树中子树最大右端点，支持区间重叠查询；
min/max：支持快速范围判断。

增强平衡树的设计要点：

字段能从左右孩子汇总；
普通 BST 操作后沿路径更新；
旋转后按自底向上顺序重算受影响节点；
不让额外字段破坏原平衡规则。

它本质是把平衡树从「有序集合」扩展为支持更复杂查询的动态索引。

完整版教学

一、为什么需要增强平衡树

普通平衡 BST 擅长查找、插入、删除、前驱后继，复杂度 O(log n)。但很多业务不只问某个 key 是否存在，还会问排名、区间和、区间是否重叠、某范围内有多少元素。若每次都临时遍历子树，复杂度会退化。

增强型平衡树的思路是在节点上多存一些可维护的摘要信息。只要这些信息能随结构变化快速更新，就能把很多查询从 O(n) 降到 O(log n)。

记忆钩子：增强字段像给每棵子树贴一张统计标签，旋转搬家后标签必须重算。

二、什么字段适合增强

适合增强的字段通常满足「局部可合并」。也就是说，一个节点的字段可以由 node 自身、left 字段和 right 字段算出来。例如：

size(node) = 1 + size(left) + size(right)
sum(node)  = value(node) + sum(left) + sum(right)
maxEnd(node) = max(end(node), maxEnd(left), maxEnd(right))

如果一个字段依赖整棵树中复杂的外部状态，就不适合直接作为节点增强字段。局部可重算是旋转后仍能维护正确性的根基。

三、旋转后为什么必须更新增强字段

旋转会改变两个或三个节点的子树归属。虽然中序顺序不变，但某个节点覆盖的子树范围变了，它的 size/sum/maxEnd 也会变。如果只改指针不改字段，后续查询会使用过期信息。

以左旋为例：

    x              y
     \            /
      y    =>    x
     /            \
    B              B

旋转后要先更新 x，再更新 y。因为 y 的新字段依赖 x 的新字段。顺序反了，y 可能读到旧的 x.size。

四、代码模式怎么写

工程里通常写一个统一的 pull 或 maintain 函数，用于从孩子重算当前节点字段。所有插入、删除、旋转结束后都调用它。

void pull(Node x) {
    x.size = 1 + size(x.left) + size(x.right);
    x.sum = x.value + sum(x.left) + sum(x.right);
}

Node rotateLeft(Node x) {
    Node y = x.right;
    x.right = y.left;
    y.left = x;
    pull(x);
    pull(y);
    return y;
}

把字段维护集中到 pull，能减少漏更新概率。不要在各处手写重复计算，越写越容易漏。

五、增强字段和查询如何配合

以第 K 小为例，size 字段让我们知道左子树里有多少元素。以区间和为例，如果再维护前缀式拆分或支持按 key 分裂，就可以用子树 sum 快速得到范围总和。以区间树为例，maxEnd 可以判断左子树是否可能存在与查询区间重叠的区间。

增强字段	支持能力	查询收益
size	第 K 小、排名	O(log n)
sum	动态区间求和	O(log n) 级别
maxEnd	区间重叠查询	剪枝搜索
min/max	范围判断	快速剪枝

增强字段的价值在于「查询时少走不必要的路」。

六、和线段树、树状数组的区别

增强平衡树适合动态 key 集合，key 可以稀疏、可插可删。线段树和树状数组更适合下标范围固定或可离散化的场景。比如订单价格动态插入删除并查排名，平衡树更自然；数组下标区间频繁加减求和，线段树更直接。

选择数据结构时要看操作模型。若 key 空间巨大且动态变化，增强平衡 BST 的灵活性很高；若下标连续且更新模式规律，专用区间结构常数更好。

七、常见误区与追问

误区：增强字段只在插入删除时更新即可。 旋转也会改变子树归属，必须更新。
追问：什么字段适合挂在节点上？ 能由当前节点和左右子树 O(1) 合并得到的字段。
误区：增强字段会改变 BST 有序性。 它只是附加摘要，不改变 key 的搜索规则。
追问：旋转后更新顺序是什么？ 先更新下沉的旧根，再更新上升的新根。
误区：增强平衡树能替代所有区间结构。 它适合动态有序集合，不一定比线段树适合固定数组区间更新。

八、加强记忆

增强型平衡树可以记成「平衡 BST + 子树统计标签」。字段必须局部可合并，操作后必须重算，旋转后尤其要按依赖顺序更新。它把平衡树从简单有序集合扩展成动态索引，能支持排名、区间和、区间重叠等更复杂查询。设计时先问字段能不能由左右孩子合并，不能就要换思路。

简化版

详细版