【资料下载】长方体的体积并

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