（ 数据结构专题 ）【 权值线段树 】_线段树 统计区间内x出现的次数大于k

（ 数据结构专题 ）【 权值线段树 】

权值线段树

学习权值线段树，首先要了解线段树是什么。如果不会的可以先学习一下。

是什么

权值线段树，顾名思义是一棵线段树。
但它和普通线段树不同：
线段树，每个节点用来维护一段区间的最大值或总和等。
权值线段树，相当于一个桶，每个节点用来表示一个区间的数出现的次数。

为什么要用它

我们可以用它来维护一段区间的数出现的次数，从它的定义上来看，它可以快速计算一段区间的数的出现次数。
此外，它还有一个重要功能，在于它可以快速找到第k大或第k小值，下面会做详细解释。
其实，它就是一个桶，桶能做到的它都可以用更快的速度去完成。

基本操作

添加

以下代码要添加的数是x，也就是x出现的次数+1。

void update( int node, int left, int right, int x ) // 树中x出现的次数+1
{
    if ( left==right ) {
        tree[node] ++;
        return ;
    }
    if ( x<=mid ) update(lson,x);
    if ( x>mid )  update(rson,x);
    tree[node] = tree[node*2]+tree[node*2+1];
}

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

与线段树查询同理，不断递归二分。
以下代码要查询的区间是[L,R]。

int query( int node, int left, int right, int L, int R ) // 在区间[L,R]有几个数出现
{
    if ( left>=L&&right<=R ) {
        return tree[node];
    }
    int sum = 0;
    if ( L<=mid ) sum+=query(lson,L,R);
    if ( R>mid )  sum+=query(rson,L,R);
    return sum;
}

查询所有数的第k大值

这是权值线段树的核心，思想如下：
到每个节点时，如果右子树的总和大于等于k，说明第kk大值出现在右子树中，则递归进右子树；否则说明此时的第k大值在左子树中，则递归进左子树，注意：此时要将k的值减去右子树的总和。
为什么要减去？
如果我们要找的是第7大值，右子树总和为4，7−4=3，说明在该节点的第7大值在左子树中是第3大值。
最后一直递归到只有一个数时，那个数就是答案。

int kth( int node, int left, int right, int k ) // 返回整个区间第k大的值
{
    if ( left==right ) return left;
    int rsum = tree[node*2+1];
    if ( k<=rsum ) return kth(rson,k);
    if ( k>rsum )  return kth(lson,k-rsum);
}

 

---

 

例题：Minimum Inversion Number   HDU - 1394

题意：

给出一个序列，一对逆序数就是满足i<j&&a[i]>a[j]条件的一对数字。每次将a数组的最后一个数放到数组的第一位上，原数组向后移动一位，得到一个新的序列，求这些序列中最小的逆序数。（每个数都在0-n-1范围内）

思路：逆序数的性质：一个序列第i次循环的逆序数Pi=P(i-1)+（n-1-a[i]）-a[i] （ 自己画一组样例也好理解 ）。用权值线段树来找出初始状态的逆序对，然后根据性质来更新最小值。

代码：

#include <bits/stdc++.h> // 权值线段树
#define mid ((left+right)/2)
#define lson node*2,left,mid
#define rson node*2+1,mid+1,right
 
using namespace std;
 
const int maxn = 1e5+10;
int tree[maxn*4];
int a[maxn];
 
void built_tree()
{
    memset(tree,0,sizeof(tree));
}
 
void update( int node, int left, int right, int x ) // 树中x出现的次数+1
{
    if ( left==right ) {
        tree[node] ++;
        return ;
    }
    if ( x<=mid ) update(lson,x);
    if ( x>mid )  update(rson,x);
    tree[node] = tree[node*2]+tree[node*2+1];
}
 
int query( int node, int left, int right, int L, int R ) // 在区间[L,R]有几个数出现
{
    if ( left>=L&&right<=R ) {
        return tree[node];
    }
    int sum = 0;
    if ( L<=mid ) sum+=query(lson,L,R);
    if ( R>mid )  sum+=query(rson,L,R);
    return sum;
}
 
int kth( int node, int left, int right, int k ) // 返回整个区间第k大的值
{
    if ( left==right ) return left;
    int rsum = tree[node*2+1];
    if ( k<=rsum ) return kth(rson,k);
    if ( k>rsum )  return kth(lson,k-rsum);
}
 
int main()
{
    int n;
    while ( cin >>n ) {
        built_tree();
        int now=0,x;
        for ( int i=0; i<n; i++ ) {
            scanf("%d",&x);
            a[i] = x;
            now+=query(1,1,n,x+1,n);  // 当前逆序对的个数
            update(1,1,n,x);
        }
        //cout << kth(1,1,n,3) << endl;
        int ans = now;
        for ( int i=n-1; i>=0; i-- ) {   // 逆序对的性质
            now = now - (n-1-a[i]) + a[i];
            ans = min(ans,now);
        }
        cout << ans << endl;
    }
 
    return 0;
}