后缀数组及SA-IS算法学习笔记

定义

字符串

字符串 $s$ 连续的一段字符组成的串叫做字符串,更广义地,任何一个由可比较大小的元素组成的数组都可称为字符串。字符串的下标从 $0$ 开始,长度为 $length(s)$。

后缀

后缀:$suffix(i)$ 表示字符串 $s$ 从第 $i$ 个位置开始的后缀,即由 $s[i]$ ~ $s[n - 1]$ 组成的子串。

Splay 学习笔记

Splay Tree(伸展树)是一种自平衡二叉排序树,可以在均摊 $O({\log} n)$ 的时间内完成基于 Splay(伸展)操作的修改与查询。

替罪羊树学习笔记[模板]

替罪羊树学习总结[模板]

传说中效率极高且较为好写的平衡树(抛开丧心病狂的红黑树和veb树),替罪羊树写法相当暴力,不用旋转,它只会选择性地重新构树来保证复杂度。

树链剖分学习总结

树链剖分学习总结

如果要在一棵树上进行路径的修改,求极值,求和,似乎线段树即可完成,实际上只用线段树并不能很好的做到,只有用一种高级的东西——树链剖分

概念

树链,就是树上的路径。剖分,就是把路径分类为重链轻链
size[v]表示以v为根的子树的节点数,depth[v]表示v的深度(根深度为1),top[v]表示v所在的链的顶端节点,father[v]表示v的父亲,son[v]表示与v在同一重链上的v的儿子节点(姑且称为重儿子),w[v]表示v与其父亲节点的连边(姑且称为v的父边)在线段树中的位置。只要把这些东西求出来,就能用$O(logn)$的时间完成原问题中的操作。

树上操作总结

树上操作学习总结

储存

用邻接表储存。

1
2
3
4
5
6
7
8
9
10
const int MAXN = 10010;
struct Node {
int v, w;
Node(int v, int w) : v(v), w(w) {}
};
vector<Node> edge[MAXN];
inline void addEdge(int u, int v, int w) {
edge[u].push_back(Node(v, w));
edge[v].push_back(Node(u, v));
}

KMP 算法学习笔记

KMP算法学习总结

KMP(Knuth-Morris-Pratt)是一种改进的字符串匹配算法,也是算法竞赛中常用的字符串匹配算法之一,它可以有效地利用失配信息来使得匹配全过程中不回溯,从而在线性时间内完成匹配。

字符串 Hash 学习总结

字符串Hash学习总结

定义

字符串Hash简单来说就是:把字符串有效地转换为一个整数

Hash函数

就是使得每一个字符串都能够映射到某一个整数上的函数

A*算法学习笔记

A*算法学习总结

引入

假设有人想从A点移动到一墙之隔的B点,如下图,绿色的是起点A,红色是终点B,蓝色方块是中间的墙。
A*算法

简化搜索区域

如上图,搜索区域已经划分成了方格,像这样简化搜索区域,是寻路的第一步。这一方法将搜索区域简化成了二位数组(基本的图论模型),数组的每一个元素是是网格的一个方块,方块被标记为可通过的和不可通过的。路径被描述为从st我们经过的方块的集合。一旦路径被找到,我们的人就从一个方格的中心走向另一个,直到到达目的地。

博弈论学习笔记

博弈论学习总结

Nim游戏

Nim游戏就是经典的取石子游戏,规则如下:
桌子上有 N 堆石子,游戏者轮流取石子。每次只能从一堆中取出任意数目的石子,但不能不取。 取走最后一个石子者胜。

结论:对于一个nim游戏局面($a_1,a_2, \cdots ,a_n$),若$a_1$ ^ $a_2$ ^ \cdots ^ $a_n = 0$ 则先手必败。

数位dp学习总结「模板」

数位dp模板,记忆化搜索,dp[pos][pre][status]。
不要62【hdu】为例

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

×