写过的一些东西合集
大概还是想记录一下这些吧，那些我所真正热爱的。
每个文可能（理论上）有很多个标签，会选择一个比较合适的归类进去。
特别置顶：
-
【详细介绍】一种基于斜二进制的序列&树上数据结构
-
并查集线段树
数据结构相关
线段树与树状数组相关
拜线段树教：https://www.luogu.com.cn/team/55190。
- zkw 线段树和 BIT 的几个小trick
其实还有更早的但被这篇子集了。大概是想写点什么，虽然写的确实很烂。
- 如何优雅地在 zkw 线段树上跑无修 rmq 【笔记】
第一次在 UOJ 上写文。东西确实没啥用，但这个思路被 ut 记下了。
- 一种野蛮处理静态序列多次在线区间查询的数据结构
上面那篇的后续。当时感觉好 NB，然后就被怒斥了，并从某位大佬处学到了
- 一棵比较有意思的线段树
对非递归线段树的再次思考，囿于“树”形态的桎梏，造出了这样一个奇奇怪怪的东西。发出后，从某位大佬处学到了 CF 上那个进化成森林的线段树。
- 【推广】猫树
进化到脱离线段树范畴的非递归写法。实际胡的时间比上面那篇早，但是写锅重置了。
- （娱乐向）learn how to use Fenwick Tree
什么罐头我说，男人。另外这篇也是有前置的，在后面。
- 【水】当多点求值遇上非递归线段树
非递归高光时刻。
- 线段树救爷爷。
2020 年上半 ut 就尝试过用 zkw 线段树救爷爷，未遂，主要原因是
- 糖人糖码
其实是个线性空间的动态开点 BIT。这东西是有前置的，后面会提。
- 位压缩线段树。
比压缩 Trie 好写。
- 分块的线段树。
基于线段树的精细化多层分块实现。
- 并查集线段树。
如何优雅地在 zkw 线段树上跑无修 rmq 【笔记】和一种野蛮处理静态序列多次在线区间查询的数据结构的后续。事实上在此一年前 ut 已经把这套思路搞到了在线的单
- 树剖，Tarjan，线段树。
上面那篇的上树版。
- 线段树，阿克曼，分块
上上面那篇的在线版说不定到时候也给上个树排列组合。
- （娱乐向）learn how to use Segment Tree
理论最优！！1
- 【详细介绍】一种基于 zkw 线段树的区间查询刻画
简单统合。
- 单 log 并查集线段树分治
线段树分治也是线段树！！1
可并堆相关
- 天哪怎么会有这么好写的可并堆啊
由于各种原因 ut 在很长一段时间里玩不明白左偏树，然后初见配对堆的时候惊为天人。
- 这是谁的部将？
书接上文，ut 初见斜堆。
- 公 若 不 弃
书接上文，ut 在论文里初见 hollow heap，Tarjan 老爷子的代码还写挂了。
- 优 先 队 列 超 进 化
同样是 Tarjan 论文里挖出来的。
- 你怎么这么短啊？
斐波那契堆。
- ❤对优先队列的爱❤
好玩，爱玩。
- 公 若 不 弃 2
是哪篇的后续我不说。
- 神之所以为神——斜堆简介
斜堆后续。
- self-adjusting 的荣勋——配对堆简介
配对堆后续，补了一个比较劣的复杂度证明。
- 我 们 仨
二项堆，懒二项堆，斐波那契堆。
关于文章里提到的某个名字……初见端倪？
- 战术 segtree 的咆哮——quake heap 简介
很有启发性的一个堆。纠结了很久要不要把这个丢到最上面那个分类。
- 优 先 队 列 超 进 化 2
上面某篇的复杂度证明。
- 梦中情堆——strict fibonacci heap 简介
如果有人试图对着实现代码就会发现，写得真的很烂。
- 左偏树，和它的怨种兄弟
姗姗来迟的 OI 快乐堆。
- fib heap 伴生算法——更快的 MST。
不知道为什么比较冷门，可能大家都不是很缺这点 MST 性能？
- 【娱乐向】战术 priority queue 的咆哮
糖人糖码和后面某个东西共同的核心前置。姑且还是归到堆里比较好。
某斜二进制数据结构相关
- 【详细介绍】一种基于斜二进制的序列&树上数据结构
【娱乐向】战术 priority queue 的咆哮正统后续。
- 更适合线性空间宝宝体质的 DAG 支配树
之所以这里另外只有一篇是因为大部分都被收进上面那个文里了。这篇也是被子集的。
- 斜二进制 LCA
懒得看以上一串的可以直接看这个。
树上数据结构相关
- 一种野蛮处理静态树上离线链查询的做法
在得到指正后，ut 和朋友一起去改了 OI-wiki。
- 一种野蛮处理静态树上在线链查询的做法
不会点分树导致的。
- 树上数据结构——ART 分解的艺术
非常冷门的算法，基本没啥用。
- 力大堆飞 P3261
万恶之源。
- 力大堆飞 P3261（二）
初见端倪。
- 力大堆飞 P3261（三）
渐入佳境。
- 力大堆飞 P3261（四）——轻量级树上数据结构一则
大彻大悟。
- 一种简单的 O(nlogn) 预处理 O(1) 查询静态树上链半群的方法
力大堆飞 P3261（三）的后续。
其他数据结构相关
- splay 复杂度证明，以及一点相关
self-adjusting 的含金量。
- y-fast trie 简介
感觉不如融合树。
- 【并查集】茴的六种写法
即使不是路径压缩，复杂度也可以是对的。
- 【水】斜堆和 LCT
联想一则。
- 单调栈救爷爷。
其实没有线段树救爷爷。那么重量级。
- 某线性的 ufds（上）
模型失真比较严重，实际意义有限。这个系列旨在用三篇论文来说明随机数据的路压并查集复杂度是线性的。但这篇其实不需要路压。
- 某线性的 ufds（下）
其实有（中）但还没写好……另外这篇的逻辑是真的很奇怪。
- 单 log 持久化并查集
节点分裂，伟大。
语言相关
- 就是说您老的这个库和命名空间能不能搞得稍微阳间一点
奇怪的不知道为啥没加入标准的随机数函数。
- 如何遍历一个 std::stack（详细揭秘）
省流：##define private public。
- experimental 大冒险（？
就是说您老的这个库和命名空间能不能搞得稍微阳间一点后续。
- 厌氧菌。
由于一般通信题不会这么唐，实际上除了让你的代码变得特别神秘以外没啥用。
- 厌氧菌，但是交互。
那怎么还真有这么唐的通信题还不开 O2。
- 哲就是 C 带给我的自信
省流：函数套函数。好玩起见叠了个厌氧菌。
- 我找到你的家了！
如何遍历一个 std::stack（详细揭秘）的后续。
O(1) 相关
- 【理性愉悦】如何优雅地玩转线性-常数时间复杂度
在洛谷写了不少东西但全都被这篇子集了。
- 【理性愉悦】无向连通图正整数边权线性时空单源最短路浅析
刚打完 NOI 闲的没事干导致的。
- 力 大 砖 飞
后续。
- 力 大 砖 飞 2
还是后续。实际上对任意规模的整数边权做 MST 是可行的，参考 fib heap 伴生算法——更快的 MST。。
- 线性算法两则
中位数和后缀数组。这个系列其实还有后续的几篇，丢到下面这个分类了。
- 位运算三则
其实现代计算机基本都可以直接指令了。混进来一个不是那么 O(1) 的东西，无妨。
数学相关
- 笔记——奇怪的逆元
不知道为啥没能得到推广，这不比快速幂和扩欧好写？
- 杜教筛小寄巧
实际上由于很多时候要多测，用处比较有限。
- 科技题
The Trygub numbers。
- 【学习笔记】快速阶乘算法
水烂了都。
- 【学习笔记】更快速阶乘算法
不太会 djq 分治导致的。
- O(1) 查询三则
初见端倪。
- Montgomery 取模器
其实比巴雷特优。
- Barrett 取模器
但巴雷特更加灵活。
- 快速幂
O(1) 查询三则的后续之一。Pohlig–Hellman algorithm 的特化。
- 快速幂（二）
虽然标题格式很奇怪但其实是上面那篇的后续。标题改了。
- 【重度魔怔】【上】O(n)-O(1) exgcd
O(1) 查询三则的后续之一。推荐先行阅读 https://luogu.com.cn/article/5kgjhh2q。
- 【小短文】【中】O(n^epsilon)-O(1) exgcd
其实可以并进上面那篇一起写，但是那个太魔怔了。
- 【EI】【下】O(n^epsilon)-O(1) exgcd
这个问题的正经做法。
杂谈
- K r u s k a l 重 构 链
本质是注意到重构树的树形结构无关紧要。
- 悬线法学习笔记
感觉其实可以推广，空间小+好写。
- 神秘 2way 字符串匹配算法
很神秘的东西，啃了很久才懂，但不是在这里，这篇只有一个代码。
- 分散层叠算法指北
算是比较知名的冷门算法？应用场景其实不少。
- 神秘 2way 字符串匹配算法（二）
上面某篇的后续，补上了说理。
- 【学习笔记】矩阵快速幂·改
某个很好玩的东西，记之。
- Kosaraju 魅力时刻
这个冷门算法少数有用的场合。
- Kosaraju，但是边双
一点扩展。
- 多重背包
最没啥用的一集，如果你喜欢写单调队列。
- Xor Tree
简单即为正义！！1
- Xor Tree（剖剖爱剖 ver.）
这个真没啥用，但是常数显著小。
- Xor Tree（基环树 ver.）
哎这个可能真有点用吧！！1
以上。