权值线段树
预备知识
学习权值线段树的预备知识，就是线段树，如果没有学过线段树，推荐先看完线段树，再回来看本文章
权值线段树
- 顾名思义，权值线段树是一颗线段树，但是又和普通的线段树不一样
- 线段树：每个节点用来维护一个区间的最大值或者总和，等等
- 权值线段树：与桶排序具有一定的相似性，每个节点相当于一个桶，用来表示一个区间的数出现的次数
相关问题
- 根据定义可以知道，我们可以用它快速计算一段区间的数的出现次数，或者是维护
- 当然他还有一个极其有用的功能，快速查找区间的第\(k\)大值或第\(k\)小值
与这边的节点，与桶排序中的桶极其相似
相关操作
添加
- 和普通线段树类似，递归到叶子节点时给\(f[v]+=1\)
- 以下代码要添加的数是x，也就是x出现的次数+1；
void add(int l, int r, int v, int x)
{
if (l == r) f[v]++;
else
{
int mid = (l + r) / 2;
if (x <= mid) add(l, mid, v * 2, x);
else add(mid + 1, r, v * 2 + 1, x);
f[v] = f[v * 2] + f[v * 2 + 1];
}
}
查找一个数出现的次数
- 递归到叶节点是，\(f[v]\)即为所求值
- 下面为寻找数\(x\)的出现次数的代码
int find(int l, int r, int v, int x)
{
if (l == r) return f[v];
else
{
int mid = (l + r) / 2;
if (x <= mid) return find(l, mid, v * 2, x);
else return find(mid + 1, r, v * 2 + 1, x);
}
}
查询一段区间的数的出现次数
- 与线段树查询同理，不断的二分递归
- 以下的代码为查询区间[x,y]出现的次数
int find(int l, int r, int v, int x, int y)
{
if (l == x && r == y) return f[v];
else
{
int mid = (l + r) / 2;
if (y <= mid) return find(l, mid, v * 2, x, y);
else if (x > mid) return find(mid + 1, r, v * 2 + 1, x, y);
else return find(l, mid, v * 2, x, mid) + find(mid + 1, r, v * 2 + 1, mid + 1, y);
}
}
查询所有数的第k大值
- 这是权值线段树的核心，思想如下：
- 到每个节点时，如果右子树的总和大于等于$$k\(，说明第\)k\(大值出现在右子树中，则递归进右子树；否则说明此时的第\)k\(大值在左子树中，则递归进左子树，注意：此时要将\)k$的值减去右子树的总和。
- 为什么要减去？
- 假设我们要寻找的是第7大的值，右子树的总和为4，\(7-4=3\)，那么说明第7大值在左子树中是第3大值
- 最后递归到只有一个数时，那个数就是答案
int kth(int l, int r, int v, int k)
{
if (l == r) return l;
else
{
int mid = (l + r) / 2, s1 = f[v * 2], s2 = f[v * 2 + 1];
if (k <= s2) return kth(mid + 1, r, v * 2 + 1, k);
else return kth(l, mid, v * 2, k - s2);
}
}
总结
- 这些就是权值线段树的基本应用了
- 掌握这些之后你就可以进一步学习主席树了
版权声明：本文为ghostlx原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。