树状数组.doc

树状数组先看一个简单的例子：例一：一个学校有个班级，起初每个班级都没有学生，学校的招生办遇到了一个棘手的问题，他们必须随时了解前个班级的总人数（任务一），并且随时会增加若干人到某一个班级（任务二）。我们可以很容易的想到一个简单的算法，开一个长度为的一位数组记录每个班的人数，这样完成任务二的时间复杂度是（），但是完成任务一的时间复杂度是（），所以速度较慢。我们也可以用记录前个班级的总人数，这样完成任务一的时间复杂度是（），但是完成任务二的时间复杂度是（）。以上两种方法在很大的情况下速度都比较慢。所以我们必须引入新的数据结构数状数组。我们同样以例一为例，定义数组，其中表示第个班级的人数。再定义一个数组，其中Ci=ai-2k+1+ai(k为i在二进制形式下末尾0的个数)。由c数组的定义可以得出：c1=a1c2=a1+a2=c1+a2c3=a3c4=a1+a2+a3+a4=c2+c3+a4c5=a5c6=a5+a6=c5+a6如上图所示为时的情况。任务一：定理若ak所牵动的序列为Cp1，Cp2Cpm。则p1=k，而p i+1=pi+2li（li为pi在二进制中末尾的个数）。由此得出更改元素值的方法：若将x添加到ak，则c数组中cp1、cp2、cpm（pmn9 由此得出，c3、c4、c8亦应该添加x。任务二：子序列求和可以转化为求由a1开始的序列a1ak的和S。而在树状数组中求S十分简单： 根据ck=ak-2l+1+ +ak (l为k在二进制数中末尾的个数)我们从k1=k出发，按照ki+1=ki-2lki（lki为ki在二进制数中末尾0的个数） 公式一递推k2，k3，km (km+1=0)。由此得出S=ck1+ck2+ck3 + + ckm例如，计算a1+a2+a3+a4+a5+a6+a7k1=7k2= k1-2l1=7-20=6k3= k2-2l2=6-21=4k4= k3-2l3=4-22=0 即a1+a2+ a3+a4+ a5+a6+ a7=c7+c6+c4数状数组的二维扩展：例二：移动电话（mobiles）：问题假设Tampere区域的第四代手机基地站运行如下。该区域被划分为一些正方形（方阵）。这些正方形构成一个SS的矩阵，矩阵行和列的编号从0到S-1。每个正方形包含一个基地站。由于一个手机可能从一个正方形移动到另一个正方形，或者手机可能开机或关机，所以，在一个正方形内正在使用的手机数目是随时变化的。有时，每个基地站需要将正在使用的手机数的变化用矩阵的行和列报告给主基地站。请你写一个程序，接收这些报告并回答有关任一个长方形区域内当前正在使用的手机总数的查询。输入与输出输入是从标准输入读入整数，对查询的回答是把一个整数写到标准输出。输入格式如下。每个输入占用一行，每行由一个标志数和一些参数构成，标志数和这些参数的格式见下表。标志数 参 数意 义0S用全零来初始化矩阵，大小为 SS. 该标志数仅仅给出一次，并将是第一个标志数。1X Y A将A的值加到矩阵表方阵(X,Y)当前正在使用的手机数目中。A 可正可负。2L B R T 在方阵(X,Y)中查询当前正在使用的手机数的总和，其中L X R，B Y T3结束程序. 该标志数仅仅给出一次并将是最后一个标志数。所有数值将始终在范围内，因而不需要检查。特别是，当A为负时，可以假定它不会把正方形内的数目减到0以下。范围的序号从0开始。例如，对于一个4*4的表，X和Y的变化范围为0X3, 0Y3。对于一个标志数非（不是）2的行，你的程序不应回答任何内容。如果标志数是2，你的程序应当将答案以一个整数的形式写到标准输出来回答查询。编程提示在下面的示例中，整数last是从一行中被读入的最后一个数，answer是包含你的答案的整数变量。如果你用C+编程并使用iostreams,你应当用下列语句实现标准输入的读入和标准输出的写入。cinlast;coutanswerendlflush; 如果你用C+编程并使用scanf和printf, 你应当用下列语句实现标准输入的读入和标准输出的写入:scanf (%d, &last);printf(%dn,answer); fflush (stdout);如果你用Pascal编程，你应当用下列语句实现标准输入的读入和标准输出的写入:Read(last); . Readln;Writeln(answer);示例标准输入 标准输出 解释0 4 初始化矩阵表为 44.1 1 2 3 用+3更新矩阵表(1,2) .2 0 0 2 2 查询矩形 0 X 2, 0 Y 2区域内正在使用的手机数. 3 该查询的答案为3.1 1 1 2 用+2更新矩阵表(1,1)1 1 2 -1 用-1更新矩阵表(1,2)2 1 1 2 3 查询长方形1 X 2, 1 Y 3区域内正在使用的手机数. 4 该查询的答案为43 结束程序.限制矩阵表大小SS11 SS 10241024任意时间的单元值V0 V 215 1 (= 32767)更新量A-215 A 2151 (= 32767)输入中标志数的数目U3 U 60002整个矩阵表中手机数的最大值MM= 230在20个输入中, 16个输入（矩阵表）的大小最多是 512512。同样的我们也可以用一个二维数组表示，其中cI,jai-2ki+1, j-2kj+1+aI, j-2kj+1+aI,j。练习：在一个圆桌上有个碗排成一圈，其中第个碗中分别有个豆子，每次系统或者告诉你往第个碗中加入个豆子，或者询问你从第个碗到第个碗中一共有多少个豆子。旷野战：在一场战争中，我方先进的卫星系统可以了解敌军的所有部队的情况，在旷野中没有任何的障碍物。为了表示方便把整个战场分成了N的区域，卫星系统可能向总指挥部发送敌军的情况，其中包括以下几种信息：敌军在（，）的区域增加了名士兵（可能是新招募的吧）；：敌军把（，）区域的名士兵移动到了（，）区域；：敌军在（，）区域的战斗中被歼灭了人。同时，我方的前线指挥部还会向总指挥部询问在从（，）到（，）的区域中有多少敌方士兵。现在要你编写总指挥部的计算机系统来完成这个任务。在茫茫宇宙中，存在着无数的各种飞行物。在年，人类发现了一个小行星密集区，在这个区域中有着许多小行星，它们会相互碰撞，所以在这个区域中会不断有新的小行星出现，也会有小行星在碰撞中消失，当然小行星的轨道并不是一致的，所以在不断运行中会发生相对位移。科学家们以一颗小行星为原点把这个区域分割成了一块块小立方体区域。太空望远镜会返回这个区域的变化情况：在一个区域内增加了一个小行星；：在一个区域内减少了一个小行星；：一个小行星从一个区域移动到另一个区域；当然，返回的信号是有可能出错的，幸好，中央系统会及时纠正错误（假设纠错时是不会发生错误的）。另外，还会有不断的打来的电话来询问一个区域中有多少小行星。输入文件：第一行有三个整数，表示小行星密集区的大小；以下有个矩阵，其中，第个矩阵的第行的第个数表示在（，）的区域中的小行星数。从第行开始，每行为一个命令，其形式如下：表示在（，）的区域中增加了一个小行星；：B表示在（，）的区域中减少了一个小行星；：C表示从（，）区域移动了一个小行星到（，）区域；：DS表示一位电话号码为S的人打来电话询问在（，）到（，）的区域中有多少小行星；：EN表示向前数，第N个信息是错误的。输出文件： 如果，三个任务无法执行（在该区域中没有小行星供减少或转移）就输出一行。 对于任意一个电话必须返回询问问题的答案。 如果某行信息