主席树，又叫可持久化权值线段树，也叫函数式线段树，是可持久化线段树的子集。在本文中，我们可以认为主席树等于可持久化线段树 可持久化线段树简介 基本结构、特点、作用在这篇文章中已经提到过：线段树扩展：权值线段树 总的来说就是每次修改或插入一个值，就新建一个根节点，并且向下递归去新建其他节点。 优点解释 每次插入操作最多创建的节点数都为$\log n$…