1、长方体体积并 金陵中学 陆可昱1/19矩形n平面中n个矩形面积并计算n方法：n离散n扫描法n线段树2/19离散n离散点n矩形各边（或其延长线）与坐标轴交点n离散单位段n离散点有序化后相邻两个离散点之间距离3/19扫描法n把平面分割成条，在每个条中环境变成一维n每一个给定条截面都可表现为其相邻两个条截面中任意一个小修改4/19线段树n二叉树n每个结点表示一区间a,bnb-a1:nc=(a+b)div 2na,c及c,d5/19长方体n三维空间中n个长方体体积并计算n方法：n离散n扫描法n存放平面6/19二重二叉树n存放平面nx轴二叉树ny轴二叉树7/19矩形示意8/19标号n根结点为1n非叶子结
2、点in左子结点：2*in右子结点：2*i+1nTx1y1表示一个平面区间nx1：x轴二叉树ny1：y轴二叉树9/1910/19插入及删除nC：统计Tx1y1覆盖次数n最终到达结点：n水平分量：Axn垂直分量：AynpAx,qAy：修改Tpq.C11/1912/19面积计算nM：统计Tx1y1中矩形面积并nTx1y1.C0nTx1y1.C=0nAEIH+EBFI+IFCG+HIGDnAEIHnAEIHnABFHnAEGD13/19修改面积n碰到结点标号：n水平分量：Sxn垂直分量：Sy14/1915/19npSx,qSy：修改Tpq.Mn深度较深结点n标号大16/19时间复杂度n修改C：O(lg2n)n修改M：O(lg2n)n总复杂度：O(n*lg2n)17/19拓展n方法：n离散n扫描法n存放块nd重二叉树18/19谢谢19/19
