长方体体积并

null长方体的体积并长方体的体积并金陵中学 陆可昱矩形矩形平面中n个矩形的面积并的计算 方法： 离散 扫描法 线段树离散离散离散点 矩形各边（或其延长线）与坐标轴的交点 离散单位段 离散点有序化后相邻两个离散点之间的距离扫描法扫描法把平面分割成条，在每个条中环境变成一维的 每一个给定的条的截面都可现为其相邻两个条截面中任意一个小的修改线段树线段树二叉树 每个结点表示一区间[a,b] b-a>1: c=(a+b) div 2 [a,c]及[c,d]长方体长方体三维空间中n个长方体的体积并的计算 方法： 离散 扫描法 存储平面二重二叉树二重二叉树存储平面 x轴二叉树 y轴二叉树矩形的示意矩形的示意标号标号根结点为1 非叶子结点i 左子结点：2*i 右子结点：2*i+1 T[x1][y1]表示一个平面区间 x1：x轴二叉树 y1：y轴二叉树null插入及删除插入及删除C：记录T[x1][y1]的覆盖次数 最终达到的结点： 水平分量：Ax 垂直分量：Ay p∈Ax,q∈Ay：修改T[p][q].Cnull面积计算面积计算M：记录T[x1][y1]中矩形的面积并 T[x1][y1].C>0 T[x1][y1].C=0 AEIH+EBFI+IFCG+HIGD AEIH AEIH ABFH AEGD修改面积修改面积遇到的结点的标号： 水平分量：Sx 垂直分量：Synullnullp∈Sx,q∈Sy：修改T[p][q].M 深度较深的结点 标号大时间复杂度时间复杂度修改C：O(lg2n) 修改M： O(lg2n) 总的复杂度：O(n*lg2n)拓展拓展方法： 离散 扫描法 存储块 d重二叉树谢谢谢谢