算法合集之二分法统计问题.ppt

算法合集之二分法统计问题;简介;线段树;线段树-构造思想;线段树-动态数据结构;线段树-静态数据结构;线段树-建树;线段树-插入删除线段;线段树-一个特殊性质举例;线段树-变形，对点统计;[例一]; 建立点线段树，范围是[1，1000000]，即每种面额的帐单设为一个叶结点。 如果C[LSON[v]]0,那么树v中的最小值一定在它的左子树上。 如果C[RSON[v]]0，它的最大值在右子树上； ;一种静态统计方法;一维序列求和;对于序列a[1..n]，我们设一个数组C[1..n]，C[i]=a[i-2k+1]+…+a[i],其中k为i在二进制下末尾0的个数 10000 k =4 计算C[x]对应的2k LOWBIT（x） 2k =x and (x xor (x-1)) ;修改一个a[x]的值 与哪些C相关？ 例如x=76=(1001010)2，从形式上进行观察，可以得到： p1= 1001010 p2= 1001100 p3= 1010000 p4= 1100000 p5修改C[p1],C[p2],…;procedure UPDATA(x,A) begin p←x while (p=n) do begin C[p]←C[p]+A p←p+LOWBIT(p) end end 维护的费用：logn;求a[1]-a[x]的和 function SUM(x) begin ans ← 0 p ← x while (p0) do begin ans←ans+C[p] p←p-LOWBIT(p) end return ans end ;推广为原来的二维问题，把C构造成 C[x，y]，其每一维定义与原来相同。 推广后算法：两层嵌套，一次维护费用为O(log2n);集合{3，4，5，8，19，6} ;构造过程1 递归：;构造过程2 非递归：;插入一个点x;怎样解决例二;求a[1..x]的元素和 function SUM(x):longint begin ans ← 0 now ←1 repeat if (V[now]=x) ans←ans+LESS[now] if (V[now]=x) break if (V[now]x) now←now*2 else now←now*2+1 until false return ans end ;[例三]采矿(KOP) ;样例图示;初步，对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的坐标排序，得(1,+1),(3,+1),(4,-1), (5,+1)， (6,-1), (8,-1), (9,+1), (9,+1),(12,-1), (12,-1) 我们把后面的标号反映在一个y坐标的映射上，然后从低到高求和 ?;坐标下的求和，这些和中最大的一个就是该带状区域中一个包含最多点数的矩形 在插入或者删除??个点事件之后，能够维持坐标下∑的值；能够在很短时间内得到∑中最大的一个值。 ;实现：;自下而上维护树的特性;二分法虚拟实现树;对于一个表{1，3，4，8，9}的二分查找，等价于在如下图的二叉排序树上进行查找： ;举插入结点的例子，来说明这种虚实现的方法，设LESS表示根及其左树上结点的个数： ;[例四]最长下降序列;对P进行特殊的限制，即，在所有等价的决策j中，P选择a[j]最大的那一个 在处理完a[1..x-1]之后，对于所有长度为M[x]-1的下降序列，P[x]的决策只跟其中末尾最大的一个有关。 用另外一个动态变化的数组b，当我们计算完了a[x]之后，a[1..x]中得到的所有下降序列按照长度分为L类，每一类中只需要一个作为代表，这个代表在这个等价类中末尾的数最大，我们把它记为b[j],1≤j≤L。 处理当前的一个数a[x]，我们无需和前面的a[j]（1≤j≤x-1）作比较，只需要和b[j]（1≤j≤L)进行比较。 ;首先，如果a[x]b[L]，把a[x]接在这个序列的后面，形成了一个长度为L+1的序列.。这时b[L+1]=a[x],即a[x]作为长度为L+1的序列的代表，同时L应该增加1。 另一种可能是a[x]=b[1]，这时a[x] 仅能构成长度为1