可持久化线段树

一句话理解

可持久化线段树：改时新建一条链，旧版本还在。

为什么要学

主席树基础。

讲解

每次修改 O(log n) 新节点。

例子

历史版本的根存在 root[i]。

常见错误

• 每次整树复制。
• 空间没按 m log n 开。