樹狀數組

什麼是樹狀數組？

簡單來說，就是暴力周遊數組來解決區間問題等，不過周遊的路徑使用了位運算來進行壓縮，複雜度是O(log2(n))這樣就不會逾時了（為所欲為？）。
lowbit()操作

其核心是神奇的lowbit操作，lowbit(x)=x&(-x)，它的功能是找到x的二進制數的最後一個1，原理是利用負數的補碼表示，補碼是原碼取反加一。例如x=6=00000110(2)，-x=x補=11111010(2)，那麼lowbit(x)=x&(-x)=10(2)=2。

從lowbit()引出數組a[]，a[x]的值是把ax(題目輸入初始值)和他前面的m個數相加，如下表所示：

圖形化：

那麼通過數組a[]，就可以求sum,例如sum(8)=a[8]，sum(7)=a[7]+a[6]+a[4]，sum(6)=a[6]+a[4]，如此一來不就是我們要的路徑壓縮了嗎？

同樣地，更新ax時也要更新a[]，例如更新a3，那麼首先更改a[3]；然後3+lowbit(3)=4,更改a[4]；接着4+lowbit(4)=8，更改a[8]。

例題

傳送門: HDU-3015

One day Sophia finds a very big square. There are n trees in the square. They are all so tall. Sophia is very interesting in them.

She finds that trees maybe disharmony and the Disharmony Value between two trees is associated with two value called FAR and SHORT.

The FAR is defined as the following:If we rank all these trees according to their X Coordinates in ascending order.The tree with smallest X Coordinate is ranked 1th.The trees with the same X Coordinates are ranked the same. For example,if there are 5 tree with X Coordinates 3,3,1,3,4. Then their ranks may be 2,2,1,2,5. The FAR of two trees with X Coordinate ranks D1 and D2 is defined as F = abs(D1-D2).

The SHORT is defined similar to the FAR. If we rank all these trees according to their heights in ascending order，the tree with shortest height is ranked 1th.The trees with the same heights are ranked the same. For example, if there are 5 tree with heights 4,1,9,7,4. Then their ranks may be 2,1,5,4,2. The SHORT of two trees with height ranks H1 and H2 is defined as S=min(H1,H2).

Two tree’s Disharmony Value is defined as F*S. So from the definition above we can see that, if two trees’s FAR is larger , the Disharmony Value is bigger. And the Disharmony value is also associated with the shorter one of the two trees.

Now give you every tree’s X Coordinate and their height , Please tell Sophia the sum of every two trees’s Disharmony value among all trees.

input:

There are several test cases in the input

For each test case, the first line contain one integer N (2 <= N <= 100,000) N represents the number of trees.

Then following N lines, each line contain two integers : X, H (0 < X,H <=1,000,000,000 ), indicating the tree is located in Coordinates X and its height is H.

output:

For each test case output the sum of every two trees’s Disharmony value among all trees. The answer is within signed 64-bit integer.

Sample Input:

複制

Sample Output:

1
13

複制

題意

給出N棵樹的坐标X和高度H，定義兩棵樹的不和諧值為FAR*SHORT，其中FAR=abs(x1-x2)，SHORT=min(h1,h2)，注意此時的x,h是排序後的排名，且有同名情況。求總的不和諧值。

分析

資料處理：

讀入pair<坐标X，原始下标>x[]，排序後處理同名情況，高度H同理，最後拼接得到pair<相對坐标，相對高度>p[]。
維護兩個樹狀數組：

因為SHORT=min(h1,h2)，那我們對p[]按高度降序排序，然後周遊p[]，每次即得到了目前的最小高度SHORT，然後乘上之前所有樹的FAR即可。

那麼FAR怎麼求呢？？？

此時維護數組cnt[]表示數量，dis[]表示坐标，總FAR=FAR左+FAR右（因為是按高度排序，不是坐标，是以有左右之分），FAR左=左邊樹的數量×目前樹坐标-左邊樹的坐标和，就得到了左邊所有樹到目前樹的距離;

同樣的，FAR右=右邊樹的坐标和-右邊樹的數量×目前樹的坐标。

至此維護數組更新答案就好了。

代碼

#include<cstdio>
#include<algorithm>
#include<string.h>
using namespace std;
typedef long long ll;
const int maxn = 100005;
pair<ll, ll>p[maxn], x[maxn], h[maxn];
int n;
ll cnt[maxn], dis[maxn];
bool cmp(pair<ll, ll>a, pair<ll, ll>b) {
	return a.second > b.second;
}
int lowbit(int x) {
	return x & (-x);
}
ll sum(ll* bit, int x) {
	ll res = 0;
	for (int i = x; i > 0; i -= lowbit(i))
		res += bit[i];
	return res;
}
ll sum(ll* bit, int from, int to) {
	return sum(bit, to - 1) - sum(bit, from - 1);
}
void update(ll* bit, int x, ll y) {
	for (int i = x; i <= maxn; i += lowbit(i))
		bit[i] += y;
}
int main() {
	while (~scanf("%d", &n)) {
		//1.資料處理
		for (int i = 1; i <= n; i++) {
			scanf("%lld%lld", &x[i].first, &h[i].first);
			x[i].second = h[i].second = i;
		}
		sort(x + 1, x + n + 1);
		sort(h + 1, h + n + 1);
		ll tx = x[1].first, th = h[1].first, ans = 0;
		x[1].first = h[1].first = 1;
		for (int i = 2; i <= n; i++) {//同名處理
			if (x[i].first == tx)
				x[i].first = x[i - 1].first;
			else {
				tx = x[i].first;
				x[i].first = i;
			}
			if (h[i].first == th)
				h[i].first = h[i - 1].first;
			else {
				th = h[i].first;
				h[i].first = i;
			}
		}
		for (int i = 1; i <= n; i++) {
			p[x[i].second].first = x[i].first;
			p[h[i].second].second = h[i].first;
		}
		//2.維護兩個樹狀數組
		sort(p + 1, p + 1 + n, cmp);//高度降序
		memset(cnt, 0, sizeof(cnt));
		memset(dis, 0, sizeof(dis));
		for (int i = 1; i <= n; i++) {
			ll cx = p[i].first, ch = p[i].second;//目前樹坐标和高度
			ll left = sum(cnt, 1, cx), right = sum(cnt, cx + 1, maxn);//左邊樹的數量和右邊樹的數量
			ans += ch * (left * cx - sum(dis, 1, cx) + sum(dis, cx + 1, maxn) - right * cx);
			update(cnt, cx, 1);//更新數量
			update(dis, cx, cx);//更新坐标
		}
		printf("%lld\n", ans);
	}
	return 0;
}

複制

小結

看見求和，坐标等關鍵詞時，普通模拟會逾時則可以考慮轉換成樹狀數組題型來求解，重點是如何轉換，若要用到多個樹狀數組時，一般會有最值比較排序。

樹狀數組-HDU3015 Disharmony Trees樹狀數組例題小結相關推薦

目錄

樹狀數組

例題

題意

分析

代碼

小結

相關推薦