【读书笔记】数据结构与算法之美 第7章 跳表、并查集、线段树和树状数组
《数据结构与算法之美》，王争 著
标签：数据结构、算法
第7章 跳表、并查集、线段树和树状数组
一、跳表
这一部分介绍了
跳表的由来
用跳表查询到底有多快
跳表是不是浪费内存
高效插入和删除
跳表索引动态更新
跳表的应用：为什么Redis的有序集合用跳表而非红黑树来实现
笔记：跳表是一种动态数据结构，各种基本操作的性能是不错的，但是，这个数据结构比较新，很多编程语言没有封装，开发者要使用跳表要自己从零开始实现。
二、并查集
这一部分介绍了
并查集的由来
基于链表的思路实现并查集
基于树的思路实现并查集
笔记：作者通过用不同的数据结构来实现并查集，这种组织方式对学习者有效
三、线段树
这一部分介绍了
区间统计问题（统计某个区间的数据个数）：使用线段树求解
线段树的其他应用：统计某个区间的数据之和、最大值和最小值、以及某个区间的第K大值
笔记：区间统计问题，是很多编程比赛经常出现的问题，实际工程中也有很多应用。当然，实现线段树还是需要一定的编程能力的。
四、树状数组
这一部分介绍了
前缀和问题
树状数组和线段树的对比
如何用树状数组实现一个高性能】低延迟的实时排行榜
笔记：所有可以用树状数组来解决的问题都可以用线段树来解决。但是如果能用树状数组来解决，代码会更加简单，空间消耗更少。
这一章介绍的跳表、并查集、线段树和树状数组属于比较高级的数据结构，所谓高级，其实就是一般数据结构教材和课程是没有、不讲也不考的。而且，这类数据结构一般不常用，只是在某些特定问题和特殊需求时有奇效。
跳表是基于有序链表、添加多级索引构建而成，支持快速的查找、插入、删除数据操作。除此之外，跳表还支持快速地查找落在某个区间的数据。
并查集主要用来根据两两对象之间的直接关系，快速查询任意两个对象之间是否存在直接或间接的关系。
线段树主要用来做区间统计，比如统计落在某个数值区间的数据个数。
树状数组主要用于求动态数据集合的前缀和。
