poj 2481 Cows 树状数组

缘起

树状数组,又叫做Binary Index Tree (BIT) 或者 Fenwick 树.主要用于查询任意两位之间的所有元素之和. 引入树状数组的缘起是为了能高效求数组的片段和.

一般的，一个数组修改一个元素和片段求和的复杂度分别是O(1)和O(N), 但是现在树状数组的引入，以牺牲修改单个元素性能为代价，但是树状数组大大提高了片段求和的性能——树状数组修改单个元素和片段求和的性能都是O(logN).

为了入门树状数组，我们拿 poj 2481 Cows 来练手.

传送门

分析

首先必须要讲解一下什么是树状数组

如上图, 我们说 c是a的树状数组. 树状数组的索引都是从1开始的（不论是c还是a）, 其中树状数组的定义是

1
c[k] = a[k-lowbit(k)+1,...,k]的部分和, k>=1

其中lowbit(k)=k的最低比特位. 例如 k=12=1100, 则lowbit(k)=100 即4, 也就是 lowbit(12)=4

注意, c和a的索引范围是一致的.

于是我们不难知道为什么树状数组求部分和序列（片段和就是2个部分和的差）的性能是O(logn)了. 因为其伪代码是

1
2
3
4
5
6
while(n)
{
    sum += c[n];
    n -= lowbit(n); // 因为 c[n]就是 a[n-lowbit(n)+1,...,n] 之和, 所以利用树状数组进行求和的时候压根不需要顺序扫描, 只需要逐段的扫描就行了
}
return sum;  // sum 就是 a[1,...,n]的部分和

一言以蔽之, 求Sn=a1+…+an这个部分和序列就是用lowbit进行划分.

但是如前所述, 树状数组求解部分和的性能是从O(n)骤降到了O(logn), 性能得到了极大的提升，但是代价就是修改a的一个元素的值的时候, 你需要修改之后去维护a的树状数组c. 不难知道, 修改了 a[k]之后, 你需要维护的树状数组元素是 c[k], c[k+lowbit(k)],… 所以要同步更新, 因此树状数组的引入导致修改单个元素之后维护的代价由O(1)提升到了O(logn)——有得必有失嘛~ 那么树状数组和本题有什么关系呢?

很显然， 要用树状数组解题的话, 一定要将原问题转换为部分和问题. 首先，我们将N个区间排序. 使得”强壮的”区间排在前面. 这里强壮的打引号是因为并不是按照题意中定义的强壮, 而是弱化一点的

1
[s1,e1]排在[s2,e2]前面当且仅当 e1>e2 || (e1==e2 && s1<s2), 即按照e降序、s升序来排序的

那么对于任何一个区间， 要求比他强壮的区间总数只需求出排在他前面的区间中s比他小的元素总个数即可（注意，这里有一个细节，即如果s和e都相等怎么办? 则我们令这种情况是区间相等, 则我们只需要简单认为比两者强壮的区间个数一样就行了）. 令a[i]=”s为i的区间个数”, 则对于任何一个区间[s,e], 比他强壮的区间个数=S[s](即a[1]+…+a[s]部分和序列)，从而我们可以逐个的将区间按照从小到大的顺序加入进来，加的过程中使用O(logn)的代价来维护该树状数组即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include "stdafx.h"
#include <iostream>
#include <algorithm>
#pragma warning(disable:4996)
#define LOCAL
using namespace std;

const int MAX_N = 100005; // 奶牛的最大头数 以及区间的最大数目

struct Cow // 奶牛数据结构
{
	int s,e,id; // [s,e] 是该奶牛的区间, id是该奶牛的id, 不然排序之后会乱的, 但是题目要求输出的是按照原先的顺序

	bool operator <(const Cow &b) const
	{
		return e > b.e || (e==b.e && s < b.s);
	}

	bool operator ==(const Cow &b) const 
	{
		return s == b.s && e == b.e;
	}
} cows[MAX_N]; // cows是奶牛数组, 0索引不用于存储数据

int maxS, cnt[MAX_N],c[MAX_N]; // maxS是所有区间s域的最大值, 因为a[i]="s域为i的区间的个数" 所以, a和c的索引是一致的.cnt[i]是比i号奶牛强壮的奶牛数目 ,c是a的树状数组（其中a[i]=s域为i的区间的个数）, 0 都不用于存储数据

int lowbit(int x) {return x&(-x);} // 返回x的最低比特位，例如6=110, 则lowbit(6)=2, 即最低位非0比特, 这个自己用补码试试就知道了

void maintain(int i,int val) // 维护a[1,..,n]的树状数组, 其中, 我们给a[i]加了val, 则c要进行维护， 代价是O(logn)
{
	while(i<=maxS)
	{
		c[i] += val;
		i+=lowbit(i); // 为什么要加lowbit(i)? 你其实想想加的数是x,如果x<lowbit(i)的话, 则加上之后的数假设是y, 即y=i+x, 则c[y]按照定义就不会包含a[i], 如果x>lowbit(i), 则会漏掉一些, 所以只能加上lowbit(i)
	}
}

int partialsum(int k) // 求a[1,...,k]的部分和
{
	int sum = 0;
	while(k)
	{
		sum += c[k];
		k -= lowbit(k);
	}
	return sum;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in","r",stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	int n; // 奶牛的数目
	while(scanf("%d", &n) && n)
	{
		maxS = -1;
		memset(cnt, 0, sizeof(cnt));
		memset(c, 0, sizeof(c));
		for (int i = 1; i<=n; i++)
		{
			scanf("%d%d", &cows[i].s, &cows[i].e);
			cows[i].s++;
			cows[i].e++; // 加1的原因是, 可能为0，但是树状数组的索引从1开始的.
			cows[i].id = i;
			maxS = max(maxS, cows[i].s);
		}
		sort(cows+1, cows+n+1); // 先升序(按照我们的逻辑就是按照e降序再按照s升序)
		cnt[cows[1].id] = 0; // cows[1].id 是e最大的奶牛, 是没有奶牛能比它强壮的!
		for (int i = 1; i<=n; i++)
		{
			if (i>1 && cows[i] == cows[i-1]) // 如果区间一致的话
			{
				cnt[cows[i].id] = cnt[cows[i-1].id]; //简单赋值就好了
			}
			else
			{
				cnt[cows[i].id] = partialsum(cows[i].s); //否则的话, 比它壮的奶牛就是a[1,...,cows[i].s]的部分和(注意，起点为cows[i].s的区间不会等于cows[i].id这个区间, 否则的话, 就是区间相等, 与本else考虑的情形不符)
			}
			maintain(cows[i].s, 1); // logn代价来维护树状数组
		}
		for (int i = 1; i<=n;i++) printf("%d ", cnt[i]);
		puts("");
	}
	return 0;
}

ac 情况如下

Status Accepted
Time 813ms
Memory 2112kB
Length 1891
Lang C++
Submitted 2019-06-05 22:32:49
Shared
RemoteRunId 20296636