• 学习笔记

    【模板】ST表

    简介 ST表,稀疏表,用于求解经典的RMQ问题。即区间最值问题。基于倍增思想,利用递推的方式预处理,支持高效的查询,不支持修改 代码 #include <cstdio> #include <cmath&…

  • 学习笔记

    【模板】线段树

    概述 线段树是一种二叉搜索树,用来维护区间内的符合区间加法的值,支持高效的查询与修改操作。每一次操作的时间复杂度是 $O(log_2N)$ 原理 线段树把区间 $[l,r]$ 成了 $[l,mid]$ 与 $[mid+1…

  • 学习笔记

    【模板】01背包

    $f[i]$表示背包已用i容量时能得到的最大价值,value[i]表示第i个物体的价值,size[i]表示第i个物品所要占据的背包容量(或者说是重量、时间之类的)。那么我们的决策就是要不要把当前处理的物品放入背包中。我们…

  • 学习笔记

    Dijsktra算法

    Dijkstra算法是一种用于求最短路径的算法,用于求一个节点到其他所有节点的最短路径。与其他的最短路径算法一样,都采用松弛操作,并且运用了贪心的思想。适用于处理不存在负边权的稀疏图,算法的时间复杂度为 $O(N^2)$…

  • 学习笔记

    【模板】SPFA算法

    SPFA算法是Bellman-Ford(蛤?你说你不知道Bellman-Ford算法?)算法的队列实现方法,采取动态逼近的方式来求得单源最短路,时间复杂度为O(ek)e为边数,k是所有点进队的平均次数。适用于不存在负权回…