定义：
权值线段树，基于普通线段树，但是不同。
举个栗子：对于一个给定的数组，普通线段树可以维护某个子数组中数的和，而权值线段树可以维护某个区间内数组元素出现的次数。
在实现上，由于值域范围通常较大，权值线段树会采用离散化或动态开点的策略优化空间。单次操作时间复杂度o(logn)
权值线段树的节点用来表示一个区间的数出现的次数 例如： 数 1和2 分别出现3次和5次，则节点1记录 3，节点2 记录5， 1和2的父节点记录它们的和8 .
存储结构：
堆式存储：rt ,l, r, rt<<! , l, m rt<<1|1 ,m+1, r
结点式存储 struct Node { int sum ,l , r :};
基本作用：
查询第k小或第k大。
查询某个数排名。
查询整干数组的排序。
查询前驱和后继（比某个数小的最大值，比某个数大的最小值）
基本操作：
单点修改 (单个数出现的次数+1)
void update(int l,int r,int rt,int pos) // 当前区间范围 l r 节点 rt 位置 pos { if(l==r) t[rt]++; else { int mid=(l+r)/2; if(pos<=mid) add(l,mid,rt*2,pos); else add(mid+1,r,rt*2+1,pos); t[rt]=t[rt*2]+t[rt*2+1]; { }
查询一个数出现的次数
int query(int l,int r,int rt,int pos) { if(l==r) return t[rt]; else { int mid=(l+r)/2; if(pos<=mid) return find(l,mid,rt*2,pos); else return find(mid+1,r,rt*2+1,pos); } }
查询一段区间数出现的次数 查询区间 【x,y]
递归+二分
int query(int l,int r,int rt,int x,int y) { if(l==x&&r==y) return t[rt]; else { int mid=(l+r)/2; if(y<=mid) return find(l,mid,rt*2,x,y); else if(x>mid) return find(mid+1,r,rt*2+1,x,y); else return find(l,mid,rt*2,x,mid)+find(mid+1,r,rt*2+1,mid+1,y); } }
查询所有数的第k大值
这是权值线段树的核心，思想如下：
到每个节点时，如果右子树的总和大于等于k kk，说明第k kk大值出现在右子树中，则递归进右子树；否则说明此时的第k kk大值在左子树中，则递归进左子树，注意：此时要将k kk的值减去右子树的总和。
为什么要减去？
如果我们要找的是第7 77大值，右子树总和为4 44，7−4=3 7-4=37−4=3，说明在该节点的第7 77大值在左子树中是第3 33大值。
最后一直递归到只有一个数时，那个数就是答案。
int kth(int l,int r,int rt,int k) { if(l==r) return l; else { int mid=(l+r)/2,s1=f[rt*2],s2=f[rt*2+1]; if(k<=s2) return kth(mid+1,r,rt*2+1,k); else return kth(l,mid,rt*2,k-s2); } }
进阶知识 主席树：https://www.cnblogs.com/young-children/p/11787490.html
参考博客：https://blog.csdn.net/qq_39565901/article/details/81782611
原文：https://www.cnblogs.com/young-children/p/11787493.html