algorithm - 回答大网格矩形查询中的元素总和

Question

考虑一个大网格 10^5 * 10^5。给定 n = 10^8 数据 (x, y, v) 意味着单元格 (x, y) 包含值 v。所有其他单元格都包含 0。关于 q = 10^5 查询被要求给出一个轴平行的矩形。输出应该是该矩形内单元格中包含的所有值的总和。如何处理此类查询？有合适的数据结构吗？

我可以按 x 坐标对数据进行排序，平均而言这会很好。但在最坏的情况下，这将是 O(nq)。有帮助吗？

Answer 1

你没有修改查询，这意味着你不一定要使用复杂的数据结构，如二维二叉树(事实上二维芬威克树存在并且很简单，但是内存消耗太大了问题)。

如果您的查询是离线的，有一个扫线算法:

• 使用 x 坐标对点和查询(矩形的左侧和右侧，视为“事件”)进行排序。
• 维护用于动态一维范围查询的数据结构(例如 Fenwick 树)。假设您有两个函数 add(y, value) 和 sum(y1, y2)。
• 还存储一种“累积计数器”:A[i] 用于每个矩形。
• 对于从左到右的所有事件:
  • 如果是一个点(x, y, value):调用add(y, value)。
  • 如果它是坐标为 (y_down, y_up, ...) 的矩形的左角:A[i] := sum(ydown, yup)。
  • 如果是右角:给定查询的答案是 sum(ydown, yup) - A[i]。

时间复杂度:O((n + q)(log(q) + log(n)))。
内存复杂度:O(n + q)。