本书是算法竞赛的入门和进阶教材,包括算法思路、模板代码、知识体系、赛事相关等内容。本书把竞赛常用的知识点和竞赛题结合起来,讲解清晰、透彻,帮助初学者建立自信心,快速从实际问题入手,模仿经典代码解决问题,进入中级学习阶段。 全书分为12章,覆盖了目前算法竞赛中的主要内容,包括算法竞赛概述、算法复杂度、STL和基本数据结构、搜索技术、**数据结构、基础算法思想、动态规划、数学、字符串、图论、计算几何。 本书适合用于高等院校开展的ICPC、CCPC等算法竞赛培训,中学NOI信息学竞赛培训,以及需要学习算法、提高计算思维的计算机工作者。

第5章**数据结构

并查集
二叉树
Treap树
Splay树
线段树
树状数组

竞赛题是对输入的数据进行运算,然后输出结果。因此,编写程序的一个基本问题就是数据处理,包括如何存储输入的数据、如何组织程序中的中间数据等。这个技术就是数据结构。学习数据结构,建立计算思维的基础,是成为合格程序员的基本功。本章讲解一些常用的**数据结构。

数据结构的作用是分析数据、组织数据、存储数据。基本的数据类型有字符和数字,这些数据需要存储在空间中,然后程序按规则读取和处理它们。
数据结构和算法不同,它并不直接解决问题,但是数据结构是算法不可分割的一部分。首先,���据结构把杂乱无章的数据有序地组织起来,逻辑清晰,易于编程处理; 其次,数据结构便于算法**地访问和处理数据,大大减少空间和时间复杂度。
(1) 存储的空间效率。例如一个围棋程序,需要存储棋盘和棋盘上棋子的位置。棋盘可以简单地用一个19×19的二维数组(矩阵)表示。每个棋子是一个坐标,例如W[5][6]表示位于第5行第6列的白棋。这种二维数组是数据结构“图”的一种描述,图是描述点和点之间连接关系的数据结构。棋盘只是一种简单的图,更复杂的图例如地图。地图上有两种元素,即点、点之间直连的道路。地图比棋盘复杂,棋盘的每个点只有上、下、左、右4个相邻的点,而地图上的一个点可能有很多相邻的点。那么如何存储一个地图?可以简单地用一个二维数组,例如有n个点,用一个n×n的二维矩阵表示地图,矩阵上的交叉点(i,j)表示第i点和第j点的连接关系,例如1表示相邻,0表示不相邻。二维矩阵这种数据结构虽然简单、访问速度快,但是用它来存储地图非常浪费空间,因为这是一个稀疏矩阵,其中的交叉点绝大多数等于0,这些等于0的交叉点并不需要存储。一个有10万个点的地图,存储它的二维矩阵大小是100000×100000=10GB。所以,在程序中使用二维矩阵来存储地图是不行的,例如手机上的导航软件,常常有几十万个地点,手机存储卡根本放不下。因此,大地图的存储需要用到更有效率的数据结构,这就是邻接表。
(2) 访问的效率。例如输入一大串个数为n的无序数字,如果直接存储到一个一维数组里面,那么要查找到某个数据,只能一个个试,需要的时间是O(n)。如果先按大小排序然后再查询,处理起来就很有效率。在n个有序的数中找某个数,用折半查找的方法,可以在O(log2n)的时间里找到。
用数据结构存储和处理数据,可以使程序的逻辑更加清晰。
数据结构有以下3个要素
《数据结构与算法分析新视角》,作者周幸妮等,电子工业出版社。。

(1) 数据的逻辑结构: 线性结构(数组、栈、队列、链表)、非线性结构、集合、图等。
(2) 数据的存储结构: 顺序存储(数组)、链式存储、索引存储、散列存储等。
(3) 数据的运算: 初始化、判空、统计、查找、遍历、插入、删除、更新等。
常见的数据结构有数组、链表、栈、队列、树、二叉树、集合、哈希、堆与优先队列、并查集、图、线段树、树状数组等。
在第3章中已经介绍了基本的数据结构
《数据结构(STL框架)》,作者王晓东,清华大学出版社。——栈、队列、链表,本章继续讲解一些常用的**数据结构,包括并查集、二叉树、线段树、树状数组。
5.1并查集
并查集(Disjoint Set)是一种非常精巧而且实用的数据结构,它主要用于处理一些不相交集合的合并问题。经典的例子有连通子图、*小生成树Kruskal算法
参考本书的“10.10.2 kruskal算法”。和*近公共祖先(Lowest Common Ancestors,LCA)等。
通常用“帮派”的例子来说明并查集的应用背景。在一个城市中有n个人,他们分成不同的帮派; 给出一些人的关系,例如1号、2号是朋友,1号、3号也是朋友,那么他们都属于一个帮派; 在分析完所有的朋友关系之后,问有多少帮派,每人属于哪个帮派。给出的n可能是106的。
读者可以先思考暴力的方法以及复杂度。如果用并查集实现,不仅代码很简单,而且复杂度可以达到O(log2n)。
并查集: 将编号分别为1~n的n个对象划分为不相交集合,在每个集合中,选择其中某个元素代表所在集合。在这个集合中,并查集的操作有初始化、合并、查找。

目录 第1章算法竞赛概述 1.1培养杰出程序员的捷径 1.1.1编写大量代码 1.1.2丰富的算法知识 1.1.3计算思维和逻辑思维 1.1.4团队合作精神 1.2算法竞赛与创新能力的培养 1.3算法竞赛入门 1.3.1竞赛语言和训练平台 1.3.2判题和基本的输入与输出 1.3.3测试 1.3.4编码速度 1.3.5模板 1.3.6题目分类 1.3.7代码规范 1.4天赋与勤奋 1.5学习建议 1.6本书的特点 第2章算法复杂度 2.1计算的资源 2.2算法的定义 2.3算法的评估 第3章STL和基本数据结构 3.1容器 3.1.1vector 3.1.2栈和stack 3.1.3队列和queue 3.1.4优先队列和priority_queue 3.1.5链表和list 3.1.6set 3.1.7map 3.2sort() 3.3next_permutation() 第4章搜索技术 4.1递归和排列 4.2子集生成和组合问题 4.3BFS 4.3.1BFS和队列 4.3.2八数码问题和状态图搜索 4.3.3BFS与A*算法 4.3.4双向广搜 4.4DFS 4.4.1DFS和递归 4.4.2回溯与剪枝 4.4.3迭代加深搜索 4.4.4IDA* 4.5小结 第5章**数据结构 5.1并查集 5.2二叉树 5.2.1二叉树的存储 5.2.2二叉树的遍历 5.2.3二叉搜索树 5.2.4Treap树 5.2.5Splay树 5.3线段树 5.3.1线段树的概念 5.3.2点修改 5.3.3离散化 5.3.4区间修改 5.3.5线段树习题 5.4树状数组 5.5小结 第6章基础算法思想 6.1贪心法 6.1.1基本概念 6.1.2常见问题 6.1.3Huffman编码 6.1.4模拟退火 6.1.5习题 6.2分治法 6.2.1归并排序 6.2.2快速排序 6.3减治法 6.4小结 第7章动态规划 7.1基础DP 7.1.1硬币问题 7.1.20/1背包 7.1.3*长公共子序列 7.1.4*长递增子序列 7.1.5基础DP习题 7.2递推与记忆化搜索 7.3区间DP 7.4树形DP 7.5数位DP 7.6状态压缩DP 7.7小结 第8章数学 8.1高精度计算 8.2数论 8.2.1模运算 8.2.2快速幂 8.2.3GCD、LCM 8.2.4扩展欧几里得算法与二元一次方程的整数解 8.2.5同余与逆元 8.2.6素数 8.3组合数学 8.3.1鸽巢原理 8.3.2杨辉三角和二项式系数 8.3.3容斥原理 8.3.4Fibonacci数列 8.3.5母函数 8.3.6特殊计数 8.4概率和数学期望 8.5公平组合游戏 8.5.1巴什游戏与Pposition、Nposition 8.5.2尼姆游戏 8.5.3图游戏与SpragueGrundy函数 8.5.4威佐夫游戏 8.6小结 第9章字符串 9.1字符串的基本操作 9.2字符串哈希 9.3字典树 9.4KMP 9.**C自动机 9.6后缀树和后缀数组 9.6.1概念 9.6.2用倍增法求后缀数组 9.6.3用后缀数组解决经典问题 9.7小结 第10章图论 10.1图的基本概念 10.2图的存储 10.3图的遍历和连通性 10.4拓扑排序 10.5欧拉路 10.6无向图的连通性 10.6.1割点和割边 10.6.2双连通分量 10.7有向图的连通性 10.7.1Kosaraju算法 10.7.2Tarjan算法 10.82SAT问题 10.9*短路 10.9.1FloydWarshall 10.9.2BellmanFord 10.9.3SPFA 10.9.4Dijkstra 10.10*小生成树 10.10.1prim算法 10.10.2kruskal算法 10.11*大流 10.11.1FordFulkerson方法 10.11.2EdmondsKarp算法 10.11.3Dinic算法和ISAP算法 10.12*小割 10.13*小费用*大流 10.14二分图匹配 10.15小结 第11章计算几何 11.1二维几何基础 11.1.1点和向量 11.1.2点积和叉积 11.1.3点和线 11.1.4多边形 11.1.5凸包 11.1.6*近点对 11.1.7旋转卡壳 11.1.8半平面交 11.2圆 11.2.1基本计算 11.2.2*小圆覆盖 11.3三维几何 11.3.1三维点和向量 11.3.2三维点积 11.3.3三维叉积 11.3.4*小球覆盖 11.3.5三维凸包 11.4几何模板 11.5小结 第12章ICPC区域赛真题 12.1ICPC亚洲区域赛(中国大陆)情况 12.2ICPC区域赛题目解析 12.2.1F题Friendship of Frog(hdu 5578) 12.2.2K题Kingdom of Black and White(hdu 5583) 12.2.3L题LCM Walk(hdu 5584) 12.2.4A题An Easy Physics Problem(hdu 5572) 12.2.5B题Binary Tree(hdu 5573) 12.2.6D题Discover Water Tank(hdu 5575) 12.2.7E题Expection of String(hdu 5576) 12.2.8G题Game of Arrays(hdu 5579) 12.2.9I题Infinity Point Sets(hdu 5581) 参考文献