前言

先前博客中写过“线段树”这一篇文章，而这一次是一种具有新的含义的线段树：权值线段树。

权值线段树简介

定义

权值线段树和普通线段树的形态类似，但是含义不同。普通线段树的节点通常存储该区间的最值或者和值，其节点范围是一个区间：权值线段树的节点存储该值域内的元素个数，其节点范围是一个值域。

基本结构

如图，对于每个节点的位置表示的是元素的值，然后节点旁边的元素表示的是元素的数量。

其中第一个节点$[1,5]$表示值域大于等于$1$小于等于$5$，周围红色的元素表示落入值域$[1,5]$的数有$8$个。其他类似：落入值域$[1,3]$的数有$5$个，落入值域$[4,4]$的数有$2$个……

权值线段树的一般操作与普通线段树相同。

主要作用

查询第k小或第$k$大、查询某个数排名、查询整干数组的排序、查询前驱和后继（比某个数小的最大值，比某个数大的最小值）

权值线段树的扩展

如果我们有$n$棵这样的线段树，它们形态一模一样，只是节点的权值不一样，那么这些线段树是可以互相加减的（两棵线段树相加减就是它们所对应的节点权值相加减）。

于是我们就可以利用前缀和的思想：如果任意一个区间$[l,r]$的权值线段树都可以由两棵权值线段树相减得到，我们就可以在这棵权值线段树上快速查询区间问题。

但开出$n$棵权值线段树索要花费的空间太大，如果这$n$棵树中有很多点重复，我们可以让它们公用一个节点。其他有变化的节点再去重新构造，这就成了主席树。