权值线段树的定义

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

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

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

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

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

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

权值线段树的原理与操作

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



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

 $D[k]$：一定区间内所含元素的个数。

 可以看出，基础线段树和权值线段树的一个较大的区别点在于：(此处特指使用数组储存树结构)基础线段树根据初始的一个序列建立树结构，具有单独的建树操作；而权值线段树不需要进行建树操作，初始状态下默认建立一棵所有点权为$0$的空树，对于每个元素，在遍历的时候相应的结点做自增运算。

查找第K大元素的方法：

 由于权值线段树每个节点记录了某段区间内包含的元素个数，且元素在叶子节点构成的序列中是有序的：

 对于整列数中第$K$大/小的值，我们从根节点开始判断（这里按第$K$大为例），如果$K$比右儿子大，就说明第$K$大的数在左儿子所表示的值域中。然后，$K$要减去右儿子。（这是因为继续递归下去的时候，正确答案，整个区间的第$K$大已经不再是左儿子表示区间的第$K$大了)。如此递归到叶子节点时即为答案。（其实跟BST的原理差不多）。

 整棵线段树的根节点就表示整个值域有几个数。

 我们很容易看出：在权值线段树中，采用元素到下标数组映射的方式进行插入。这样会导致一个问题：在数据离散程度较大的情况下，空间的利用效率比较低。因此我们对于线段树所开空间不足时，常采用离散化的方式进行解决。

查询第$K$大/小元素

#define ls p<<1
#define rs p<<1|1 

int query(int p,int l,int r,int k){//第k大 
    if(l==r)return l;//到达根节点，找到了 
    int mid=(l+r)/2,right=t[rs];//这里的t数组存储的是区间有多少个数 
    if(k<=right)return query(rs,mid+1,r,k);//就在右子树中找 
    else return query(ls,l,mid,k-right);//在左子树中找 
}

int query(int p,int l,int r,int k){//第k小 
    if(l==r)return l;
    int mid=(l+r)/2,left=t[ls];
    if(k<=left)return query(ls,l,mid,k);
    else return query(rs,mid+1,r,k-left);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

单点更新

#define ls p<<1
#define rs p<<1|1

void update(int p,int l,int r,int x){
    if (l==r)t[p]++;
    else{
        int mid=(l+r)/2;
        if(x<=mid)update(ls,l,mid,x);
        else update(rs,mid+1,r,x);
        t[p]=t[ls]+t[rs];
    }
}



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

查询某个数出现的个数(二分实现)

#define ls p<<1
#define rs p<<1|1

int find(int p,int l,int r,int x){
    if (l==r)return t[v];
    else{
        int mid=(l+r)/2;
        if (x<=mid)return find(ls,l,mid,x);
        else return find(rs,mid+1,r,x);
    }
}
1
2
3
4
5
6
7
8
9
10
11

查询一段区间的数出现的次数

#define ls p<<1
#define rs p<<1|1

int find(int p,int l,int r,int x,int y){
    if (x<=l and r<=y) return tree[v];
    int mid=(l+r)/2,ans=0;
    if(x<=mid)ans+=find(ls,l,mid,x,y);
    if(y>mid)ans+=find(rs,mid+1,r,x,y);
    return ans;
}

1
2
3
4
5
6
7
8
9
10
11

离散化就不用我讲了吧