题目链接

题目概括大力征集中~

本文部分内容转载自 OI Wiki Splay

$\LaTeX$ 就先咕着吧……有时间慢慢搞

概述

Splay是一种二叉查找树，它通过不断将某个节点旋转到根节点，使得整棵树仍然满足二叉查找树的性质，并且保持平衡而不至于退化为链，它由 Daniel Sleator 和 Robert Tarjan 发明。

本文部分内容转载自 OI Wiki 树状数组套主席树

概述

普通数据结构维护单一维度信息，树套树维护多维度信息。

概述

树链剖分用于将树分割成若干条链的形式，以维护树上路径的信息。

具体来说，将整棵树剖分为若干条链，使它组合成线性结构，然后用其他的数据结构维护信息。

题目链接

给定数轴上$n$个点，给出$m$条独立的指令，将编号为$[l,r]$ 的点集中到$[k,k+r-l]$的位置且这些点个点位置不能重合，求每次命令中移动的点的距离和的最小值
（$n,m≤5×10^5, 1≤a_i,K≤10^6$）

感谢@oy的贡献

概述

可持久化数据结构可以存储数据集在任意时间的历史状态。“可持久化”的基本思想是在每项操作结束后，仅创建数据结构中发生改变的部分的副本，不拷贝其他部分。这样一来，维护数据结构的时间复杂度没有增加，空间复杂度仅增长为与时间同级的规模。换言之，可持久化数据结构能够高效地记录一个数据结构的所有历史状态。