Mayflyyh
Mayflyyh
MayFlyyh's Blog

学习笔记
文章归档

静态主席树

静态主席树 维护区间查某个数的存在次数或者第k大以及更多 可持久化线段树+权值线段树 可持久化线段树,每次修改logn个节点包含当前需要修改的点x的区间,从前一个中继承剩下无需修改的区间 主席树查询:用区间下标root[r]-区间下标root[l-1]的结果查询 比如一个…

   129   2018-06-16 去围观

Splay 学习笔记(未完成)

一个月没写博客了,今后要更加努力啊 Splay Tree 是一种二叉排序树 通过不断旋转以维护单词操作复杂度为log(n)级别 在这里讲述的操作有:插入,删除,查询第k大,rank,前驱后继 旋转分三种情况 1.Zig 2.ZigZig 3.ZigZag 在这里不详细叙述旋转细节,而…

   5,176   2018-05-06 去围观

线段树学习笔记

线段树学习笔记 已知一个数列,你需要进行下面两种操作 1.将某区间每一个数加上x 2.求出某区间每一个数的和 线段树,即是将一个整区间分解成几小区间,保存多个子区间值以便查询时节约时间的数据结构。而LazyTag的设置使在单点修改节约了时间。 L1 …

   482   2018-02-24 去围观

LCA学习笔记

建树 结点数为N 边数为M 根节点S log2N 为树的最大深度 int log2N=log(1.0*N)/log(2.0)+0.5; 通过DFS预处理出树与深度 inline void dfs(int x,int f){ V[x]=1; D[x]=D[f]+1; F[X][0]=f; for(int i=Last[x];i;i=e[i].next){ if(V[x]) con…

   172   2018-02-13 去围观

最短路学习笔记

图的存储 邻接矩阵 初始化 G[i][j]=inf G[i][j] = v 表示 从点i与点j有边,权值为v; 有向图存一遍,无向图存两遍,重边取最小(吧) 适用于稠密图 领接表 定义一个Last[N]数组用于存储某点最新连接的边号 int Last [N],cnt = 0; struct Edge{ …

   373   2018-02-13 去围观