维护两棵线段树套线段树,记为A和B。
每次矩形加的时候,在A的外层上找到对应区间,对内层进行区间加,维护区间和。
在B的外层上在找到对应区间之前遍历到的所有节点,对那些节点的内层线段树区间加,维护区间和。
然后查询一个矩形和的时候,就是在B的外层对应位置上找到对应区间,区间求和。
在A的外层上在找到对应区间之前遍历到的所有节点,计算与询问区间的交的面积作为系数,区间求和。
这么搞会出现啥问题吗?