主席树/函数式线段树/可持久化线段树 初步 学习笔记

主席树/函数式线段树/可持久化线段树 初步 学习笔记
1.什么是主席树？
主席树是一种由许多棵 重叠的 值域线段树构成的数据结构，可以维护很多跟值域有关的信息。
2.怎么写主席树？
先来看一道例题(区间第 /(k/) 小)：

洛谷P3834 【模板】可持久化线段树 2
题目大意:给定 /(n/) 个整数构成的序列 /(a/)，将对于指定的闭区间 /([l,r]/) 查询其区间内的第 /(k/) 小值。

先离散化一下。考虑用值域线段树来维护这个东西，一个非常暴力的思路就是建 /(n/) 棵线段树，第 /(i/) 棵线段树维护区间 /([1,i]/) 的信息，对于区间 /([l,r]/) 只需把第 /(r/) 棵线段树和第 /(l-1/) 棵线段树做差再查第 /(k/) 小。这样做的时间复杂度是 /(O(n^2)/) 的，时间也是 /(O(n^2)/) 的 (时空两开花) ，显然会炸。
有没有优化的方法？当然有！
注意到一件事：

如果把其他的节点复制一遍显然太浪费了，所以可以在新建

主席树/函数式线段树/可持久化线段树 初步 学习笔记最先出现在Python成神之路。