数据结构与算法 (8)

该文章描述了如今比较常用的数据结构-跳表，在leveldb、redis等项目中都能看到其身影。跳表数据结构由美国计算机科学家William Pugh 在《Skip Lists: A Probabilistic Alternative to Balanced Trees》（1990）[^1]中发表。因此理论部分主要根据这篇论文，实现为标准链表C++实现。

介绍 Bellman-Ford 的松弛过程、路径恢复、边数限制，以及 SPFA 的队列优化和负环检测。

介绍有向无环图的拓扑排序，分别使用 DFS 和 Kahn 算法实现，并说明如何检测有向环。

介绍 LIS 和 LCS 的动态规划、路径恢复、复杂度优化，以及严格递增序列的二分模板。

介绍摩尔投票算法查找出现次数超过一半的多数元素，并比较随机抽样方法与一般众数问题的区别。

介绍树状数组的 lowbit 原理、单点修改、前缀和查询，以及使用树状数组统计逆序对。

介绍多项式滚动哈希、前缀哈希、子串哈希的 O(1) 计算，以及哈希冲突的处理方式。

总结一维和二维前缀和、差分数组的定义、区间查询与区间修改模板。