type
status
date
slug
summary
tags
category
icon
password
快速
矩阵快速幂
欧几里得求最大公约数
拓展欧几里得
扩展欧几里得算法可以在求得 ， 的最大公约数的同时，找到整数 ，（其中一个可能是负数），使它们满足 。如果 是负数，可以把问题转化成 ，然后令 。
拓扑排序
树状数组
单点修改与区间查询
树状数组区间修改与单点查询
我们用树状数组保存差分即可实现区间修改。
另一个写法是树状数组存相邻个两数之间的差值，在此不做演示。
二维树状数组
二维树状数组差分
由二维差分的知识可知，我们需要维护四个数组。
逆序对
线段树
tire树
质数筛法
筛法求欧拉函数
最短路
Floyd 算法
适用于任何图，不管有向无向，边权正负，但是最短路必须存在。（不能有个负环）
Bellman–Ford 算法
Bellman–Ford 算法是一种基于松弛（relax）操作的最短路算法，可以求出有负权的图的最短路，并可以对最短路不存在的情况进行判断。
队列优化：SPFA
SPFA 也可以用于判断 点是否能抵达一个负环，只需记录最短路经过了多少条边，当经过了至少 条边时，说明 点可以抵达一个负环。
虽然在大多数情况下 SPFA 跑得很快，但其最坏情况下的时间复杂度为 ，将其卡到这个复杂度也是不难的，所以考试时要谨慎使用（在没有负权边时最好使用 Dijkstra 算法，在有负权边且题目中的图没有特殊性质时，若 SPFA 是标算的一部分，题目不应当给出 Bellman–Ford 算法无法通过的数据范围）。
Dijkstra 算法
在 所有边权值非负 的前提下，Dijkstra 算法是正确的。
不能检测负环。
Johnson 全源最短路径算法
Johnson 和 Floyd 一样，是一种能求出无负环图上任意两点间最短路径的算法。
- Author:Serendipity
- URL:https://serendipity565.netlify.app//article/%E6%9D%BF%E5%AD%90
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!