TOC
这一章的主要内容其实是如何利用现有的数据结构来扩充成一个新的数据结构，并让这种新的数据结构具有一些神奇的特性。
动态顺序统计
我们在前面就学习了如何在 logn 的时间内在一个有序的数组中找到第 i 小的值，我们当时使用的是随机找个数并进行 left,right 排序，并不断向下递归，接下来我们将了解如何在一颗标准的红黑树之中添加一个哨兵从而实现 logn 时间的搜索。
首先，我们将为一颗红黑树的节点添加一个熟悉，size,size 代表的是一个子节点所拥有的所有子节点数+其自身，即x.size = left.size + right.size + 1,这个 size 我们称之为轶。如果是叶子节点，那么他的轶就是 1。
其实这个轶揭示了一个与顺序统计方法类似的事实，即一个节点的左子树的轶为 x 时，他将会正好是整棵树中第 x + 1 大的节点。
os - select(x, i)
r = x.left.size + 1
if (r === i) return x
if (i < r) return os - select(x.left, i)
else return os - select(x.right, i - r)
伪代码
首先输入 x 代表目前正在查找的节点，i 为需要查找第 i 小的节点，接着找出 r r 其实就是当前节点的轶，接下来通过对比不断递归
维护
试想一下我们该如何维护这个 size,简单来讲，我们只要在插入的时候，在经过任意节点时将经过的节点 size+1。就足以维护这个属性，但是别忘了，这棵树是一个红黑树，这意味修复操作极有可能会破坏我们的 size,所以我们需要在修复的时候去更新 size.
值得庆幸的是树的旋转操作只会破坏其自身的 size,只要重新计算一遍就可以，还是很方便的。
// 对x进行左旋的时候
y.size = x.size
x.size = x.left.size + x.right.size + 1
扩充数据结构的基本步骤（非绝对）
- 选择一种数据结构
- 确定要添加的附加信息
- 检验这个附加信息是否能够在数据更新时正确维护
- 动手去做
区间树
简单介绍了一下利用红黑树扩充成区间树，简单记录一下伪代码。
// t = tree i = 一个区间[i,j]
intervalSearch(t,i)
x = t.root
while(x!=null && i dont have overlap x.int ) // 如果节点不等于null或者未找到匹配 循环继续向下
if(x.left != null && x.left.max >= x.low)
x = x.lfet
else
x = x.right
return x
值得提醒的是，该算法是以 low 点进行排序的。
所以当左子树的 max 都小于 x 的时候，区间只可能出现在右子树。差不多是这样
我其实一开始没想明白的是，用 low 点进行对比的时候，要是这区间一半在左边，一般在右边咋办，仔细一想，这当然找不到啦，本身区间就是完全包含才算搜索到的。