分类「数据结构」下的文章

莫队算法

莫队算法用于解决一类区间询问问题的办法对于一段给定的数据序列,有 $m$ 次询问,…

Splay平衡树

Splay平衡树基于 Splay 伸展操作维持平衡的二叉树,不断将某个节点旋转到根节点,可以在均摊 …

树链剖分、重链剖分

关于树上的查询修改问题,如果采用DFS的方式处理,时间效率会上升到 $O(n^2)$ 可以将树转化为…

LCA最近公共祖先

倍增法求LCAvector<int> e[500010]; int dep[500010]…

ST表

ST表(Sparse Table,稀疏表)主要用来解决 RMQ,可重复贡献问题 问题,相比于线段树,…

可持久化权值线段树(主席树)

区别于普通线段树,权值线段树维护的信息不同普通线段树:节点区间是序列的下标区间,维护区间最…

线段树、懒标记

RMQ问题——线段树+懒标记线段树,基于分治思想,用来维护区间信息的二叉树结构例如RM…

树状数组

树状数组相比于线段树类的操作,支持单点修改与区间查询,代码量小于线段树类的一种精…

邻接表实现树与图的存储与遍历

树是一种特殊的图,树没有环且相互连通图分为有向图和无向图,无向图可…

Trie树、字典树

Trie树是一种高效的存储字符串的数据结构,它将多个字符串的前缀合并在一条边上,每次插入时,都判断当前的树上有无能…

设置

黑暗模式
简繁体切换