《算法合集之《二分法统计问题》.ppt》由会员分享，可在线阅读，更多相关《算法合集之《二分法统计问题》.ppt（42页珍藏版）》请在三一办公上搜索。
1、二分法统计问题 江苏省淮阴中学 李睿,简介,一定范围内计数问题特点：1 描述简单2 要求对数据动态维护，动态计算解决手段：特殊的统计模式和结构,线段树,动态处理可以映射在一个坐标轴上的一些固定线段，例如求并区间的总长度，或者并区间的个数等等。优点：随时插入一个区间或删除一个已有区间，并同时用低耗费维护需要的性质。,线段树-构造思想,下图显示了一个能够表示1，10的线段树：,线段树-动态数据结构,TypeTnode=Treenode;Treenode=recordB,E:integer;Count:integer;LeftChild,Rightchild:Tnode;End;其中B和E表示了该区
2、间为B,E；Count为一个计数器，通常记录覆盖到此区间的线段的个数。LeftChild和RightChild分别是左右子树的根。,线段树-静态数据结构,用数组B，E，C，LSON，RSON。设一棵线段树的根为v。那么Bv,Ev就是它所表示区间的界。Cv用来作计数器。LSONv，RSONv分别表示了它的左儿子和右儿子的根编号。,线段树-建树,从根对应的区间a，b出发，每次分成两个部分，分别建立对应的左右子树，直到面临一个初等区间x,x+1。,线段树-插入删除线段,将区间c,d插入线段树T(a,b),并设T(a,b)的根编号为v procedure INSERT(c,d;v)Begin mid=
3、(Bv+Ev)div 2;if cBv and Evd then Cv Cv+1else if cmid then INSERT(c,d;RSONv);end,线段树-一个特殊性质举例,要得到线段树上线段并集的长度，增加一个数据域 Mv，讨论：Cv0,Mv=Ev-Bv;Cv=0 且v是叶子结点，Mv=0；Cv=0 且v是内部结点，Mv=MLSONv+MRSONv;,线段树-变形，对点统计,例一,一位顾客要进行n（1n5000）天的购物，每天他会有一些帐单。每天购物以后，他从以前的所有帐单中挑出两张帐单，分别是面额最大的和面额最小的一张，并把这两张帐单从记录中去掉。剩下的帐单留在以后继续统计。输
4、入的数据保证，所有n天的帐单总数不超过1000000，并且每份帐单的面额值是1到1000000之间的整数。保证每天总可以找到两张帐单。,建立点线段树，范围是1，1000000，即每种面额的帐单设为一个叶结点。如果CLSONv0,那么树v中的最小值一定在它的左子树上。如果CRSONv0，它的最大值在右子树上；,一种静态统计方法,例二IOI2001 MOBILES：在一个N*N的方格中，开始每个格子里的数都是0。现在动态地提出一些问题和修改：提问的形式是求某一个特定的子矩阵(x1,y1)-(x2,y2)中所有元素的和；修改的规则是指定某一个格子(x,y)，在(x,y)中的格子元素上加上或者减去一个
5、特定的值A。现在要求你能对每个提问作出正确的回答。1N1024,提问和修改的总数可能达到60000条。,一维序列求和,设序列的元素存储在a中，a的下标是1.n的正整数，需要动态地更新某个ax的值，同时要求出ax1到ay1这一段所有元素的和。,对于序列a1.n，我们设一个数组C1.n，Ci=ai-2k+1+ai,其中k为i在二进制下末尾0的个数10000 k=4 计算Cx对应的2k LOWBIT（x）2k=x and(x xor(x-1),修改一个ax的值 与哪些C相关？例如x=76=(1001010)2，从形式上进行观察，可以得到：p1=1001010 p2=1001100 p3=101000
6、0 p4=1100000 p5=10000000修改Cp1,Cp2,procedure UPDATA(x,A)begin px while(p=n)do begin CpCp+A pp+LOWBIT(p)endend 维护的费用：logn,求a1-ax的和function SUM(x)beginans 0p xwhile(p0)do begin ansans+Cp pp-LOWBIT(p)endreturn ansend,Cp=ap-2k+1+ap下一个p=x-2k,推广为原来的二维问题，把C构造成 Cx，y，其每一维定义与原来相同。推广后算法：两层嵌套，一次维护费用为O(log2n),集合3
7、，4，5，8，19，6,静态二叉排序树实现,构造过程1 递归：,建立所有点坐标的映射Xp 0 作为X映射中的指针procedure BUILD(ID:integer)beginif(ID*2n)then BUILD(ID*2);pp+1；VID=Xp；if(ID*2+1n)then BUILD(ID*2+1);end在主程序中调用BUILD(1),构造过程2 非递归：,方法，依次找出当前点的后继点的下标第一个点first一定为最下层最左边的一个位置,若n个点有L层,则first=2 L-1若当前的点位置为now：如果它有右儿子，即now*2+1=n,则下一 个位置是右子树最左下的点 如果没有右
8、儿子，当now是奇数时，将now除以2，直到now是偶数，最后再将now除以2。,插入一个点x,procedure INSERT(x)beginnow 1repeat SUMnowSUMnow+1 if(Vnow=x)break if(Vnowx)nownow*2 else nownow*2+1until falseEnd其中SUM是记录一棵子树上结点总数删除 的方法是类似的,怎样解决例二,procedure INSERT2(x,A)beginnow 1repeat if(xx)nownow*2 else nownow*2+1until falseendLESS为根及其左子树上所有点位置的权和
9、,求a1.x的元素和function SUM(x):longintbeginans 0now 1repeat if(Vnowx)nownow*2 else nownow*2+1until false return ansend,例三采矿(KOP),金矿的老师傅年底要退休了。经理为了奖赏他的尽职尽责的工作，决定送他一块长方形地。长度为S，宽度为W。老师傅可以自己选择这块地。显然其中包含的采金点越多越好。你的任务就是计算最多能得到多少个采金点。如果一个采金点的位置在长方形的边上，它也应当被计算在内。任务：读入采金点的位置。计算最大的价值。输入：文件KOP.IN的第一行是S和W，(1=s,w=100
10、00);他们分别平行于OX坐标和OY坐标，指明了地域的尺寸。接下来一行是整数n(1=n=15000)，表示采金点的总数。然后是n行，每行两个整数，给出了一个采金点的坐标。坐标范围是(-30000=x,y=30000)。输出：一个整数，最多的采金点数。,样例图示,初步，对X离散化后，图示,对于每一种坐标y，建立成两个点事件(y,+1),(y+w+1,-1)，例如在一个带状区域内有5个点的纵坐标分别是5，3，9，1，9，w=2，标成(1,+1),(4,-1),(3,+1),(6,-1),(5,+1),(8,-1),(9,+1),(12,-1),(9,+1),(12,-1),再将他们按照y的坐标排序
11、，得(1,+1),(3,+1),(4,-1),(5,+1)，(6,-1),(8,-1),(9,+1),(9,+1),(12,-1),(12,-1)我们把后面的标号反映在一个y坐标的映射上，然后从低到高求和,坐标下的求和，这些和中最大的一个就是该带状区域中一个包含最多点数的矩形 在插入或者删除一个点事件之后，能够维持坐标下的值；能够在很短时间内得到中最大的一个值。,实现：,SUMnow对应子树上所有+1，-1标号的和。实现极简单MAXSUMnow，子树上和最大的一个前缀的值。MAXSUM1是一种状态下得到最优解。如何维护？MAXSUM有哪几种可能？1 最大值在左树上；2 最大值正好包含根结点；3
12、 最大值在右树上。,自下而上维护树的特性,找到当前坐标对应点序号now,修正标号为kRepeat SUMnowSUMnow+k MAXSUMnowMax MAXSUMnow*2,SUMnow-SUMnow*2+1,SUMnow-SUMnow*2+1+MAXSUMnow*2+1 now now div 2until now=0,二分法虚拟实现树,二叉树使用之前必须构造出一个空的二叉树 对于任何一个有序表，在对其进行二分查找时，实际上就等于在一个二叉树上进行查找,对于一个表1，3，4，8，9的二分查找，等价于在如下图的二叉排序树上进行查找：,举插入结点的例子，来说明这种虚实现的方法，设LESS表示
13、根及其左树上结点的个数：,procedure INSERT(x)beginl1,rnwhile(l=r)do begin m=(l+r)div 2 if x=Vm LESSmLESSm+1if x=Vm breakif xVm then r m 1 else lm+1 endend,例四最长下降序列,给定一个整数序列a，求最长下降序列的长度。,O（n2),对P进行特殊的限制，即，在所有等价的决策j中，P选择aj最大的那一个 在处理完a1.x-1之后，对于所有长度为Mx-1的下降序列，Px的决策只跟其中末尾最大的一个有关。用另外一个动态变化的数组b，当我们计算完了ax之后，a1.x中得到的所有下
14、降序列按照长度分为L类，每一类中只需要一个作为代表，这个代表在这个等价类中末尾的数最大，我们把它记为bj,1jL。处理当前的一个数ax，我们无需和前面的aj（1jx-1）作比较，只需要和bj（1jL)进行比较。,首先，如果ax=b1，这时ax 仅能构成长度为1的下降序列，同时它又必然是最大的，所以它作为b1的代表,b1=ax。如果前面的情况都不存在，我们肯定可以找到一个j,2jL,有bj-1ax,bjax，这时分析，ax必然接在bj-1后面，行成一个新的长度为j的序列。,这几种情况实际上都可以归结为：处理ax，令bL+1为无穷小，从左到右找到第一个位置j，使bjax,然后则只要将bj=ax,如果j=L+1,则L同时增加。x处以前对应的最长下降序列长度为Mx=j。L 0for x1 to n do beginbL+1无穷小 j1 while(bjax)jj+1 bjax if jL then Lj end,更改成：j1,kL while(jk)do begin m(j+k)div 2 if bmai jm+1 else km-1 end if jL LL+1 bjai,小结,离散化转化问题，构造可统计的结构,Thank you all!,
