nihility
  文章分类
数据结构 5 字符串 3 图论 2 动态规划 1 Golang 3
LCT LCT
动态树问题：维护一个森林，支持删除某条边，加入某条边并保证时刻是一个森林，我们需要维护森林的一些信息，一般的操作有询问两点连通性，询问两点路径的权值和，修改某点的权值。 基本介绍$LCT$是用来解决动态树问题的数据结构，各种操作的时间复
2022-09-06 数据结构
LCT
splay splay
简单介绍伸展树（$splay$），也叫分裂数，是一种平衡二叉树，能在$O(log\ n)$的时间复杂度内完成插入，查找和删除操作，比较好写而且很实用，$LCT$也经常借助$splay$来实现，是一种在竞赛中比较常用的数据结构。本篇就来给大
2022-09-05 数据结构
splay
可并堆 可并堆
可并堆，又叫左偏树，是一种支持合并的堆，以下内容基于小根堆（即根节点最小，大根堆类似），它支持以下功能： 求一个数所在堆的根节点（复杂度同并查集路径压缩） $O(1)$求最小值 $O(log\ n)$合并两个堆 $O(log\ n)$删除
2022-09-01 数据结构
可并堆
线段树 线段树
本文章以线段树的拓展为主，不会讲解基础内容。另外本人目前比较忙，将在军训和第三学期后更新内容，现只列出大纲和例题。 线段树妙用HH的项链 喵星球上的点名 多tag后效性处理维护序列 线段树合并Dominant Indices 线段树分裂Ma
2022-06-21 数据结构
线段树
并查集 并查集
这篇文章我们不再讲解并查集的基础知识，主要讲解并查集的一些拓展用法，需要补一下基础知识的同学我推荐这一篇文章：并查集，另外这篇文章里讲到的按秩合并，也可以是把小的集合合并到大的集合上面，这样更容易代码实现，我们只需多维护一个集合的大小就可
2022-06-19 数据结构
并查集