主打一个自定义(((
目前包含的内容:
FENWICK_TREE
数据结构:树状数组。
* 预处理:O(n)O(n)O(n)。
* modify:将 AiA_iAi 增加 kkk,O(logn)O(\log n)O(logn),常数极小。
* query:查询 ∑j=1iAj\sum_{j=1}^{i} A_j∑j=1i Aj ,O(logn)O(\log n)O(logn),常数极小。
可以替换成前缀异或、前缀最值等。
SEGTREE
数据结构:线段树。
* 预处理:O(n)O(n)O(n)。
* modify:将 Al,Al+1,...,ArA_l,A_{l+1},...,A_rAl ,Al+1 ,...,Ar 的值增加 kkk,O(logn)O(\log n)O(logn),常数较大。
* query:查询 ∑j=lrAj\sum_{j=l}^r A_j∑j=lr Aj ,O(logn)O(\log n)O(logn),常数较大。
可以替换成区间最值,区间 kkk 次方和等。
BLOCK
* 预处理:O(nlogn)O(n\log n)O(nlogn)。
* modify:将 Al,Al+1,...,ArA_l,A_{l+1},...,A_rAl ,Al+1 ,...,Ar 的值增加 kkk,O(nlogn)O(\sqrt n\log n)O(n logn)。
* query:查询 maxj=lrAj×[Aj<k]\max_{j=l}^r A_j\times [A_j\lt k]maxj=lr Aj ×[Aj <k],O(nlogn)O(\sqrt n\log n)O(n logn)。
这个可以改的就很多了,几乎可以说是万能数据结构。
DSU
数据结构:并查集。
* 预处理:O(n)O(n)O(n)。
* find:查询一个点所在集合的代表,O(α(n))O(\alpha(n))O(α(n))。
* merge合并两个集合,O(α(n))O(\alpha(n))O(α(n))。
可以删除路径压缩优化,用作可撤销并查集,此时查询、合并时间复杂度均为 O(logn)O(\log n)O(logn)。
MATRIX
数据结构:矩阵。
* 预处理:O(n2)O(n^2)O(n2)。
* 乘法:O(n3)O(n^3)O(n3)。
MULTI_SEGTREE
数据结构:可持久化线段树/主席树。
* 预处理:O(n)O(n)O(n)。
* build_new:新建一个数组 AnewA_{new}Anew ,使 Anew,j=Apre,jA_{new,j}=A_{pre,j}Anew,j =Apre,j ,并修改 Anew,i=kA_{new,i}=kAnew,i =k,O(logn)O(\log n)O(logn),常数较大。
* query:查询 ∑j=lrAi,j\sum_{j=l}^r A_{i,j}∑j=lr Ai,j ,O(logn)O(\log n)O(logn),常数中等。
SCC_SOLVER
算法:Tarjan 求 SCC。
* get_SCC:对一个大小为 nnn,有 mmm 条边的图,求它的所有 SCC(强联通分量),O(n+m)O(n+m)O(n+m)。