-
Dfn序 && 欧拉序
Dfn 序 点修改+子树查询/子树修改+点查询 树状数组维护单点/差分 子树修改+子树查询 线段树区间加区间和 路径修改+点查询 维护 和每个点到根的路径和，转成 ，，， 从下往上差分，一个点的差分为它的值-所有儿子的值 1234mdf(dfn[x],d);mdf(dfn[y],d);mdf(dfn[p],-d);if(fa[p]) mdf(dfn[fa[p]],-d);pri... -
Extra 线段树-优化建图
常见线段树 一般是区间/点向区间/点连边 线段树的本质就是区间向点的映射，我们利用这一点优化 P6348 [PA2011] Journeys 我们建立一颗入树和出树，如下图 左边是出树， 右边是入树， 蓝色边权为 当我们需要从 建边，就 对 建立两个虚点，虚点之间连边 1234567891011121314151617181920212223242526272829303132... -
Extra 树状数组
单点加+矩阵求和123456void add(int x,int y,int v){ for (int i=x;i<=n;i+=lowbit(i)) for (int j=y;j<=m;j+=lowbit(j)) a[i][j]+=v;} 12345678910111213int sum(int x,int y){ int res=0... -
树剖
树链剖分将树上问题转到序列上，转而方便用数据结构维护 重子节点：表示其子节点中子树最大的子结点 如果有多个子树最大的子结点，取其一 如果没有子节点，就无重子节点 轻子节点：表示剩余的所有子结点 重边：从这个结点到重子节点的边为 轻边：到其他轻子节点的边为 重链：若干条首尾衔接的重边构成 把落单的结点也当作重链，那么整棵树就被剖分成若干条重链 树上每个节点都属于且仅属于一条重链 在剖分时，重... -
三分
三分法求单峰函数极值点，当发现类似双指针的结构最值时，可以考虑三分 https://blog.csdn.net/Mr_dimple/article/details/126361376 实数三分例题 https://www.luogu.com.cn/problem/P3382 给出一个 次函数，保证在范围 内存在一点 ，使得 上单调增， 上单调减。试求出 的值 时， 就没用了，这就... -
线性代数
Here’s something encrypted, password is required to continue reading.
-
EXSTL-Pbds
奇淫巧技-Pbds 的平衡树+ 表 内部为平衡树 平衡树有红黑树，，有序向量树 一般就用红黑树 123#include<ext/pb_ds/assoc_container.hpp>#include<ext/pb_ds/tree_policy.hpp>using namespace __gnu_pbds; 一般就定义成 1tree<int,null_type... -
EXSTL-Rope
奇淫巧技-Rope 的可持久化平衡树，无法做区间第 大 内部为块状链表实现 12345678910111213141516#include <ext/rope>using namespace __gnu_cxx;rope<int> rp;rope<int> rp[N]rp.push_back(x);rp.insert(pos,x); //a[pos]=x... -
Tarjan && 圆方树
Here’s something encrypted, password is required to continue reading.
-
概率期望
Here’s something encrypted, password is required to continue reading.
