學習權值線段樹，首先要了解線段樹是什麼。如果不會的可以先學習一下。
是什麼
權值線段樹，顧名思義是一棵線段樹。
但它和普通線段樹不同：
線段樹，每個節點用來維護一段區間的最大值或總和等。
權值線段樹，相當于一個桶，每個節點用來表示一個區間的數***出現的次數***。
為什麼要用它
我們可以用它來維護一段區間的數出現的次數，從它的定義上來看，
它可以快速計算一段區間的數的出現次數。此外，它還有一個重要功能，
在于它可以快速找到第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);
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];
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];
if(y<=mid)
return find(l,mid,v*2,x,y);
if(x>mid)
return find(mid+1,r,v*2+1,x,y);
return find(l,mid,v*2,x,mid)+find(mid+1,r,v*2+1,mid+1,y);
查詢所有數的第k大值
這是權值線段樹的核心，思想如下：
到每個節點時，如果右子樹的總和大于等于k，說明第k大值出現在右子樹中，
則遞歸進右子樹；否則說明此時的第k kk大值在左子樹中，則遞歸進左子樹，
注意：此時要将k的值減去右子樹的總和。
為什麼要減去？
如果我們要找的是第7大值，右子樹總和為4(大數字在後面喲)，7-4=3，
說明在該節點的第7大值在左子樹中是第3大值。
最後一直遞歸到隻有一個數時，那個數就是答案。
int kth(int l,int r,int v,int k)
//l左邊界，r右邊界，v目前根結點,查詢第k大的數字
if(l==r) return l;
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);
return kth(l,mid,v*2,k-s2);