rjHwcu92rXjy/m0+rHttcTP37bOo6zEx8O0sci9z9Xiwb249s/fts61xMio1rW089ChoaPI57n7vdq148v5tPqx7bXEz9+2zrXEyKjWtdChu/LV39Ta1q7HsLj5sb7OtLG7uLK4x6Os1PK9q8bkyKjWtbj80MLOqrWxx7DP37bOtcTIqNa1oaM8L3A+CgoKCjxwcmUgY2xhc3M9"brush:java;">// 插入 void Insert(int left,int right,int height,int num){ // 若插入的线段完全覆盖当前节点所表示的线段 if(intervalTree[num].left == left && intervalTree[num].right == right){ // 更新权值(高度) if(intervalTree[num].height < height){ intervalTree[num].height = height; }//if intervalTree[num].cover = 1; return; }//if // 当前节点的左子节点所代表的线段包含插入的线段 if(right <= intervalTree[num].mid){ Insert(left,right,height,2*num); }//if // 当前节点的右子节点所代表的线段包含插入的线段 else if(left >= intervalTree[num].mid){ Insert(left,right,height,2*num+1); }//if // 插入的线段跨越了当前节点所代表线段的中点 else{ Insert(left,intervalTree[num].mid,height,2*num); Insert(intervalTree[num].mid,right,height,2*num+1); }//else }
而最后计算面积并时，需要遍历整个线段树，因为这样才能确定每个从根节点到叶节点的路径上，即每个元线段上（形如[a,a+1)的线段），最大的高度是多少。统计过程从根向叶遍历，遍历过程中统计高度的最大值，并在叶节点上进行计算，非叶节点的计算结果是其左右子节点的计算结果之和。实现的代码如下(因为计算结果的数据超过了int的范围，所以使用long long 数据类型):
// 计算面积
long long Cal(int h,int num){
// 统计过程从根向叶遍历，遍历过程中统计高度的最大值
if(h > builds[num].height){
builds[num].height = h;
}//if
// 叶节点上进行计算
if(builds[num].left + 1 == builds[num].right){
long long area = builds[num].height *
(hash[builds[num].right] - hash[builds[num].left]);
return area;
}//if
// 非叶节点的计算结果是其左右子节点的计算结果之和
return Cal(builds[num].height,2*num) +
Cal(builds[num].height,2*num+1);
}