可持久化后的数据结构并不会修改什么。它把所有版本都存了下来，每次修改都会新建一个副本，然后将修改作用于副本。这样，它就拥有数据回滚、访问历史版本的能力了。

在 OI 中，红黑树可是跑的最快的，其实很好写，就 100 行够了，希望看完后你能掌握它。

Splay 是最灵活的平衡树，除了常数和不能完全可持久化，它几乎没有缺点。

luogu 阅读链接。 题目链接 我们先看一道弱化版：P1972。 在 P1972 中，我们将询问离线，每个颜色当前的最后一位才有贡献。 在这道题，我们每个颜色有了不同的贡献，从保留一位变成保留 kkk 个。 我们先对当前位置单点加。 如果超出 kkk 个，就把最前面的数减去。 答案就是当前的区间和。 用树状数组做单点修改、区间查询，用 vector 访问前面的数。 123456789101...

luogu 阅读链接。 题目链接 我们先把环断成链。 转换题意：fi,j=fi−1,j−1⨁fi−1,j+1f_{i, j} = f_{i - 1, j - 1} \bigoplus f_{i - 1, j + 1}fi,j​=fi−1,j−1​⨁fi−1,j+1​。 其中第一维是操作次数，⨁\bigoplus⨁ 是异或。 由于 TTT 很大，而且大概率是不会有循环的。 那么我们先画图： ...

线段树你肯定会吧，WBLT 就是把线段树和平衡树结合起来了。

luogu 阅读链接。 题意 题目链接 有两行，一行 nnn 个点，和 mmm 条线（从第一行的节点连向第二行的节点）。 现在问你最多留下多少线，能使任意两条线均不相交。 思路 为了方便描述，第 aaa 条线的第一行节点是 axa_xax​，第二行节点是 aya_yay​。 显然，两条相交的线 a,ba, ba,b 必然满足，ax<bx∧ay>bya_x < b_x \...

fhq-treap 又名“无旋 treap”，有着码量小，易理解，可持久化等特点。

前言 在 volantis 中，归档是自动生成的，但 tags, categories 是需要自行添加的。 添加 在博客的根目录处，执行这个语句： 12hexo new “tags”hexo new “categories” 成功后，打开 / source / tags / tags.md , 将下面一段粘贴： 12345---layout: tagindex: truetitle: 所...