求逆序数的三种数据结构比较

对于查询基本上和插入一样。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cassert>
#include <ctime>
using namespace std;
typedef long long int64;
const int maxn = 10001;
int tree[maxn];
int tree1[maxn];
int tree2[maxn*4];

int64 sa, sb, sc;
static inline void insertA(int x)
{
	for (; x; x -= x & -x) ++tree[x];
}

static inline int queryA(int x)
{
	int r = 0;
	for (; x < maxn; x += x & -x) r += tree[x];
	return r;
}

static inline int queryB(int root, int l, int r, int x)
{
	if (l == r) return tree2[root]++;
	int mid = l + r >> 1, lc = root << 1, rc = lc + 1;
	++tree2[root];
	if (x <= mid) return tree2[rc] + queryB(lc, l, mid, x);
	else return queryB(rc, mid+1, r, x);
}

static inline int queryBext(int root, int l, int r, int x)
{
	int ret = 0;
	while (l <= r)
	{
		if (l == r) return ret + tree2[root]++;
		int mid = l + r >> 1, lc = root << 1, rc = lc + 1;
		++tree2[root];
		if (x <= mid)
		{
			ret += tree2[rc];
			r = mid;
			root = lc;
		}
		else
		{
			l = mid + 1;
			root = rc;
		}
	}
	
}

void calA()
{
	srand(123);
	fill(tree, tree+maxn, 0);
	int start = clock();
	for (int i = 0; i < 10000000; ++i)
	{
		int u = rand() % 10000 + 1;
		int a = queryA(u);
		insertA(u);
		sa += a;
	}
	int use = clock() - start;
	cerr << use << endl;
}

void calB()
{
	srand(123);
	fill(tree2, tree2+maxn*4, 0);
	int start = clock();
	for (int i = 0; i < 10000000; ++i)
	{
		int u = rand() % 10000 + 1;
		int a = queryB(1, 1, 10000, u);
		sb += a;
	}
	int use = clock() - start;
	cerr << use << endl;
}

static inline int query_and_insert(int x)
{
	int l = 1, r = 10000;
	int ret = 0;
	while (l <= r)
	{
		int mid = l + r >> 1;
		if (x == mid)
		{
			ret += tree1[x]++;
			break;
		}
		else if (x > mid)
		{
			++tree1[mid];
			l = mid + 1;
		}
		else
		{
			ret += tree1[mid];
			r = mid - 1;
		}
	}
	return ret;
}

void calC()
{
	srand(123);
	fill(tree1, tree1+maxn, 0);
	int start = clock();
	for (int i = 0; i < 10000000; ++i)
	{
		int u = rand() % 10000 + 1;
		sc += query_and_insert(u);
	}
	int use = clock() - start;
	cerr << use << endl;
}

int main()
{
	calA();
	calB();
	calC();
	cerr << sa << " " << sb << " " << " " << sc << endl;
	return 0;
}

求逆序数的三种数据结构比较

原文：http://blog.csdn.net/baihacker/article/details/38779343