树状数组离线 修&查 二维二阶前缀和
感觉是一个很多人用的,但是搜了一圈好像没人写( 首先是一道题。校内模拟赛的,不知道有没有原( 在 n \times m 的平面上有 n 个互不相交的矩形(可以看作平面直角坐标系),左下角为 (x_1, y_1),右上角为 (x_2, y_2)。然后有 q 组询问,每次询问查询给定矩形与平面上每个矩形的面积交的和。 n, m \le 5\times 10^5。 有一个朴素的 O(nm) 的做法,就是差分维护给定的矩形(修改),跑两遍前缀和,第一遍前缀和求出差分数组的原数组,第二遍是为了快速区间求和 […]