hdu1394 樹狀數組 解法

本題使用樹狀數組果然更加快。

樹狀數組難點：

1 如何遍歷樹

2 如何利用數組數據

建立一個樹狀數組就如上圖紅色部分代表所有的樹狀數組節點了。

基本操作：

查找下一個節點的計算，如不明白下面函數的作用，請查看負數內存存放的問題。

簡而言之就是：內存放是求反+1； 利用這個函數可以神奇地尋找到其單親節點和兄弟節點，比如上圖6->8，6->4或者7->8， 7 -> 6這樣跳轉節點。

這是樹狀數組實現的關鍵了，理解了如何遍歷這樣的樹，就會使用這個數據結構了。

inline int lowbit(int x)
	{
		return x & (-x);//or return x&(x^(x-1));
	}

void update(int i, int val, int len)
	{
		while (i <= len)
		{
			c[i] += val;
			i += lowbit(i);
		}
	}

int getsum(int x)
	{
		int ans = 0;
		while (x > 0)
		{
			ans += c[x];
			x -= lowbit(x);
		}
		return ans;
	}

解決這道題的代碼：

class MinimumInversionNumber_3_TreeArray
{
	static const int SIZE = 5005;
	int *a, *c;//一般數組和樹狀數組
	inline int lowbit(int x)
	{
		return x & (-x);//or return x&(x^(x-1));
	}

	void update(int i, int val, int len)
	{
		while (i <= len)
		{
			c[i] += val;
			i += lowbit(i);
		}
	}

	int getsum(int x)
	{
		int ans = 0;
		while (x > 0)
		{
			ans += c[x];
			x -= lowbit(x);
		}
		return ans;
	}
public:
	MinimumInversionNumber_3_TreeArray() : a((int*)malloc(sizeof(int)*SIZE)), 
		c((int*)malloc(sizeof(int)*SIZE))
	{
		int n, t;  
		while(~scanf("%d",&n))  
		{
			for(int i = 1; i <= n; i++)
			{  
				scanf("%d", &t);  
				a[i] = t + 1;  
			}  

			//memset(c, 0, sizeof(c));最好不要使用memset設置初值
			fill(c, c+n+1, 0);
			int res = 0;  
			for(int i = 1; i <= n; i++)  
			{  
				update(a[i], 1, n);
				res += i - getsum(a[i]);//目前為止，出現了多少個小於等於a[i]的數位getsum(a[i])，所以大於a[i]的數位i-getsum(a[i])，即為逆序數
			}  
			int ans = res;
			for(int i = 2; i <= n; i++)  
			{  
				res += n - 2*a[i-1] + 1;  
				if(res < ans) ans = res;  
			}  
			printf("%d\n", ans);  
		}     
	}

	~MinimumInversionNumber_3_TreeArray()
	{
		free(a);
		free(c);
	}
};