二分,再二分!——从mobiles(ioi2001)一题看多重二分

《二分,再二分!——从mobiles(ioi2001)一题看多重二分》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、二分，再二分！――从Mobiles(IOI2001)一题看多重二分【引言】二分，作为一种非常重要的思想及方法，在许多方面都有着不可替代的作用。信息学的发展一日千里，使“二分”思想中产生新的思路。本文想就一种新颖的二分思想――多重二分谈谈作者的一些粗浅看法。【问题】假设Tampere地区被划分成N*N个单元，形成一个N*N的表格，行、列坐标均为0到N－1，每个单元中有一个移动电话信号发射基地，这些基地不时地报告所在单元的移动电话数的变化情况。写一个程序，接收这些报告并回答一些询问，询问内容是某些矩形区域内目前的移动电话总数。输入有若干行，每行包含一个整数，代表某种操作，后跟若干个整数，是此操作

2、的参数，具体如下表：操作参数含义0N初始化表格，大小为N*N，所有单元的值均为0。此操作只出现一次，且一定是第一条出现的操作。1XYA将(X,Y)单元的移动电话数增加A。A可能为正或负。2LTRB询问从左上角(L,T)到右下角(R,B)的矩形区域内的移动电话总数。3无结束程序，此操作只出现一次，且一定是最后一条出现的操作。对每个２号操作，你要输出一行，包含单个整数，代表当时“询问”操作的答案。范围限制：表格大小N´N1´1£N´N£1024´1024任意时刻单元的值VV0£V£215–1(=32767)每次增加的个数A-215£A£215–1(=32767)输入的操作总数M3£M£60002

3、所有单元的值之和SS£230【初步分析】看到此题，首先会想到一种最简单的算法：开一个1024*1024的数组，记录每个单元的移动电话数，开始全部清零。顺次读入指令，进行操作，“更改”操作只需要直接改动数组上的相应单元，“询问”操作则必须察看从左上角到右下角的所有单元，把其中的移动电话数累加起来并输出。这种算法的优点是简单自然，便于实现。缺点是时间复杂度过高，每条“更改”操作的处理时间是常数级，但每条“询问”操作的处理时间却高达O(n2)级。在最坏情况下，这种算法的时间复杂度为O(m*n2)=60000*1024*1024，显然无法在规定时间内出解。【二分方法】为了便于分析，我们把问题简化一下

4、，降一维来看：只考虑表格中的一行，“更改”操作改动此行中某单元的移动电话数，“询问”操作查询从L单元至R单元共有多少移动电话。如果用前面所说的简单算法，则“更改”操作时间复杂度为O(1)，“询问”操作时间复杂度为O(n)，总体时间复杂度为O(m*n)，是很差的。为了改进，很自然地，我们得到一种二分的思想：将１至n的n个单元划分成两段，再对每段继续二分下去，并记录每一段移动电话数的总和，形成一种树状结构。例如：下面一行单元对应如图所示的分法，括号中的数字代表每一段的移动电话总数：坐标01234567移动电话数352146136－7(4)0－7(25)0－3(11)4－7(14)0－1(8)2－

5、3(3)4－5(10)0(3)1(5)2(2)3(1)6(1)4(4)5(6)7(3)二分之后，“更改”操作需要修改从“根”到“叶”的路径上的各段的移动电话数，因此其时间复杂度为O(log2n)。“询问”操作如何实现呢？注意，(L－R)这一段中的移动电话总数，等于(0－R)段的移动电话总数减去(0－(L－1))段的移动电话总数。而(0－X)段的移动电话总数，可以按照如下方法得到：Total初始为０，从“根”出发，向下查找Ｘ，若某一步是向右走，则将左子树整段的移动电话数加入Total，最后找到Ｘ，再将“叶”节点上记录的移动电话数加入Total，此时的Total值即为(0－Ｘ)段的移动电话总数。

6、这样，“询问”操作的时间复杂度也为O(log2n)，整个算法时间复杂度仅为O(m*log2n)，是很优的。【多重二分】上面分析的是一维的情况，以二分思想为指导，得出了一种比较优的算法。这种算法能否推广到二维的情况呢？可以的。思考一下，一维情况下，“二分”的对象是“段”，或者可以看成“线”，“分”的标准是X坐标。如果推广到二维，那么“二分”的对象理应是“面”，也即表格，“分”的标准应该是X、Y坐标同时考虑，此时“二分”涉及两个不同的标准，因此我们称之为“多重二分”。如何分呢？首先，我们按照X坐标，把整个表格分成部分，并对每个部分按照X坐标继续二分下去，同时，我们将分得的每个部分再按Y坐标进行二

7、分，并记下最终分得的每个部分的移动电话总数。例如，下面的表格可以分成右图的情况，括号中的数字代表每一部分的移动电话总数：　　　XY01032110X:0－1Y:0－1X:0－1Y:0－1(6)X:0－1Y:0－0(5)X:0－1Y:1－1(1)X:0－0Y:0－1X:0－0Y:0－1(4)X:0－0Y:0－0(3)X:0－0Y:1－1(1)X:1－1Y:0－1X:1－1Y:0－1(2)X:1－1Y:0－0(2