首页 > 代码库 > NYOJ117&& 树状数组求逆序数
NYOJ117&& 树状数组求逆序数
(转)树状数组可以用来求逆序数， 当然一般用归并求。如果数据不是很大， 可以一个个插入到树状数组中， 每插入一个数， 统计比他小的数的个数，对应的逆序为 i- getsum( da
大小关系不变。如： 10 30 20 40 50 与 1 3 2 4 5 的逆序数是相同的定义一个结构体 struct Node{ int data; // 对应数据 int pos; // 数据的输入顺序 };
先对 da
题目链接：click here
预备函数
定义一个Lowbit函数，返回参数转为二进制后,最后一个1的位置所代表的数值.
例如,Lowbit(34)的返回值将是2；而Lowbit(12)返回4；Lowbit(8)返回8。
将34转为二进制,为0010 0010,这里的"最后一个1"指的是从2^0位往前数,见到的第一个1,也就是2^1位上的1.
程序上，((Not I)+1) And I表明了最后一位1的值,
仍然以34为例,Not 0010 0010的结果是 1101 1101(221),加一后为 1101 1110(222), 把 0010 0010与1101 1110作AND,得0000 0010(2).
Lowbit的一个简便求法:（C++）
int lowbit(int x)
{
return x&(-x);
}新建
定义一个数组 BIT，用以维护A的前缀和，则:
具体能用以下方式实现：（C++）
void build()
{
for (int i=1;i<=MAX_N;i++)
{
BIT[i]=A[i];
for (int j=i-1; j>i-lowbit(i);j-=lowbit(j))
BIT[i]+=BIT[j];
}
}修改
假设现在要将A[I]的值增加delta,
那么,需要将BTI[I]覆盖的区间包含A[I]的值都加上K.
这个过程可以写成递归,或者普通的循环.
需要计算的次数与数据规模N的二进制位数有关,即这部分的时间复杂度是O(LogN)
修改函数的C++写法
void edit(int i, int delta)
{
for (int j = i; j <= MAX_N; j += lowbit(j))
BIT[j] += delta;
}求和
- 首先,将ans初始化为0，将i计为k.
- 将ans的值加上BIT[P]
- 将i的值减去lowbit(i)
- 重复步骤2～3，直到i的值变为0
求和函数的C/C++写法
int sum (int k)
{
int ans = 0;
for (int i = k; i > 0; i -= lowbit(i))
ans += BIT[i];
return ans;
}复杂度
初始化复杂度最优为O(N)
单次询问复杂度O(LOG(N))其中N为数组大小
单次修改复杂度O(LONG(N))其中N为数组大小
空间复杂度O(N);
代码：#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=1000001;
const double eps=1e-6;
const double pi=acos(-1.0);
#define lowbit(x) ((x)&(-x))
struct node
{
int data,pos;
} doo[maxn];
int n;
int coo[maxn],poo[maxn];
int cmp(const void *a,const void *b)
{
node *ta=(node *)a;
node *tb=(node*)b;
return ta->data-tb->data;
}
int cmp1(node aa,node bb)
{
return aa.data-bb.data;
}
void updata(int pos,int value)
{
int x=pos;
while(x<=n)
{
coo[x]+=value;
x+=lowbit(x);
}
}
int getsum(int pos)
{
int x=pos,sum=0;
while(x)
{
sum+=coo[x];
x-=lowbit(x);
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1; i<=n; i++)
{
scanf("%d",&doo[i].data);
doo[i].pos=i;
}
qsort(doo+1,n,sizeof(doo[0]),cmp);
// sort(doo,doo+n,cmp1);
int id=1;
poo[doo[1].pos]=1;
for(int i=2; i<=n; i++)
if(doo[i].data=http://www.mamicode.com/=doo[i-1].data) poo[doo[i].pos]=id;>
归并排序合并算法
#include <stdio.h>
#include <string.h>
#define MAXM 1000003
#define INF 0x7fffffff-1;
long long cnt;
int arr[MAXM];
int temp1[MAXM/2+1], temp2[MAXM/2+1];
void Merge(int array[], int start, int mid, int end)// 归并排序中的合并算法
{
int n1, n2,i,k,j;
n1 = mid - start + 1;
n2 = end - mid;
for (i = 0; i < n1; i++) // 拷贝前半部分数组
{
temp1[i] = array[start + i];
}
for ( i = 0; i < n2; i++) // 拷贝后半部分数组
{
temp2[i] = array[mid + i + 1];
}
temp1[n1] = temp2[n2] = INF; // 把后面的元素设置的很大
for ( k = start, i = 0, j = 0; k <= end; k++)// 逐个扫描两部分数组然后放到相应的位置去
{
if (temp1[i] <= temp2[j])
{
array[k] = temp1[i];
i++;
}
else
{
cnt+=n1-i; //逆序对的个数
array[k] = temp2[j];
j++;
}
}
}
// 归并排序
void MergeSort(int array[], int start, int end)
{
if (start < end)
{
int i;
i = (end + start) / 2;
// 对前半部分进行排序
MergeSort(array, start, i);
// 对后半部分进行排序
MergeSort(array, i + 1, end);
// 合并前后两部分
Merge(array, start, i, end);
}
}
int main()
{
//freopen("11.txt","r",stdin);
//freopen("2.txt","w",stdout);
int T,i,n;
scanf("%d",&T);
while(T--)
{
cnt=0;
scanf("%d",&n);
for(i=0; i<n; i++)
{
scanf("%d",arr+i);
}
MergeSort(arr,0,n-1);
printf("%lld\n",cnt);
}
return 0;
}
NYOJ117&& 树状数组求逆序数