算法合集之《长方体的体积并》市公开课一等奖百校联赛优质课金奖名师赛课获奖课件.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。,长方体体积并,金陵中学 陆可昱,1/19,矩形,平面中n个矩形面积并计算,方法：,离散,扫描法,线段树,2/19,离散,离散点,矩形,各边（或其延长线）与坐标轴交点,离散单位段,离散点有序化后相邻两个离散点之间距离,3/19,扫描法,把平面分割成条，在每个条中环境变成一维,每一个给定条截面都可表现为其相邻两个条截面中任意一个小修改,4/19,线段树,二叉树,每个结点表示一区间a,b,b-a1:,c=(a+b)div 2,a,c及c,d,5/19,长方体,三维空间中n个长方体体积并计算,方法：,离散,扫描法,存放平面,6/19,二重二叉树,存放平面,x轴二叉树,y轴二叉树,7/19,矩形示意,8/19,标号,根结点为1,非叶子结点i,左子结点：2*i,右子结点：2*i+1,Tx1y1表示一个平面区间,x1：x轴二叉树,y1：y轴二叉树,9/19,10/19,插入及删除,C：统计Tx1y1覆盖次数,最终到达结点：,水平分量：Ax,垂直分量：Ay,p,Ax,q,Ay：修改Tpq.C,11/19,12/19,面积计算,M：统计Tx1y1中矩形面积并,Tx1y1.C0,Tx1y1.C=0,AEIH+EBFI+IFCG+HIGD,AEIH,AEIH,ABFH,AEGD,13/19,修改面积,碰到结点标号：,水平分量：Sx,垂直分量：Sy,14/19,15/19,p,Sx,q,Sy：修改Tpq.M,深度较深结点,标号大,16/19,时间复杂度,修改C：O(lg,2,n),修改M：O(lg,2,n),总复杂度：O(n*lg,2,n),17/19,拓展,方法：,离散,扫描法,存放块,d重二叉树,18/19,谢谢,19/19,