什么是 Order Statistic Tree，它如何支持第 K 小和排名查询？

简化版

Order Statistic Tree 是在平衡二叉搜索树节点上额外维护 size 字段的增强结构，size 表示当前节点子树的节点数。查第 K 小时看左子树大小 L：如果 k == L + 1，当前节点就是答案；如果 k <= L，去左子树；否则去右子树找第 k - L - 1 小。插入、删除和旋转时同步维护 size。

详细版

普通 BST 能按值搜索，但不能直接回答“第 K 小是谁”或“某个值排名第几”。Order Statistic Tree 在 AVL、红黑树等平衡树基础上加一个子树规模字段，让每个节点知道左边有多少个元素。这样排名问题就能沿搜索路径逐层缩小，而不用中序遍历整棵树。

查第 K 小时，设 L = size(node.left)。如果 K 等于 L + 1，说明左边正好有 L 个更小元素，当前节点排名第 K；如果 K 更小，答案在左边；如果 K 更大，答案在右边，且右边要找的排名变成 K - L - 1。查 rank 时也类似：向右走时把左子树规模和当前节点一起累加。只要底层平衡树高度是 O(log n)，这些查询就是 O(log n)。

完整版教学

一、为什么普通平衡树还不够

AVL 和红黑树能保证搜索、插入、删除是 O(log n)，但它们默认只按 key 查找。例如你问“第 100 小的元素是谁”，普通树不知道每个子树里有多少节点，只能做中序遍历数到第 100 个。数据量是 100000 时，如果频繁查第 K 小，这个代价就不划算。

普通 BST:
  search(value) -> O(log n) 平衡时
  kth(k)        -> 中序数数，最坏 O(n)

Order Statistic Tree:
  search(value) -> O(log n)
  kth(k)        -> O(log n)
  rank(value)   -> O(log n)

增强的核心很小：每个节点多维护一个 size，但它让树从“按值查找”升级成“按排名查找”。

二、size 字段的语义

size(node) 表示以 node 为根的整棵子树有多少个节点。空子树 size 为 0，叶子节点 size 为 1。维护公式非常简单：

size(node) = size(node.left) + size(node.right) + 1

例如下面这棵树中，节点 5 的左子树有 3 个节点，右子树有 2 个节点，所以 size(5)=6。

        5(size=6)
       /         \
  2(size=3)    8(size=2)
   /   \          /
  1     3        7

有了左子树大小，就知道当前节点在当前子树中的排名是 size(left) + 1。这就是第 K 小查询的根本依据。

三、第 K 小查询怎么走

设 L = size(node.left)，当前节点左边有 L 个更小的元素。若 k == L + 1，当前节点就是第 K 小；若 k <= L，第 K 小还在左子树；若 k > L + 1，要去右子树找第 k - L - 1 小，因为左子树和当前节点已经占掉 L + 1 个名额。

当前判断	说明	下一步
`k == L + 1`	当前节点排名正好是 k	返回当前节点
`k <= L`	第 k 小在左子树	去左边，k 不变
`k > L + 1`	第 k 小在右子树	去右边，k 减去 `L + 1`

找第 5 小:
node=5, L=3，L+1=4，k=5 > 4
去右子树找第 5-4=1 小
node=8, L=1，L+1=2，k=1 <= 1
去左子树找第 1 小
node=7, L=0，L+1=1，命中 7

这个例子说明 k 会随着向右走而改变。忘记减掉左子树和当前节点，是最常见的 off-by-one 错误。

四、rank 查询如何累加

rank 查询是反过来问“某个值是第几小”。从根向下搜索 value：如果 value 小于当前节点，就去左边，排名不增加；如果 value 大于当前节点，说明当前节点左子树和当前节点都比 value 小，要把 size(left) + 1 加到答案里，再去右边；如果命中当前节点，再加上左子树大小和 1。

int rank(TreeNode root, int value) {
    int ans = 0;
    TreeNode cur = root;
    while (cur != null) {
        int leftSize = size(cur.left);
        if (value < cur.val) {
            cur = cur.left;
        } else if (value > cur.val) {
            ans += leftSize + 1;
            cur = cur.right;
        } else {
            return ans + leftSize + 1;
        }
    }
    return -1;
}

如果树允许重复值，rank 定义会更复杂：是第一个等于 value 的排名，还是最后一个等于 value 的排名，或者返回区间排名。面试中要主动确认这个约定。

五、旋转时为什么必须维护 size

Order Statistic Tree 通常基于 AVL 或红黑树。插入删除会触发旋转，旋转改变局部父子关系，因此 size 也必须更新。只更新插入路径、不更新旋转后的两个节点，会让第 K 小和 rank 全部错掉。

右旋前:
      y
     /
    x
     \
      T2

右旋后:
    x
     \
      y
     /
    T2

右旋后要先更新 y，再更新 x：

size(y) = size(T2) + size(y.right) + 1
size(x) = size(x.left) + size(y) + 1

顺序很重要，因为 x 的 size 依赖新的 y 的 size。这个细节是工程实现里最容易出错的地方。

六、常见误区与追问

记忆钩子：第 K 小看左子树大小，向右走时 K 要扣掉左边和自己。

误区：有了平衡树就天然支持第 K 小 O(log n)。 普通平衡树只保证按值搜索快，不维护子树规模就无法按排名跳转。
误区：size 只在插入删除路径上更新即可。 旋转会改变局部子树归属，旋转相关节点也必须重新计算 size。
误区：向右查第 K 小时 k 不需要变化。 左子树和当前节点已经被排除，必须查第 k - L - 1 小。
追问：重复值怎么处理？ 可以在节点上维护 count 表示重复次数，公式变为 size = left + right + count。
追问：复杂度为什么是 O(log n)？ 每次只走一层，底层 AVL 或红黑树保证高度 O(log n)。
追问：它和 Fenwick Tree 有什么区别？ Fenwick Tree 适合离散下标和前缀频次，Order Statistic Tree 更适合动态有序 key。

七、加强记忆

Order Statistic Tree 的关键是给平衡 BST 加一个 size 字段，让每个节点知道“左边有多少人”。查第 K 小时，左子树大小 L 决定当前节点排名是 L + 1；向左走 k 不变，向右走 k 要减掉 L + 1。查 rank 时，向右走就累计左子树和当前节点。真正实现时别忘了插入、删除、旋转都要维护 size，否则树形仍然平衡，但排名答案会悄悄错。

简化版

详细版