首页 > 程序开发 > 软件开发 > 其他 >

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

2017-03-03

线段树或树状数组求逆序数:求逆序数的方法有分治,归并,本文只介绍线段树或树状数组求逆序数的办法,众所周知,线段树和树状树可以用来解决区间操作问题。

线段树或树状数组求逆序数:求逆序数的方法有分治,归并,本文只介绍线段树或树状数组求逆序数的办法,众所周知,线段树和树状树可以用来解决区间操作问题,就是因为这两个算法区间操作的时间复杂度很低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
#include
#include
#defineMAX51000
#defineMID(a,b)(a+b)>>1
#defineR(a)(a<<1|1)
#defineL(a)a<<1
typedefstruct{
intnum,left,right;
}Node;
intans[MAX];
NodeTree[MAX<<2];
intn;

voidBuild(intt,intl,intr)//以1为根节点建立线段树
{
intmid;
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);
}

voidInsert(intt,intl,intr,intx)//向以1为根节点的区间[l,r]插入数字1
{
intmid;
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);
}
elseif(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;
}

intQuery(intt,intl,intr)//查询以1为根节点,区间[l,r]的和
{
intmid;
if(Tree[t].left==l&&Tree[t].right==r)
returnTree[t].num;
mid=MID(Tree[t].left,Tree[t].right);
if(l>mid)
{
returnQuery(R(t),l,r);
}
elseif(r<=mid)
{
returnQuery(L(t),l,r);
}
else
{
returnQuery(L(t),l,mid)+Query(R(t),mid+1,r);
}
}


intmain()
{
inta,n,i,t;
scanf("%d",&t);
longlongintk;
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);
}
return0;
}

树状数组:

view plaincopy

//树状数组
#include
#include
#include
#include
usingnamespacestd;
#defineMAX100010
intc[MAX],a[MAX],ans[MAX],n;

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

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

intSum(intx)//向后更新求和
{
intsum=0;
while(x>0)
{
sum+=c[x];
x-=Lowbit(x);
}
returnsum;
}

intmain()
{
inti,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);
}
return0;
}
相关文章
最新文章
热点推荐