欢迎来到天天文库
浏览记录
ID：19508044
大小：566.00 KB
页数：19页
时间：2018-10-02
《国家集训队2003论文集 陆可昱》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、长方体的体积并金陵中学陆可昱矩形平面中n个矩形的面积并的计算方法：离散扫描法线段树离散离散点矩形各边（或其延长线）与坐标轴的交点离散单位段离散点有序化后相邻两个离散点之间的距离扫描法把平面分割成条，在每个条中环境变成一维的每一个给定的条的截面都可表现为其相邻两个条截面中任意一个小的修改线段树二叉树每个结点表示一区间[a,b]b-a>1:c=(a+b)div2[a,c]及[c,d]长方体三维空间中n个长方体的体积并的计算方法：离散扫描法存储平面二重二叉树存储平面x轴二叉树y轴二叉树矩形的示意标号根结点为1
2、非叶子结点i左子结点：2*i右子结点：2*i+1T[x1][y1]表示一个平面区间x1：x轴二叉树y1：y轴二叉树插入及删除C：记录T[x1][y1]的覆盖次数最终达到的结点：水平分量：Ax垂直分量：Ayp∈Ax,q∈Ay：修改T[p][q].C面积计算M：记录T[x1][y1]中矩形的面积并T[x1][y1].C>0T[x1][y1].C=0AEIH+EBFI+IFCG+HIGDAEIHAEIHABFHAEGD修改面积遇到的结点的标号：水平分量：Sx垂直分量：Syp∈Sx,q∈Sy：修改T[p][q]
3、.M深度较深的结点标号大时间复杂度修改C：O(lg2n)修改M：O(lg2n)总的复杂度：O(n*lg2n)拓展方法：离散扫描法存储块d重二叉树谢谢
此文档下载收益归作者所有
