可持久化线段树和主席树是一个东西吗？ about oi-wiki HOT 5 CLOSED

据我的了解：
可持久化线段树是指狭义的可持久化，也就是“persistent”这词的含义，包括“部分可持久化”和“完全可持久化”等。（详见 wikipedia: persistent data structures）

函数式是指“functional”，这是在 Programming Language Theory 中的一个概念。可以理解为对数据结构的所有操作都不能修改已有数据，而必须是建立新的数据（如新的“结点”）。
函数式线段树是指使用函数式编程**的线段树。通常只要用完全可持久化（fully persistent）线段树就可以实现。
另一方面，多棵结构相同的线段树（可以是可持久化线段树、函数式线段树）能够进行一些算术运算，比如加法和减法。这样能表示一些单棵线段树难以表示的信息。

主席树往往指“区间的权值线段树”。这可以通过构造每个前缀区间的（可持久化）权值线段树，再通过减法运算来实现。主席树多用于“区间第 k 大”类型的题目。

希望能对这类问题有帮助。

from oi-wiki.

可持久化线段树就是主席树

from oi-wiki.

放在一起没有问题

from oi-wiki.

因为发现可持久化线段树可以合并,相减的人叫黄嘉泰,hjt,让人想起胡锦涛,所以外号是主席

from oi-wiki.

然后那个不叫persistent,叫Chair-Tree,是发明人自己说的

from oi-wiki.