本文共 2841 字,大约阅读时间需要 9 分钟。
线段树或树状数组求逆序数
求逆序数的方法有分治,归并,本文只介绍线段树或树状数组求逆序数的办法,众所周知,线段树和树状树可以用来解决区间操作问题,就是因为这两个区间操作的时间复杂度很低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)
- {
- 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)
- {
- 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)
- {
- 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++)
- {
- scanf("%d",&ans[i]);
- }
- for(i=1,k=0;i<=n;i++)
- {
- a=ans[i];
- Insert(1,a,a,1);
- k=k+(i-Query(1,1,a));
- }
- 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)
- {
- 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]);
- k=k+(i-Sum(ans[i]));
- }
- printf("%d\n",k);
- }
- return 0;
- }
转载地址:http://isali.baihongyu.com/