权值线段树 学习笔记

前置知识

线段树及其常用操作（区间修改，区间查询，动态开点）、离散化、二分查找

权值线段树

又称值域线段树，权值线段树，顾名思义就是节点带权值的线段树，我们基本的线段树的节点由一个区间范围和一个记录最大最小值或者区间和的数值组成。 但是我们的权值线段树的节点是由权值构成的，即数组中出现的某一个数字的次数，就可以看作一个权值，因此就可以存储在权值线段树中当作这个线段的节点，这就是权值线段树。

对于一个给定的数组：

• 普通线段树可以维护某个子数组中数的和
• 而权值线段树可以维护某个区间内数组元素出现的次数

请注意：权值线段树维护的是值域，所以对于权值线段树来说空间往往是其限制因素，我们基本不可能做到维护 $1e9$ 以上的数据，因此往往需要 离散化 + 线段树，不光是权值线段树，基本上所有的线段树都需要离散数据，如果值域小的话则不需要。

NOTE

值域线段树结点下标可能不连续，因为其范围通常超出空间限制，要用到动态开点 / 离散化下标

权值线段树对于处理值域上的值出现的次数，即计数问题有着很大的优势。

何为动态开点？

动态开点线段树是线段树的变种之一，与普通的线段树不同的是，它是白手起家，并没有建树的过程，而是哪里要用开哪里，每个节点的左右子树的编号不再是该点编号固定的 2 倍和 2 倍 + 1，而是根据当前所开的节点数确定。

换句话说，就是建立一棵 “残疾” 的线段树，上面只有询问过的相关节点。从而节约了大量空间，这样当你面对庞大的数据时，也能如鱼得水，游刃有余。

应用场景

1. 求一段区间的某个数字出现的次数
2. 查询整体区间的第 k 大 / 小的值（注意是整体区间（整个值域），之后的学习中你会发现权值线段树与主席树的区别，主席树可以求得任意区间的第 k 大 / 小的值）

具体实现

一个完善的权值线段树能够支持的功能应该有：

1. 添加一个数字

   • 往权值线段树中添加一个数字，则节点记录的就是这个数字出现的次数
   • 因此逐层递归到指定区间后，次数加 1 即可
   • 可能要在这期间做动态开点

2. 求某数出现的次数

   • 递归寻找表示此数的区间
   • 判断到达叶子节点（这部分的实现可能不太一样），返回 sum [i] 即可

3. 查询一段区间中数字出现的次数

   • 给出一段区间 [L,R]，在权值线段树中查询 在这个区间里的所有的数出现的总次数
   • 递归左右子树，找到完全覆盖的子区间或叶子节点
   • 累加递归获得答案

4. 查询整个值域中第 k 小 / 大的数

   • 首先求出左右孩子节点的元素个数 Ln 和 Rn
   • 如果 k 小于等于 Ln，说明第 k 小的元素在左子树中，则递归到左子树
   • 如果 k 大于 Ln，说明第 k 小的数字在右子树中，则递归到右子树，注意此时相当于在右子树中寻找第 k-Ln 个元素

复杂度分析

由于权值树也是线段树，所以权值树的操作复杂度也都是跟线段树一样的，单词操作时间复杂度是 $\log (len)$。

注意事项

• 动态开点的时候，第一个点需要特殊注意保存，需要小心是否与特判竞争
• 在区间求和（求总数）的时候，需要及时剪枝，对于不存在的节点直接返回空值
• 注意在动态开点的时候，建树 / 添加节点的函数接受的应该是根节点的引用，方便更新对应父节点的子节点信息，节省空间时间，增强代码可读性，降低调试难度