Question

1.动态顺序统计

动态顺序统计是指，在一个动态的无序的集合中，任意的顺序统计量都可以在 O(lgn) 时间内确定。

2.基础数组结构

红黑树，每个树结点的域包括：key[x]，color[x]，left[x]，right[x]

3.附加信息

size[x]：以结点 x 为根的子树的内部结点（包括 x）数，即子树的大小。

如果定义哨兵 nil，则 size[nil[T]]为 0

size[x] = size[left[x]] + size[right[x]] + 1

4.对信息的维护

（1）插入操作：

第一个阶段，即从根开始，沿树下降，将新结点插入为某个已有结点的孩子，这一阶段的维护方法是对路径上每个结点的 size 都+1，时间是 O(lgn)

第二个阶段，即沿树上升，做一些颜色修改和旋转以保持红黑性质，例如 LEFT-ROTATE(T, x)，维护方法是 size[y]<-size[x]，size[x]<-size[left[x]] + size[right[x]] + 1，由于至多旋转两次，时间是 O(1)

（2）删除操作：

第一阶段，即对查找树进行操作，维护方法是对路径上每个结点的 size 都-1，时间是 O(lgn)

第二阶段到多做三次旋转，维护方式与上面相同，时间是 O(1)

5.设计新的操作

OS-SELECT(x, i)：找出顺序统计树 T 中的第 i 小关键字，时间为 O(lgn)

OS-RANK(T, x)：给定指向一顺序统计树 T 中结点 x 的指针，返回对 T 进行中序遍历后得到 的线性序中 x 的位置，时间为 O(lgn)