［心痛］线段树或树状数组求逆序数

原文地址

线段树或树状数组求逆序数

求逆序数的方法有分治，归并，本文只介绍线段树或树状数组求逆序数的办法，众所周知，线段树和树状树可以用来解决区间操作问题，就是因为这两个算法区间操作的时间复杂度很低O(logN)，才让这种方法具有可行性。

首先先来看一个序列   6 1 2 7 3 4 8 5，此序列的逆序数为5+3+1=9。冒泡法可以直接枚举出逆序数，但是时间复杂度太高O(n^2)。冒泡排序的原理是枚举每一个数组，然后找出这个数后面有多少个数是小于这个数的，小于它逆序数+1。仔细想一下，如果我们不用枚举这个数后面的所有数，而是直接得到小于这个数的个数，那么效率将会大大提高。

总共有N个数，如何判断第i+1个数到最后一个数之间有多少个数小于第i个数呢？不妨假设有一个区间 [1,N]，只需要判断区间[i+1,N]之间有多少个数小于第i个数。如果我们把总区间初始化为0，然后把第i个数之前出现过的数都在相应的区间把它的值定为1，那么问题就转换成了[i+1,N]值的总和。再仔细想一下，区间[1,i]的值+区间[i+1,N]的值=区间[1,N]的值(i已经标记为1)，所以区间[i+1,N]值的总和等于N-[1,i]的值！因为总共有N个数，不是比它小就是比它(大或等于)。

现在问题已经转化成了区间问题，枚举每个数，然后查询这个数前面的区间值的总和， i-[1,i] 既为逆序数。

线段树预处理时间复杂度O(NlogN)，N次查询和N次插入的时间复杂度都为O(NlogN)，总的时间复杂度O(3*NlogN)

树状数组不用预处理，N次查询和N次插入的时间复杂度都为O(NlogN)，总的时间复杂度O(2*NlogN)

线段树:
 

// 线段树
#include <stdio .h>
#include <string .h>
#include <stdlib .h>
#define MAX 51000
#define MID(a,b) (a+b)>>1
#define R(a) (a< <1|1)
#define L(a) a<<1
typedef struct {
    int num,left,right;
}Node;
int ans[MAX];
Node Tree[MAX<<2];
int n;

void Build(int t,int l,int r)         //以1为根节点建立线段树
{
    int mid;
    Tree[t].left=l,Tree[t].right=r;
    if(Tree[t].left==Tree[t].right)
    {
        Tree[t].num=0;
        return ;
    }
    mid=MID(Tree[t].left,Tree[t].right);
    Build(L(t),l,mid);
    Build(R(t),mid+1,r);
}

void Insert(int t,int l,int r,int x)     //向以1为根节点的区间[l,r]插入数字1
{
    int mid;
    if(Tree[t].left==l&&Tree[t].right==r)
    {
        Tree[t].num+=x;
        return ;
    }
    mid=MID(Tree[t].left,Tree[t].right);
    if(l>mid)
    {
        Insert(R(t),l,r,x);
    }
    else if(r< =mid)
    {
        Insert(L(t),l,r,x);
    }
    else
    {
        Insert(L(t),l,mid,x);
        Insert(R(t),mid+1,r,x);
    }
    Tree[t].num=Tree[L(t)].num+Tree[R(t)].num;
}

int Query(int t,int l,int r)           //查询以1为根节点，区间[l,r]的和
{
    int mid;
    if(Tree[t].left==l&&Tree[t].right==r)
        return Tree[t].num;
    mid=MID(Tree[t].left,Tree[t].right);
    if(l>mid)
    {
        return Query(R(t),l,r);
    }
    else if(r<=mid)
    {
        return Query(L(t),l,r);
    }
    else
    {
        return Query(L(t),l,mid)+Query(R(t),mid+1,r);
    }
}


int main()
{
    int a,n,i,t;
    scanf("%d",&t);
    long long int k;
    while(t--)
    {
        scanf("%d",&n);
        memset(Tree,0,sizeof(Tree));  //初始化线段树
        Build(1,1,n);
        for(i=1;i<=n;i++)             //输入n个数
        {
            scanf("%d",&ans[i]);
        }
        for(i=1,k=0;i<=n;i++)
        {
            a=ans[i];
            Insert(1,a,a,1);          //把线段树[ans[i],ans[i]]区间的值插入为1
            k=k+(i-Query(1,1,a));     //查询区间[1,ans[i]]值的总和,逆序数等于i-[1,ans[i]]
        }
        printf("%lld\n",k);
    }
    return 0;
}

树状数组:

// 树状数组
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define MAX 100010
int c[MAX],a[MAX],ans[MAX],n;

int Lowbit(int x)      //返回二进制最后一个1所表示的数
{
  return x&(-x);
}

void Updata(int x)     //向前更新
{
  while(x<=n)
  {
    c[x]++;
    x+=Lowbit(x);
  }
}

int Sum(int x)         //向后更新求和
{
  int sum=0;
  while(x>0)
  {
    sum+=c[x];
    x-=Lowbit(x);
  }
  return sum;
}

int main()
{
  int i,t,k;
    scanf("%d",&t);
  while(t--)
  {
        scanf("%d",&n);
        for(i=1;i<=n;i++)
    {
      scanf("%d",&ans[i]);
    }
    memset(c,0,sizeof(c));        //初始化树状数组
    for(i=1,k=0;i<=n;i++)
    {
      Updata(ans[i]);         //向后更新节点ans[i].k
      k=k+(i-Sum(ans[i]));    //向前查询节点ans[i].k
    }
    printf("%d\n",k);
  }
  return 0;
}