线段树应用——权值线段树_权值线段树的应用

作者：Gausst松鼠会 | 2024-03-02 10:55:09

踩

权值线段树的应用

权值线段树的定义

权值线段树是一种建立在基本线段树之上的数据结构。因此它的基本原理仍是基于对区间的维护操作。但与线段树相区分的点是：权值线段树维护的信息与基本线段树有所差异：

1.基本线段树中每个结点可以用来维护一段区间的最大值或总和等；
2.权值线段树每个结点维护的是一个区间的数出现的次数。

实际上，权值线段树可以看作是一个桶，桶的操作它都支持，并且能够以更快的方式去完成。

根据权值线段树的性质，我们可以知道其主要用途：

权值线段树一般用于维护一段区间的数出现的次数，从它的定义来看，它可以快速计算出一段区间的数的出现次数。

在实际应用中，我们使用权值线段树查询区间第 $K$ 大的值。

假设我们现在有一个序列 $A={1,2,2,3,3,3,4,4,4,4}$ 我们先来通过三张图片感性理解一下这两种线段树的不同。
在这里插入图片描述

上图相关解释：
$A [1] = 1$ ：原序列中存在值为 $1$ 的元素 $1$ 个
$A [2] =$

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/180023