权值线段树
就是指线段树的叶子节点保存的是当前值的个数。
权值线段树一般支持以下三个操作：
-
insert -
erase/remove -
query
贴一个alphadalao的题解。
主席树
主席树，也叫做可持久化线段树，准确来说，应该叫做可持久化权值线段树，因为其中的每一颗树都是一颗权值线段树。
经典例题：查询区间第k小。
主席树是静态的。
为了实现可持久化，就要保存树的历史版本。最自然的想法当然是每进行一次修改，就新建一颗线段树，这样的空间复杂度显然是不能够接受的。通过观察不难发现，每次进行单点修改，发生变化的只有从叶子节点到根节点这一条链上的节点，换句话说，只有 \(logN\) 个节点发生了变化，而其他的节点都可以重用，没有必要新建。
看图非常好理解。
然后就是一些实现上的细节了。
- 先建立不同的根，接下来只要修改 \(logN\) 个节点，查询从根节点开始即可。
- 数组大约要开 \(MlogN+4logN\) 大小。