什么叫“可持久化”？

在算法竞赛中，“可持久化”通常指一种数据结构技术，它允许我们在修改数据结构后，仍然能访问到修改前（即历史版本）的数据。

主席树的核心思想

主席树，又称可持久化（权值）线段树，是可持久化思想的经典应用。它通过巧妙地复用节点，实现了在保持历史版本的同时，高效地创建新版本。

当我们对线段树进行单点修改时，从根节点到目标叶子节点的路径上，最多只有 log(N) 个节点会发生改变。可持久化的思想就是：只创建这 log(N) 个新的节点，而路径上其他未改变的节点，则直接链接到旧版本的对应节点上。