《算法合集之二分法统计问题精品文稿.ppt》由会员分享，可在线阅读，更多相关《算法合集之二分法统计问题精品文稿.ppt（42页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、算法合集之二分法统计问题第1页，本讲稿共42页简介l一定范围内计数问题特点：l1描述简单l2要求对数据动态维护，动态计算l解决手段：特殊的统计模式和结构第2页，本讲稿共42页线段树动态处理可以映射在一个坐标轴上的一些固定线段，例如求并区间的总长度，或者并区间的个数等等。优点：随时插入一个区间或删除一个已有区间，并同时用低耗费维护需要的性质。第3页，本讲稿共42页线段树-构造思想l下图显示了一个能够表示1，10的线段树：第4页，本讲稿共42页线段树-动态数据结构TypeTnode=Treenode;Treenode=recordB,E:integer;Count:integer;LeftChil
2、d,Rightchild:Tnode;End;其中B和E表示了该区间为B,E；Count为一个计数器，通常记录覆盖到此区间的线段的个数。LeftChild和RightChild分别是左右子树的根。第5页，本讲稿共42页线段树-静态数据结构l用数组B，E，C，LSON，RSON。设一棵线段树的根为v。那么Bv,Ev就是它所表示区间的界。Cv用来作计数器。LSONv，RSONv分别表示了它的左儿子和右儿子的根编号。第6页，本讲稿共42页线段树-建树l从根对应的区间a，b出发，每次分成两个部分，分别建立对应的左右子树，直到面临一个初等区间x,x+1。第7页，本讲稿共42页线段树-插入删除线段l将区间
3、c,d插入线段树T(a,b),并设T(a,b)的根编号为vlprocedureINSERT(c,d;v)lBeginlmid=(Bv+Ev)div2;lifcBvandEvdthenCvCv+1lelse ifcmidthenINSERT(c,d;RSONv);lend第8页，本讲稿共42页线段树-一个特殊性质举例l要得到线段树上线段并集的长度，增加一个数据域Mv，讨论：lCv0,Mv=Ev-Bv;lCv=0且v是叶子结点，Mv=0；lCv=0且v是内部结点，Mv=MLSONv+MRSONv;第9页，本讲稿共42页线段树-变形，对点统计第10页，本讲稿共42页例一l一位顾客要进行n（1n500
4、0）天的购物，每天他会有一些帐单。每天购物以后，他从以前的所有帐单中挑出两张帐单，分别是面额最大的和面额最小的一张，并把这两张帐单从记录中去掉。剩下的帐单留在以后继续统计。输入的数据保证，所有n天的帐单总数不超过1000000，并且每份帐单的面额值是1到1000000之间的整数。保证每天总可以找到两张帐单。第11页，本讲稿共42页l建立点线段树，范围是1，1000000，即每种面额的帐单设为一个叶结点。l如果CLSONv0,那么树v中的最小值一定在它的左子树上。l如果CRSONv0，它的最大值在右子树上；第12页，本讲稿共42页一种静态统计方法l例二IOI2001MOBILES：l在一个N*N
5、的方格中，开始每个格子里的数都是0。现在动态地提出一些问题和修改：提问的形式是求某一个特定的子矩阵(x1,y1)-(x2,y2)中所有元素的和；修改的规则是指定某一个格子(x,y)，在(x,y)中的格子元素上加上或者减去一个特定的值A。现在要求你能对每个提问作出正确的回答。1N1024,提问和修改的总数可能达到60000条。第13页，本讲稿共42页一维序列求和l设序列的元素存储在a中，a的下标是1.n的正整数，需要动态地更新某个ax的值，同时要求出ax1到ay1这一段所有元素的和。第14页，本讲稿共42页l对于序列a1.n，我们设一个数组C1.n，Ci=ai-2k+1+ai,其中k为i在二进制
6、下末尾0的个数1001010110010000k=4l计算Cx对应的2kLOWBIT（x）2k=x and(x xor(x-1)第15页，本讲稿共42页l修改一个ax的值与哪些C相关？例如x=76=(1001010)2，从形式上进行观察，可以得到：p1=1001010p2=1001100p3=1010000p4=1100000p5=10000000l修改修改Cp1,Cp2,第16页，本讲稿共42页lprocedureUPDATA(x,A)lbeginlpxlwhile(p0)dolbeginlansans+Cplpp-LOWBIT(p)lendlreturn anslendCp=ap-2k+1
7、+ap下一个下一个p=x-2k第18页，本讲稿共42页l推广为原来的二维问题，把C构造成Cx，y，其每一维定义与原来相同。l推广后算法：两层嵌套，一次维护费用为O(log2n)第19页，本讲稿共42页l集合3，4，5，8，19，6静态二叉排序树实现第20页，本讲稿共42页构造过程1 1 递归：l建立所有点坐标的映射Xlp0作为X映射中的指针lprocedureBUILD(ID:integer)lbeginlif(ID*2n)thenBUILD(ID*2);lpp+1；lVID=Xp；lif(ID*2+1n)thenBUILD(ID*2+1);lendl在主程序中调用BUILD(1)第21页，本
8、讲稿共42页构造过程2 非递归：l方法，依次找出当前点的后继点的下标l第一个点first一定为最下层最左边的一个位置,若n个点有L层,则first=2L-1l若当前的点位置为now：如果它有右儿子，即now*2+1x)nownow*2lelsenownow*2+1luntilfalselEndl其中其中SUM是记录一棵子树上结点总数是记录一棵子树上结点总数l删除的方法是类似的第23页，本讲稿共42页怎样解决例二怎样解决例二lprocedureINSERT2(x,A)lbeginlnow1lrepeatlif(xx)nownow*2lelsenownow*2+1luntilfalselendlL
9、ESS为根及其左子树上所有点位置的权和第24页，本讲稿共42页l求求a1.x的元素和的元素和lfunction SUM(x):longintlbeginlans 0lnow 1lrepeatl if(Vnowx)nownow*2l else nownow*2+1luntil falsel return anslend 第25页，本讲稿共42页例三采矿采矿(KOP)l金矿的老师傅年底要退休了。经理为了奖赏他的尽职尽责的工作，决定送他一块长方形地。长度为S，宽度为W。老师傅可以自己选择这块地。显然其中包含的采金点越多越好。你的任务就是计算最多能得到多少个采金点。如果一个采金点的位置在长方形的边上，
10、它也应当被计算在内。l任务：l读入采金点的位置。计算最大的价值。l输入：l文件KOP.IN的第一行是S和W，(1=s,w=10000);他们分别平行于OX坐 标 和 OY坐 标，指 明 了 地 域 的 尺 寸。接 下 来 一 行 是 整 数 n(1=n=15000)，表示采金点的总数。然后是n行，每行两个整数，给出了一个采金点的坐标。坐标范围是(-30000=x,y=30000)。l输出：l一个整数，最多的采金点数。第26页，本讲稿共42页样例图示第27页，本讲稿共42页l初步，对X离散化后，图示第28页，本讲稿共42页对于每一种坐标y，建立成两个点事件(y,+1),(y+w+1,-1)，例如
11、在一个带状区域内有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的坐标排序，得(1,+1),(3,+1),(4,-1),(5,+1)，(6,-1),(8,-1),(9,+1),(9,+1),(12,-1),(12,-1)我们把后面的标号反映在一个y坐标的映射上，然后从低到高求和第29页，本讲稿共42页l坐标下的求和，这些和中最大的一个就是该带状区域中一个包含最多点数的矩形l在插入或者删除一个点事件之后，能够维持坐标下的值；能够在很短
12、时间内得到中最大的一个值。第30页，本讲稿共42页实现：实现：lSUMnow对应子树上所有+1，-1标号的和。实现极简单lMAXSUMnow，子树上和最大的一个前缀的值。MAXSUM1是一种状态下得到最优解。如何维护？lMAXSUM有哪几种可能？l1最大值在左树上；l2最大值正好包含根结点；l3最大值在右树上。第31页，本讲稿共42页自下而上维护树的特性自下而上维护树的特性l找到当前坐标对应点序号找到当前坐标对应点序号now,修正标号为修正标号为klRepeatlSUMnowSUMnow+kMAXSUMnowMaxMAXSUMnow*2,lSUMnow-SUMnow*2+1,lSUMnow-S
13、UMnow*2+1+MAXSUMnow*2+1llnownowdiv2luntilnow=0第32页，本讲稿共42页二分法虚拟实现树l二叉树使用之前必须构造出一个空的二叉树l对于任何一个有序表，在对其进行二分查找时，实际上就等于在一个二叉树上进行查找第33页，本讲稿共42页l对于一个表1，3，4，8，9的二分查找，等价于在如下图的二叉排序树上进行查找：第34页，本讲稿共42页l举插入结点的例子，来说明这种虚实现的方法，设LESS表示根及其左树上结点的个数：procedureINSERT(x)beginl1,rnwhile(l=r)dobegin m=(l+r)div2ifx=VmLESSmLE
14、SSm+1ifx=VmbreakifxVmthenrm1elselm+1endend第35页，本讲稿共42页例四最长下降序列l给定一个整数序列a，求最长下降序列的长度。O（n2)第36页，本讲稿共42页l对P进行特殊的限制，即，在所有等价的决策j中，P选择aj最大的那一个l在处理完a1.x-1之后，对于所有长度为Mx-1的下降序列，Px的决策只跟其中末尾最大的一个有关。l用另外一个动态变化的数组b，当我们计算完了ax之后，a1.x中得到的所有下降序列按照长度分为L类，每一类中只需要一个作为代表，这个代表在这个等价类中末尾的数最大，我们把它记为bj,1jL。l处理当前的一个数ax，我们无需和前面
15、的aj（1jx-1）作比较，只需要和bj（1jL)进行比较。第37页，本讲稿共42页l首先，如果ax=b1，这时ax仅能构成长度为1的下降序列，同时它又必然是最大的，所以它作为b1的代表,b1=ax。l如果前面的情况都不存在，我们肯定可以找到一个j,2jL,有bj-1ax,bjax，这时分析，ax必然接在bj-1后面，行成一个新的长度为j的序列。第38页，本讲稿共42页l这几种情况实际上都可以归结为：处理ax，令bL+1为无穷小，从左到右找到第一个位置j，使bjax,然后则只要将bj=ax,如果j=L+1,则L同时增加。x处以前对应的最长下降序列长度为Mx=j。lL0lforx1tondolbeginlbL+1无穷小lj1lwhile(bjax)jj+1lbjaxlifjLthenLjlend第39页，本讲稿共42页l更改成：lj1,kLlwhile(jk)dolbeginlm(j+k)div2lifbmaijm+1lelsekm-1lendlifjLLL+1lbjai第40页，本讲稿共42页小结l离散化l转化问题，构造可统计的结构第41页，本讲稿共42页第42页，本讲稿共42页