亲身经历，方知震撼与圆满。

最短路径

原文oi wiki:SP

基础

1.Dijkstra
2.Floyd

1.Dijkstra

用于求 单源最短路径，只能处理非负权边。其核心思想是： 每次从未确定的点中选择当前距离源点最近的点加入集合，并用它来更新其他点的最短距离。 原理十分简单，大学课堂100%讲过 堆优化 Dijkstra 时间复杂度为 O((n + m)log n),适用于稀疏图

线段树

原文oi wiki:SegTree

简述

线段树（Segment Tree）是一种二叉树结构，主要用于高效地维护区间信息，例如区间和、区间最值、区间最大公约数等等。

你可以把它当作一个比树状数组（Binary Indexed Tree）更万能的数据结构，因为它不仅支持单点修改和区间查询，还可以通过扩展支持区间修改、区间最值查询等操作。

原文oi wiki:string

后缀

后缀是指从某个位置 i 开始到整个串末尾结束的一个特殊子串。字符串 S 的从 i 开头的后缀表示为 $Suffix(S, i)$，也就是 $Suffix(S, i) = S[i..|S|-1]$。