–2022.2.18更新树状数组维护区间最值 树状数组维护区间和/最值假设给定我们一个数组，让我们进行单点修改和区间查询操作，则需要O（1）和O（n）的时间复杂度，多次修改查询的总复杂度最坏为O（n^2），而用树状数组进行这些操作的时间复杂

常用C++STL向量（vector）容器变长数组，使用倍增的思想。 初始化vector <int> a; // 普通初始化 vector <int> a(10); // 定义长度 vector <int>

二部图（二分图）什么是二分图对于一个无向图G=(V,E)，如果将顶点V分隔为两个互不相交的子集（A,B），且图中的每条边（i，j）所关联的两个顶点分别属于两个不同的顶点集（i in A，j in B），则称图G为一个二分图。 二分图有一个

堆堆的结构：一颗完全二叉树（十分平衡，除最后一层（叶结点）以外，其他节点均非空，最后一层从左到右依次排布）。 小根堆也指最小堆。经过排序的完全二叉树，其中每一个非终端节点均小于其左右子节点，其根节点为所有元素的最小值。 大根堆同理。 存储方

最小生成树什么是最小生成树？设定一个n点m条边的无向图G=(V,E)，V表示图中点的集合，E表示图中边的集合，n=|V|，m=|E|。 由V中的n个顶点和E中的n-1条边构成的无向连通子图成为G的一棵生成树，其中边权之和最小的生成树成为最小

图论最短路 Dijkstra算法朴素Dijkstra算法 O(n^2)Dijkstra算法用于求节1到点n的最短路，适用于稠密图（其时间复杂度与边数m无关）。 对每个点设定一个dist，代表其距离点1的距离，初始化为无穷大，后续再进

欧拉函数定义1~N中与N互质的数的个数称为欧拉函数，记为ϕ(N)。 若在算数基本定理中，N = p1^a1 * p2^a2 * ….. * pm^am。 ϕ(N) = N * (p1 - 1) / p1 * (p2 - 1) / p2 *

线性DP数字三角形用f[i] [j]表示走到f[i] [j]的最大步数，一共只有两种走法，左上方走下来或右上方走下来，因此我们可以列出状态转移方程 f[i][j] = f[i - 1][j - 1] + a[i][j]; //左上方走下来

约数约数，又称因数。整数a除以整数b(b≠0) 除得的商正好是整数而没有余数，我们就说a能被b整除，或b能整除a。a称为b的倍数，b称为a的约数。 试除法求约数#include <bits/stdc++.h> using nam

哈希表哈希表的作用将一个庞大的空间（值域）映射到比较小的空间（0-N），N一般为1e5-1e6左右。 这种映射通常使用模运算来进行，但将若干较大范围的数映射到较小范围的数，难免会发生冲突（两个数映射到同一个数上），为解决这种冲突，我们需要特

质数质数的判定-试除法质数的因子一定是成对出现的，因此不必枚举所有的因子，只要枚举其中较小的因子，也就是一半的因子即可。而较小因子的上限是sqrt(n)，所以只需到sqrt即可。 #include <bits/stdc++.h>