动态序列与动态树问题——浅谈几种常用数据..pdf

动态序列与动态树问题——浅谈几种常用数据 结构 天津南开中学 莫凡 2014 年 6 月 5 日 要 动态序列问题是指给定一个序列，在其上执行一系列在线操作（例 如一段数的修改、某一区间的反转或某一区间内的最大值查询等等）， 是算法竞赛中的常见问题，在生产生活中也具有较强的实用价值。本 文重点通过介绍通过几种常用的平衡二叉树型数据结构解决动态序列 问题。动态树问题是动态序列问题的延伸，支持一棵树（或是一片森 林）的点上、边上信息的维护以及形态的变换。由于动态树问题将维护 的对象由序列拓展成一棵树，故其在图论中具有重要的实用价值。由 于时间仓促，加上作者水平过弱，不足之处请多多指正。 本文涉及的数据结构虽然都非常简单，但是并不适合初学算法与数 据结构的读者，阅读这篇文章的前提条件只有一个：所有涉及的问题 你都可以用暴力实现 作者邮箱：w007878@ 1 Index I 几种常用的数据结构 4 1 线段树 4 1.1 线段树概况 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2 线段树的修改与信息合并 . . . . . . . . . . . . . . . . . . . . 5 1.3 线段树的具体实现与编程细节 . . . . . . . . . . . . . . . . . . 6 1.4 另一种实现方式 . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.5 适用范围 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2 伸展树 9 2.1 平衡树的旋转机制 . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 伸展——Splay 的基本操作. . . . . . . . . . . . . . . . . . . . 9 2.3 懒标记、区间查询和修改 . . . . . . . . . . . . . . . . . . . . 10 2.4 代码实现（C++ ） . . . . . . . . . . . . . . . . . . . . . . . . 11 2.5 优势与弊端 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.6 复杂度分析 . . . . . . . . . . .