0x47总结与练习

本章讲解了并查集、树状数组、线段树、分块、点分治、二叉查找树与平衡树等数据结构知识。这些数据结构大多是位运算、递归、分治、倍增等基本算法在树上的进阶应用。除了熟练掌握这些数据结构的模板之外，读者更应该多加留意它们如何在各种实际情境下解决问题。

$\spadesuit$ 本章知识点

并查集

并查集的基本实现与应用，路径压缩

并查集对传递性关系的维护，扩展域并查集，边带权并查集

树状数组

支持单点增加、区间和查询的树状数组

支持区间增加、单点查询的树状数组

支持区间增加、区间和查询的树状数组

树状数组的应用，求逆序对、实时维护01序列中的第 $k$ 个1

线段树

支持单点修改、区间查询的线段树

线段树延迟标记，支持区间修改、区间查询

扫描线思想，线段树维护扫描线

分块

分块的“大段维护、局部朴素”思想

两种常见的分块形式，在线求区间众数

离线对询问进行分块的算法

点分治

点分治框架，以树的重心为根防止退化

两种常见的子树统计方法：树上直接统计、指针扫描数组

二叉查找树与平衡树初步

BST的实现与基本操作

平衡树初步：单旋转的概念，Treap的实现与基本操作，*Splay

练习

1. 完成本章中所有例题的代码实现（标有*的题目选做）

2. 关押罪犯

题目地址：NOIP2010/CODEVS1069，提示：并查集/扩展域或边带权
3. Rochambeau
题目地址：POJ2912，提示：并查集/扩展域或边带权
4. True Liars
题目地址：POJ1417，提示：并查集+背包 (0x52节)
5. Buy Tickets
题目地址：POJ2828，提示：树状数组
6.Hotel
题目地址：POJ3667，提示：线段树/延迟标记
7. Picture
题目地址：IOI1998/POJ1177，提示：扫描线

8.*作诗

题目地址：BZOJ2821，提示：分块

9. Race

题目地址：IOI2011/BZOJ2599，提示：点分治

10.营业额统计

题目地址：BZOJ1588，提示：平衡树/Treap

11. *SuperMemo

题目地址：POJ3580，提示：平衡树/Splay