逆序数的求法_计算逆序数[通俗易懂]

目录

一、逆序数的定义

二、归并排序求逆序数

(1) 归并排序的原理及代码

(2) 归并排序求逆序数求逆序数的原理

(3) 归并排序求逆序数的代码

三、树状数组求逆序数

(1) 树状数组的原理及应用

(2) 树状数组求逆序数的原理

(3) 树状数组求逆序数的代码

四、线段树求逆序数

(1) 线段树的原理及应用

(2) 线段树求逆序数的原理

(3) 线段树求逆序数的代码

五、Trie树(字典树)求逆序数

(1) Trie树(字典树)的原理及应用

(2) Trie树(字典树)求逆序数的原理

(3) Trie树(字典树)求逆序数的代码 

一、逆序数的定义

1到n的一个排列 (a1,a2,a3…an) 中， ai>aj且 i>< , 则称有一对逆序对

序列 [5 4 1 3 2]中 有 8 对逆序对, 则称这个序列的逆序数为8。

二、归并排序求逆序数

归并排序作为八大经典排序算法之一，其重要性就不言而喻了。把握好归并排序原理，不仅仅对于算法竞赛，而且对于考研的复习都尤为重要。

(1) 归并排序的原理及代码

“归并”顾名思义就是“归”操作与“并”操作(简单的来说就是分治算法)，“排序”就是将一串序列变为从小到大(或从大到小)进行的有序序列的一个算法。

例如对于一个长度为6 的随机的序列[2,5,8,1,3,7]，我们的目标是将这个序列从小到大排序，即边为[1,2,3,5,7,8]。

具体步骤 

分离问题；将序列依次递归分成若干个小区间，使得每一个小块的问题都相互独立，并且每一个小问题与原问题性质相同 (本题中的小问题和总的问题都为使得序列有序)。。

例如：

代码如下：

void divide(int l,int r)
{
	if(l==r)return;
	int mid=(l+r)>>1;
	divide(l,mid);
	divide(mid+1,r);
	conquer(l,mid,r);
}

处理每一个小问题；使得每一个小问题都得以解决(本题的小问题就是将区间内的序列通过插入排序使其变得有序)。

例如:对于[2,5,8][1,3,7]合并为[1,2,3,5,7,8]

代码如下

void conquer(int l,int mid,int r)
{
	int mid=(l+r)>>1;
	int pos1=l,pos2=mid+1;
	int i=l;
	while(pos1<=mid&&pos2<=r)
	{
		if(a[pos1]<=a[pos2]) tep[i++]=a[pos1++];
		else tep[i++]=a[pos2++];
	}
	for(int j=pos1;j<=mid;j++)tep[i++]=a[j];
	for(int j=pos2;j<=r;j++)tep[i++]=a[j];
	for(int j=l;j<=r;j++)a[j]=tep[j];
} 

合并小问题；这个时候，两个小问题又会被合并成一个小问题，此时的小问题有会满足小问题的性质(区间左边一半都为有序，区间右边一半都为有序，总的来说为无序)。

合并小问题在本问题中就是直接用a数组来体现的。

实现的整体代码如下：

#include<bits/stdc++.h>
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define int long long
using namespace std;
const int N=1e6+7;
int a[N];
int tep[N];
void conquer(int l,int mid,int r)
{
	int pos1=l,pos2=mid+1;
	int i=l;
	while(pos1<=mid&&pos2<=r)
	{
		if(a[pos1]<=a[pos2])tep[i++]=a[pos1++];
		else tep[i++]=a[pos2++];
	}
	for(int j=pos1;j<=mid;j++)tep[i++]=a[j];
	for(int j=pos2;j<=r;j++)tep[i++]=a[j];
	for(int j=l;j<=r;j++)a[j]=tep[j];
} 
void divide(int l,int r)
{
	if(l==r)return;
	int mid=(l+r)>>1;
	divide(l,mid);
	divide(mid+1,r);
	conquer(l,mid,r);
}
signed main()
{
	FAST;
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	divide(1,n);
	for(int i=1;i<=n;i++)cout<<a[i]<<" ";
	return 0;
}

因为对于遍历每一层来说，时间复杂度为O(n)，而分为logn层，所以时间复杂度为O(nlogn)，并且此算法的时间复杂度不随数据的变化而波动，所以此算法的时间复杂度是稳定的。

(2) 归并排序求逆序数求逆序数的原理

通过对于归并排序的理解，我们不难想出有一个这样的规律：

求一个序列的逆序数，同理也可以使用分治求出。对于一个子问题而言，我们使用插入排序的时候，可以很简单的求出左边区间内有多少个比右边区间大的数。

如图所示：

 所以，左边区间内有6个比右边区间大的数。

毫无疑问，每一个子问题的性质都相同(即求左边区间有多少个比右边区间大的逆序数)；

考虑是否独立，答案是肯定的，因为对于每一个问题来说，我们只对当前处理的区间进行求逆序数并且排序，且该操作对父亲区间之间的结果无影响；

(3) 归并排序求逆序数的代码

归并排序求逆序数代码只需要在上方的conquer函数种中加上一行sum+=(mid-pos1+1);即可时间复杂度依然不变。

#include<bits/stdc++.h>
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define int long long
using namespace std;
const int N=1e6+7;
int a[N];
int tep[N];
int sum=0; 
void conquer(int l,int mid,int r)
{
	int pos1=l,pos2=mid+1;
	int i=l;
	while(pos1<=mid&&pos2<=r)
	{
		if(a[pos1]<=a[pos2])tep[i++]=a[pos1++];
		else 
		{
			sum+=(mid-pos1+1); 
			tep[i++]=a[pos2++];
		}
	}
	for(int j=pos1;j<=mid;j++)tep[i++]=a[j];
	for(int j=pos2;j<=r;j++)tep[i++]=a[j];
	for(int j=l;j<=r;j++)a[j]=tep[j];
} 
void divide(int l,int r)
{
	if(l==r)return;
	int mid=(l+r)>>1;
	divide(l,mid);
	divide(mid+1,r);
	conquer(l,mid,r);
}
signed main()
{
	FAST;
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	divide(1,n);
//	for(int i=1;i<=n;i++)cout<<a[i]<<" ";
	cout<<sum;
	return 0;
}

三、树状数组求逆序数

(1) 树状数组的原理及应用

树状数组顾名思义就是一个数组，只是我们把它看做是一棵树罢了。

？？？

“一个数组怎么可能是一棵树？”你可能会有这样的疑问。

首先我先放一个代码：

int lowbit(int x)
{
	return x&-x;
} 

可以发现这段代码虽然看起啦简单，但是实际理解起来却些许困难。

首先要知道一个常识：“计算机中所有的整数都是以补码的形式来存储的。”

所以我们可以知道，该代码实际上就是一个正数的补码与改正数的相反数的补码相“与”，得到的结果为2^k(从0开始，低位到高位，k为最后一个1所在的位置)。

然后，对于每一个节点来说，我们引入一个前缀和的概念(本博文仅仅解释最基本的操作，其实只要满足可加性即可。因而采用最简单的前缀和来解释)。只不过，这个不是简单的将前面所有的数加起来，而是将该点前2^k(从0开始，低位到高位，k为最后一个1所在的位置)累加的结果，即tree[x]存储的是a[x-lowbit(x)+1]~a[x]区间的所有数之和。

例如：

分析：这样做有什么用？

这样能够方便的进行单点查询和区间修改()。

例如：我们想要知道前7项的前缀和，我们仅仅只需要将树状数组中[7,6,4]累加起来即可，其时间复杂度为O(logn)。

同理，若我们想更改第3项的数，我们仅仅只需要更改第[3,4,8…]一直到区间的上限为止，同理其时间复杂度为O(logn)。

所以，单点修改，区间查询的代码如下：

void modify(int pos,int v,int n)
{
	while(pos<=n)
	{
		tree[pos]+=v;
		pos+=lowbit(pos);
	}
}
int query(int l,int r)
{
	int ansl=0,ansr=0;
	l--;//前缀和，减前一个。
	while(l>0)
	{
		ansl+=tree[l];
		l-=lowbit(l); 
	} 
	while(r>0)
	{
		ansr+=tree[r];
		r-=lowbit(r); 
	} 
	return ansr-ansl;
}

(2) 树状数组求逆序数的原理

因为树状数组的作用就是处理单点更新，区间查询的操作，我们可以转化一下思维。

因为逆序数顾名思义就是有多少前面已经出现的数比当前的数的大的个数总和。

所以，我们可以建立一个权值树状数组，在遍历的时候记录已经出现的数的个数。其中，通过遍历的顺序来保证i>j,在寻找时求得有多少个数比当前值大的,其时间复杂度为O(nlogn)。

注：建立权值树状数组时，因为数的值可能过于大，可能会造成空间不足，且空间浪费，所以我们采用离散化的思想。

下面是y总离散化的代码：

#include<bits/stdc++.h>
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define int long long
using namespace std;
const int N=1e6+7;
vector<int>nums; 
int a[N];
int find(int x)
{
	return lower_bound(nums.begin(),nums.end(),x)-nums.begin()+1; //返回的是从1开始的数
} 
signed main()
{
	FAST;
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		nums.push_back(a[i]);
	}
	sort(nums.begin(),nums.end());
	nums.erase(unique(nums.begin(),nums.end()),nums.end());
	for(int i=0;i<nums.size();i++){
		cout<<nums[i]<<" ";
	}
	return 0;
}

(3) 树状数组求逆序数的代码

#include<bits/stdc++.h>
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define int long long
using namespace std;
const int N=1e6+7;
vector<int>nums;
int find(int x){
	return lower_bound(nums.begin(),nums.end(),x)-nums.begin()+1; 
} 
int lowbit(int x){
	return x&-x;
} 
int a[N],tree[N];
void modify(int pos,int v,int n){
	while(pos<=n){
		tree[pos]+=v;
		pos+=lowbit(pos);
	}
}
int query(int l,int r){
	int ansl=0,ansr=0;
	l--;//前缀和，减前一个。
	while(l>0){
		ansl+=tree[l];
		l-=lowbit(l); 
	} 
	while(r>0){
		ansr+=tree[r];
		r-=lowbit(r); 
	} 
	return ansr-ansl;
}
signed main(){
	int n,ans=0;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];	
		nums.push_back(a[i]);
	}
	sort(nums.begin(),nums.end());
	nums.erase(unique(nums.begin(),nums.end()),nums.end());
	for(int i=1;i<=n;i++)
	{
		int v=find(a[i]);
		ans+=query(v+1,n+1);//此时nums可能的最大值为n，n+1避免越界 
		modify(v,1,n+1);
	}
	cout<<ans;
	return 0;
}

四、线段树求逆序数

(1) 线段树的原理及应用

什么是线段树？

线段数顾名思义就是一棵树，他能够在log的时间复杂度上处理区间等问题。

详细请见：

线段树原理及应用

(2) 线段树求逆序数的原理

我么知道，线段树可以处理区间问题，所以，我们仍然可以类似于树状数组求逆序数。

建立一个权值线段树。同样的，为了防止空间过大和空间浪费，我们可以使用离散化进行处理。

(3) 线段树求逆序数的代码

#include<bits/stdc++.h>
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define int long long
using namespace std;
const int N=1e6+7;
struct node
{
	int l;
	int r;
	int v;
}tree[N<<2];
vector<int>nums;
int a[N];
void pushup(int x)
{
	tree[x].v=tree[x<<1].v+tree[x<<1|1].v;	
}
void built(int x,int l,int r)
{
	tree[x]={l,r,0};
	if(l==r)
	{
		return;	
	}
	int mid=(l+r)>>1;
	built(x<<1,l,mid);
	built(x<<1|1,mid+1,r);
	pushup(x);
} 
void modify(int x,int pos,int v)
{
	if(tree[x].l==tree[x].r)
	{
		tree[x].v+=v;
		return; 
	}
	int mid=(tree[x].l+tree[x].r)>>1;
	if(pos<=mid)modify(x<<1,pos,v);
	if(pos>mid)modify(x<<1|1,pos,v);
	pushup(x);
}
int query(int x,int l,int r)
{
	if(tree[x].l>=l&&tree[x].r<=r)
	{
		return tree[x].v;
	}
	int mid=(tree[x].l+tree[x].r)>>1;
	int v=0;
	if(l<=mid)v+=query(x<<1,l,r);
	if(r>mid)v+=query(x<<1|1,l,r);
	return v;
}
int find(int x)
{
	return lower_bound(nums.begin(),nums.end(),x)-nums.begin()+1;
}
signed main()
{
	FAST;
	int n,ans=0;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		nums.push_back(a[i]);
	}
	built(1,1,n+1);
	sort(nums.begin(),nums.end());
	nums.erase(unique(nums.begin(),nums.end()),nums.end());
	for(int i=1;i<=n;i++)
	{
		int v=find(a[i]);
		ans+=query(1,v+1,n+1);
		modify(1,v,1);
	}
	cout<<ans;
	return 0;
}

当然，如果题目给与的空间足够大的话，我们可以不需要离散化，可以采用动态开点线段树的方法求。其时间复杂度仍然是O(nlogn)。

五、Trie树(字典树)求逆序数

(1) Trie树(字典树)的原理及应用

所谓的字典数顾名思义就是将一些字符串通过一种方式结合的一种数据结构,以便用很好的处理一堆字符串的某些共同性质，且性质不以字符串的输入顺序有关。

例如,我们需要存储一些字符串

那么，这些字符串构成的trie树为

其中，圆圈内红色的数字代表点的编号；圆圈外橙色数字表示从根节点到该节点有一个节点；箭头边黑色的字母表示状态转换的条件。

代码如下:

#include<bits/stdc++.h>
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define int long long
using namespace std;
const int N=1e6+7;
char a[N];
int trie[N][26];//trie树 
int sum[N];//记录有多少字符串的数量 
int dfn=0;//时间戳 
void insert(char *str)
{
	int p=0;
	for(int i=0;str[i];i++)
	{
		int u=str[i]-'a';
		if(!trie[p][u])trie[p][u]=++dfn;
		p=trie[p][u];
	}
	sum[p]++;
}
signed main()
{
	FAST;
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a;
		insert(a);
	}
	return 0;
}

(2) Trie树(字典树)求逆序数的原理

首先我们回到本质上来。

什么是逆序数，本质上来说就是满足i<j且ai>aj的这样的一个二元组。

对于处理i<j，我们可以通过遍历的顺序来处理。但是对于判断ai>aj我们可以通过二进制数来判断。

判断两个数的大小，就是判断位数和位数上的数字。

例如对于[12 15 7 2]这个序列来说:

我们可以依次的从高位到低位比大小。

为了使比较更加方便，我们将所有的数补齐高位0。

即 ：

然后进行比较即可。

根据上面的原理，我们不难想出一个规律：

定义一个sum数组，表示在p节点上，经过”1″这个转换条件的数量.

将数依次插入trie树中。若该节点为0，则需要统计该兄弟节点的值ans+=sum[p](在该位比当前数大的数)；若该节点为1，则需要加数量sum[p]++(在该位比当前数大的数)；

如图：

该图树上的圈内红色的数字表示节点的编号；箭头上黑色的数字表示转换条件；圆圈边上的数字表示在p节点上，经过”1″数量；颜色表示不同的插入顺序所产生的贡献值。

(3) Trie树(字典树)求逆序数的代码

#include<bits/stdc++.h>
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;
const int N=1e6+7;
int trie[N*10][2];//trie树开大一点
int sum[N*10];//开大一点
int dfn=0;//时间戳 
long long ans=0;//记得long long
void insert(int v)
{
	int p=0;
	for(int i=31;i>=0;i--)//根据题意扩展到31位
	{
		int u=(v>>i)&1;//从高位到低位取值
		if(!trie[p][u])trie[p][u]=++dfn;
		if(u==0)
		{
			ans+=sum[p];	
		}
		else
		{
			sum[p]++;	
		}
		p=trie[p][u];
	}
}
signed main()
{
	FAST;
	int n,x;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>x;
		insert(x);
	}
	cout<<ans;
	return 0;
}

毫无疑问，这个时间复杂度比上述的更低，只有O(nlog(ai))但是实际上，运行时间却比第一个归并排序要慢。原因是需要开辟很多的空间。

今天的文章逆序数的求法_计算逆序数[通俗易懂]分享到此就结束了，感谢您的阅读。