Monthly Archives: August 2010

用树状数组解决区间查询问题

本文扩写自郭神的《树状数组新应用》,在此表示膜拜。

树状数组的学名貌似叫做Binary Index Tree,关于它的基本应用可参考Topcoder上的这篇Tutorial.

树状数组可以看作一个受限制的线段树,它维护一个数组,最经典的树状数组支持的基本操作有两个:(1)改变某一个元素的值 (2)查询某一个区间内所有元素的和。在此基础上,经过简单的变形可以变成支持另一组操作:(1)把一个区间内所有元素都加上一个值 (2)查询某一个元素的值。这两个都是已经泛滥了的东西了,在此不赘述。

简单的树状数组模型是不支持这样一组操作的:(1)把某一个区间内所有元素都加上一个值 (2)查询某一个区间内所有元素的和。当然,这个东西可以用线段树完成,但是线段树占内存比较大,写起来也比较繁(对我这种不会数据结构的人而言)。下面我们用一个改进版的树状数组完成这个任务。

首先一个观察是区间操作总可以变成从最左端开始,比如把区间[3..6]都加10,可以变成[1..6]加10, [1..2]减10。查询也类似。于是下面只关心从最左端开始的情况。定义Insert(p, d)表示把区间[1..p]都加d,Query(p)表示查询区间[1..p]之和。

我们考虑调用一次Insert(p, d)对以后的某次查询Query(q)的影响:

(1) 如果p<=q,总的结果会加上p*d (2) 如果p>q,总的结果会加上q*d

也就是说,Query(q)的结果来源可分为两部分,一部分是Insert(p1,d) (p1<=q),一部分是Insert(p2,d) (p2 > q)。我们用两个数组B[], C[]分别维护这两部分信息,B[i]表示区间右端点恰好是i的所有区间的影响之和,C[i]表示区间右端点大于i的所有区间的影响之和。每当遇到 Insert时,考虑当前的Insert会对以后的Query产生什么影响,更新B和C数组;当遇到Query时,把两部分的结果累加起来。

具体来说,当我们遇到Insert(p, d)时,把B[p]增加p*d,把C[1], C[2], …, C[p-1]都增加d。当遇到Query(p)时,查询B[1]+B[2]+…+B[p]+C[p]*p即可。可以发现对B数组是修改单个元素,查询区间和;对C数组是修改区间,查询单个元素,这恰好对应于一开始说的树状数组支持的基本操作。于是我们用两个树状数组漂亮地完成了任务。:)

示例代码:

#include 

const int MAXN = 1024;
int B[MAXN], C[MAXN];

#define LOWBIT(x) ((x)&(-(x)))

void bit_update(int *a, int p, int d) {
	for ( ; p && p < MAXN ; p += LOWBIT(p))
		a[p] += d;
}

int bit_query(int *a, int p) {
	int s = 0;
	for ( ; p ; p -= LOWBIT(p))
		s += a[p];
	return s;
}

void bit_update2(int *a, int p, int d) {
	for ( ; p ; p -= LOWBIT(p))
		a[p] += d;
}

int bit_query2(int *a, int p) {
	int s = 0;
	for ( ; p && p < MAXN ; p += LOWBIT(p))
		s += a[p];
	return s;
}

inline void _insert(int p, int d) {
	bit_update(B, p, p*d);
	bit_update2(C, p-1, d);
}

inline int _query(int p) {
	return bit_query(B, p) + bit_query2(C, p) * p;
}

inline void insert_seg(int a, int b, int d) {
	_insert(a-1, -d);
	_insert(b, d);
}

inline int query_seg(int a, int b) {
	return _query(b) - _query(a-1);
}

int main() {
	int com, a, b, c;
	while (scanf("%d%d%d",&com,&a,&b) != EOF) {
		a += 2; b += 2;		//防止出现负数
		if (com == 0) {		//更新
			scanf("%d",&c);
			insert_seg(a, b, c);
		} else {			//查询
			printf("%dn",query_seg(a,b));
		}
	}
	return 0;
}

不可能完美的民主

呃……我要说的不是政治体制,是数学或者说经济学。话说我最近已经不太愤了,发现右愤+Nerd(好听点叫Geek)果然是最没前途的组合,有句名言说得好“当别人和美少女舌吻的时候,我和美少女舌战,这就是独立思考和知道太多的结局。”于是我要先把愤属性藏起来,再把Nerd属性藏起来,这样就更好地伪装成人类了,然后就可以和美少女舌吻了。

不扯了入正题,下面要说的是一个选举的问题,我们规定一些看上去完全合情合理的条件,结果却发现没有任何一种选举制度能够满足。从这个意义上讲,任何一种选举制度都是有缺陷的。

下面把问题形式化一下,有N个投票人,K个候选人。每个投票人根据自己的喜好,把这K个人排个序,设这K!种可能的序列组成的集合为L(K)。一个选举制度,就是N个L(K)的笛卡尔积到一个L(K)的映射。前面这句话是吓人用的,说白了就是,选举制度就是一个算法,输入是N个{1..K}的排列,设为R1,R2…Rn,每个排列表示一个投票人的观点,算法的输出是一个{1..K}的排列,表示结合所有的观点计算出一个最终的投票结果。我们要证明的是,不管你用什么算法在某种意义上都是有缺陷的。

我们觉得这选举算法应该满足如下3个条件:

(1)一致性或帕雷托最优性(unanimity): 如果对于全部N个排列,候选人a都排在b的前面,则最终结果a也应该排在b的前面

(2)非独裁性(non-dictatorship): 不存在这样一个i (1 <= i <= n),使得无论输入是什么,总的结果总和Ri相同。

(3)无关因素独立性(independence of irrelevant alternatives, 以下简作IIA): 对于两组可能不同的输入R1,R2…Rn和S1,S2…Sn,如果对于每个i,候选人a和b的相对顺序在Ri和Si里都一致,则由R1,R2…Rn得出的最终结果和由S1,S2…Sn得出的最终结果中,a和b的相对顺序是一样的。

条件(3)的另一种理解方式为,如果我们只关心K个候选人的一个子集,假设说是M个候选人,那么把投票人的排列里我们不关心的人都划去,剩下的仍保持原来顺序,就好像只有这M个候选人一样。然后用同样的选举算法计算,最终这M个人的顺序和原来考虑全部K个人时这M个人的相对顺序是一样的。

这三个条件看上去似乎都很合理,然而我们可以证明,没有任何一种选举算法能同时满足三条。下面我们就证明,满足(1)和(3)的选举算法,必然不满足(2),也就是说,满足一定条件的民主就变成了独裁…… -_-

证明可以分为三部分:

第一部分:存在关键的投票人

我们考虑N个投票人和三个候选人A,B,C。如果所有投票人都把B排在最后,根据一致性,显然在总排名里B排在最后。(我们把这种状态叫做状态1)同理,如果所有人都把B排在最前,总排名里B就在最前。下面我们考虑从状态1开始,编号从1到N的N个投票人,逐个把B从最后改成最前,每当一个投票人改变一次排列,就重新计算一次总的排名。这样的话,一开始B总排名垫底,到最后总排名最高,这中间必定有个变化的过程。我们会发现,这个变化是直接“跳”上去的,也就是说,在中间的某个投票人改变自己的排列后,B的总排名会突然从垫底跳到最高,没有中间过程。

我们用反证法,假设存在一个中间过程,也就是说,在某个投票人(不妨设为第n个)改变主意后,B升到了A和C的中间。不妨设此时总排名是C>B>A(A>B>C同理),现在我们把每个投票人的排列里的A都改到C的前面,由一致性可知,总排名里A也应该在C前面。又因为在投票人的排列里B不是在最前就是在最后,我们改变A,C的顺序对B的相对位置没有影响,由IIA知,因为BA, BC的相对顺序都没变,故总排名里BA,BC的相对顺序也都不变。但此时就出现了矛盾,要想让A改在C前面,BA,BC的相对顺序不可能不变。故假设不成立,第一部分得证。

第二部分:存在决定A与C相对顺序的独裁者

继续第一部分的讨论,我们把B的排名发生跳跃之前的状态,也就是前n-1个人把B排在最前,后面的人都把B排在最后的状态,称为状态2,此时总的排名里B在最后。把B的排名发生跳跃之后的状态,也就是前n个人把B排在最前,后面的人都把B排在最后的状态,称为状态3,此时总的排名里B在最前。

下面我们要证的是,这第n个人就是决定A与C相对顺序的独裁者,他说谁在前面谁就在前面。

设第n个人的投票是A>B>C,此时如果我们只考虑A和B,把C去掉,我们会发现A,B的相对顺序和状态2里是相同的(前n-1个人A<B,后面的人A>B),于是根据IIA,A-B的最终相对顺序也与状态2相同,也就是说,A应该在B前面(因为状态2里B最终在最后)。同理,如果我们只考虑B和C,我们发现B,C的相对顺序和状态3里是相同的(前n个人B>C,后面的人B<C),于是B-C的最终顺序与状态3相同,B应该在C前面(因为状态3里B最终在最前)。于是最终顺序就确定了,是A>B>C。

若设第n个人的投票是C>B>A,同理可得最终顺序是C>B>A。

现在我们只考虑A-C相对顺序,把B完全忽略掉,可以发现A-C的相对顺序是由这第n个人决定的。

注意这里是我认为整个证明里最难理解的一点:根据IIA,在我们决定A-C相对顺序时,B是无关紧要的。尽管我们的证明里出现了B,但最终的结论里没有B的事,引入B只是为了证明独裁者的存在性。在这里我猜很多人都会有的一个疑问是:我们是在如此特殊的状态下才证明了最终结果取决于第n个人,为什么可以得出在所有状态下都成立?如果我不是让前n-1人都把B排最前而后面的人都把B排最后,而是随便乱给一个输入状态呢?(如果你没有这个疑问,说明你的智商远高于我,这是一件概率非常大的事,那样就可以跳过下面的这段解释了)

解释是,我们确实可以乱给一个输入,根本不是前面状态1状态2状态3的样子,但因为现在只考虑A-C相对顺序,我们可以从这个乱给的输入里把其它的候选人都拿掉,结果是不变的,再把B按照状态1的情况插进去,结果还是不变,再逐个地把B从最低提到最高,结果还是不变,但是当总排名里B出现跳跃的时候,独裁者(那第n个人)就找到了。如果我们把此人对A,C的排名交换位置,则总排名里A,C也交换位置。这时你可以再把所有的B都改回一开始乱给的那种输入下的位置,由IIA知B的位置是不影响A-C顺序的。这样我们又回到了原来的输入,只是交换了第n个人对A,C的排名,结果总结果里就跟着变化了。所以第n个人确实是A-C顺序的独裁者。

第三部分:独裁者只有一个

这一部分的证明最简短了。第二部分我们只证明了决定A-C顺序的独裁者存在,当然同理决定B-C顺序和A-B顺序的独裁者也存在,现在的问题是这些独裁者是不是同一个人?

假设A-B独裁者x和B-C独裁者y不是同一个人,则由这两个独裁者的意见就可能决定了A-C的顺序。比如x投票是A<B,y投票是B<C,则必有A<C。但我们知道还有一个A-C独裁者存在(可能是x,y中的一个,也可能是另外一个人),如果他的投票是C<A呢?由这个矛盾可知,三个独裁者只能是同一个人。

最后我们把问题扩展到大于三个候选者,由IIA,前面的所有讨论对任意一个包含三个候选者的子集都仍然成立,于是每个三元组都有一个独裁者。由类似第三部分的证法易知,所有这些独裁者都是同一个。于是总的命题得证。

 

后记:

这其实是博弈论里的一个叫做Arrow不可能性定理的东西,我只是把这个Wiki页面翻译了一下,稍微加入一点自己的理解。在科学松鼠会这里Matrix67这里都生动介绍了此定理在现实生活中的体现,不过都没有涉及具体的证明过程。我觉得这个证明还是颇为锻炼逻辑思维能力的,而且不需要高深的数学,每一步都只是简单的逻辑推理,最终得到了神奇的结论。

这个定理能说明一切选举都无效么?显然不是的。实际上现有的选举制度都是对前面的三个条件作出了妥协的结果,但是他们有很多都工作得很好。三个条件里限制最强的就是IIA,我们也发现了在上面的证明中IIA无处不在,而现有的选举制度大都不满足IIA的要求。比如在科学松鼠会那篇文章里就提到了希拉里和奥巴马竞选时出现的有趣情况。关于此问题的后续研究很多都致力于探索如何适当放宽IIA的要求来更准确地评价选举制度的好坏。当然,天朝研究的是放宽第2个条件……哎呀该就此打住了……