萌新求助,关于树套树做矩形加矩形求和
  • 板块学术版
  • 楼主灵华
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/2/8 20:51
  • 上次更新2023/10/24 01:22:24
查看原帖
萌新求助,关于树套树做矩形加矩形求和
68882
灵华楼主2023/2/8 20:51

维护两棵线段树套线段树,记为A和B。

每次矩形加的时候,在A的外层上找到对应区间,对内层进行区间加,维护区间和。

在B的外层上在找到对应区间之前遍历到的所有节点,对那些节点的内层线段树区间加,维护区间和。

然后查询一个矩形和的时候,就是在B的外层对应位置上找到对应区间,区间求和。

在A的外层上在找到对应区间之前遍历到的所有节点,计算与询问区间的交的面积作为系数,区间求和。




这么搞会出现啥问题吗?

2023/2/8 20:51
加载中...