pb_ds优先队列学习笔记

pb_ds库

pb_ds??
平板电视??
pb_ds是G++编译器默认附带的一个扩展库,全称是Policy-Based Data Structures(官方传送门)…
pb_ds库里含有许多数据结构,如HashTable,trie,rb_tree,priority_queue…

SPFA 学习笔记

SPFA

SPFA(Shortest Path Faster Algorithm)(队列优化)算法是求单源最短路径的一种算法,它还有一个重要的功能是判负环(在差分约束系统中会得以体现),在Bellman-ford算法的基础上加上一个队列优化,减少了冗余的松弛操作,是一种高效的最短路算法。

Dijkstra 学习笔记

Dijkstra

迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。

Trie 学习笔记

Trie 树(c++实现)

原理

Trie 树,又称单词查找树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希树高。
详见 Trie 树

树状数组

树状数组求逆序对

树状数组

树状数组(Binary Indexed Tree(BIT), Fenwick Tree) 是一个查询和修改复杂度都为 $O(\log n)$ 的数据结构。主要用于查询任意两位之间的所有元素之和,但是每次只能修改一个元素的值;
经过简单修改可以在 $O(\log n)$ 的复杂度下进行范围修改,但是这时只能查询其中一个元素的值。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×