Question

1.区间树

区间树中一种对动态集合进行维护的红黑树，该集合中的每个元素 x 都包含一个区间 int[x]

2.基础数据结构

红黑树，其中每个结点 x 包含一个区间域 int[x]，x 的关键字为区间的低端点

3.附加信息

max[x]：以 x 为根的子树中所有区间的 端点的最大值

4.对信息的维护

max[x] = max(high[int[x]], max[left[x]], max[right[x]])

5.设计新的操作

INTERVAL-SEARCH(T, i)：找出树 T 中覆盖区间 i 的那个结点。