【概念】
权值线段树属于一种线段树，它的本质仍然是线段树。
普通线段树维护的信息是数列的区间信息，比如区间和、区间最大值、区间最小值等等。在维护序列的这些信息的时候，我们更关注的是这些数本身的信息，换句话说，我们要维护区间的最值或和。我们最关注的是这些数统共的信息。
权值线段树维护一列数中数的个数。
我们来看这样一个数列：1 2 2 3 3 3 4 4 4 4。我们关注的是：有几个 1，几个 2，几个 3，几个 4，这样的信息。
一棵权值线段树的叶子节点维护的是“有几个1”，“有几个2”...，他们的父亲节点维护的是“有几个1和2”。这个东西就是我们刚刚说过的“桶”。
【区别】
权值线段树维护的是桶，按值域开空间，维护的是个数。
简单线段树维护的是信息，按个数可开空间，维护的是特定信息。
【用途】
权值线段树可以解决以下几个问题：
1. 数出现的次数。
2. 数列第 k 大/小的问题。
3. 比 x 大/小的数的个数。
这里要注意！我们只能对给定数列解决整个数列的第k大/小，并不能解决数列的子区间的第k大/小。解决数列子区间的第k大/小需要主席树（可持久化线段树）
【总结】
权值线段树的空间范围是视值域而定的，那么遇到 $\ge 10^6$ 的值域后，我们就得采取离散化或者是动态开点了。

我们给定序列 {1,2,2,3,3,3,4,4,4,4}，以该序列为例建立权值线段树。
首先，给一个空树。
A[i] 表示原序列中存在值为 i 的元素个数。
D[i] 表示一定区间所含元素个数。

再按照顺序插入元素。

【查询第 K 大/小元素】
假设 K=5，这里查询第 K 大：
首先我们要知道，第 K 大是从右往左数的，是相对于终点而言的，所以从右子节点开始判断

当前节点右子树包含 4 个元素，那么说明第 K 大不在右子树里，往左子树找，并且要减去右子树的 4 个元素，等效于在左子树中找第 1 大的元素。


第 K 小与之类似，就是反过来了而已。
梳理一下：对于整列数中第 K 大/小的值，我们从根节点开始判断（这里按第 K 大为例），如果 K 比右儿子大，就说明第 K 大的数在左子树中。然后，K 要减去右子节点的值。（这是因为继续递归下去的时候，正确答案，整个区间的第 K 大已经不再是左子树表示区间的第 K 大了)。如此递归到叶子节点时即为答案。

【参考代码】
【单点更新】

void Insert(int p,int l,int r,int k)
{
	if(!p) p = ++tot;
	if(l == r) { tree[p].sum++; return; }
	int mid = (l+r) >> 1;
	if(k<=mid) 
	{
		if(!tree[p].lc) tree[p].lc = ++tot;
		Insert(tree[p].lc,l,mid,k);
	}
	else 
	{
		if(!tree[p].rc) tree[p].rc = ++tot;
		Insert(tree[p].rc,mid+1,r,k);
	} 
	tree[p].sum = tree[tree[p].lc].sum + tree[tree[p].rc].sum;
}

【查询某个数出现的个数】
数上二分查找的思想。

int find(int p,int l, int r, int k)
{
    if (l == r) return tree[p].sum;
    else
    {
       	int mid = (l + r) >> 1;
        if (k <= mid) return find(tree[p].lc,l, mid , k);
        else return find(tree[p].rc,mid + 1, r, k);
    }
}

【查询一段区间内数的个数】

int Query(int p,int l,int r,int nl,int nr)
{
	if(!p) return 0;
	if(l>=nl && r<=nr) return tree[p].sum;
	int mid = (l+r) >> 1 , res = 0;
	if(nl<=mid) res += Query(tree[p].lc,l,mid,nl,nr);
	if(nr >mid) res += Query(tree[p].rc,mid+1,r,nl,nr);
	return res;
}

【查询第 K-th】

int query_kth(int p, int l, int r, int k){
    if(l == r) return l;
    int mid = (l + r) >> 1, right = tree[tree[p].rc ].sum;
    if(k <= right) return query(tree[p].rc , mid + 1, r, k);
    else return query(tree[p].lc, l, mid, k - right);
}