高级数据结构汪一宁 清华大学基本数据结构 易于实现 功能简单，效率一般 优先考虑使用简单数据结构来完成一道试 题。星际争霸 （经典试题） 给出一个无向图，有N个点M条边，N, M 1); N.right = BuildTree(p1)+1, e)线段树：节点数据记录 某一个节点代表一个区间(b, e)上的数据记 录。如果b=e，则这个点是叶子结点；否则 ，这个点有且仅有两个孩子。 节点数据 向上更新型，例如区间上所有元素的和，最小 值，等等 向下更新型，例如该区间是否被反转，线段树：访问机制 Visit(p, b, e): Update Downward If b = p.b and e = p.e: do the visit Else: If b = p.right.b: Visit(p1)+1, MAX(b, p.left.b), e) Update Upward线段树：适用范围 一个区间上的统计信息可以通过其两个子 区间上的信息合并得到。 对一个区间上所有元素的操作可以分解成 对其两个子区间上元素分别的操作。回顾前述试题 修改 不允许插入或者删除元素，但是可以修改任何 一个位置的元素 可以将任何一段区间中的元素反转 要求查询任何一段区间中元素的和 思考 哪些数据需要“向上”维护？ 哪些数据需要“向下”维护？USACO hotel 有N间房间空着，M头奶牛前来入住 每一头奶牛希望订到连续d间房间 如果没有这样的连续d间房间，这头奶牛放 弃入住 否则，分配编号最小的满足条件的连续d间 房间给这头奶牛 N, M = 50,000解题思路 哪些向上更新的数据需要被维护？ 区间中空闲房间总数？ 哪些向下更新的数据需要被维护？ 该区间是否全部被预订 怎样才能够找出连续的d间空闲房间？ 区间左端空闲房间数 区间右端空闲房间数彩球统计 （原创） 有N个彩球排成一列，每个球的颜色是1M 中的一种。 有Q次询问，每次询问一个区间a,b中有多 少种不同颜色的球 N, M, Q = 100,000解题思路 线段树能够维护“区间中的颜色数目”这 一数据么？解题思路 (contd) 离线询问试题 将询问区间按照左端点排序 只维护每种颜色的第一个球 先用链表把每一种颜色的球串起来。 随着询问区间向右移动，在链表上移动指针。 使用线段树来回答询问区间中有多少个每 种颜色的第一个球平衡树 二叉搜索树 一颗中序遍历是升序的二叉树 平衡二叉树 采用某种机制控制二叉树的高度 严格平衡：AVL, 红黑树，SBT 均摊平衡：Splay 期望平衡：Treap 关键操作旋转Treap介绍 每个节点存储一个随机的“优先值” 结构：键值构成二叉搜索树，优先值构成 堆 优势： 旋转方式只有两种，插入删除简单 劣势： 需要多维护一个数据 常数较其他平衡树大Splay介绍 核心思想：任何操作之后（或之前），将 一个节点旋转至根节点。 优势： 思想简单，容易掌握 可以实现一些特殊的统计功能 劣势： 4种旋转，略麻烦 仅保证均摊时间复杂度，一次操作可能耗时很 长，树结构也可能很不好。数列维护(NOI2005) 维护一个数列，支持以下操作： 插入，删除，翻转 查询区间内的元素之和 查询区间内的最大元素解题思路 Splay 怎样在旋转的过程中维护子树的信息？ 怎样取出一个区间？