algorithm - 在 Fenwick 树中压缩坐标

Question

假设我们连续有 n 个空框。我们将把 m 组硬币放在一些预先知道的连续盒子里。我们将第 1 组硬币放在从 i_1 到 j_1 的盒子里，第二组放在从 i_2 到 j_2 的盒子里> 等等。

将所有硬币放入箱子后，令箱子i中的硬币数量为c_i。我们希望能够快速确定索引为i = s, s + 1, ... e - 1, e 的盒子里有多少枚硬币，我。 e.我们要计算总和

c_s +c_(s+1) + ... + c_e

高效。这可以通过使用 Fenwick tree 来完成.在没有任何改进的情况下，Fenwick 树需要 O(n) 空间来存储 c_i(在表中；实际上，tree[i] != c_i，值存储得更智能)和 O(log n) 时间来计算上和。

如果我们有这样的情况

• n 太大了，我们无法制作长度为 n 的表格(假设 ~ 10 000 000 000)
• m 足够小(比如 ~ 500 000)

有一种方法可以以某种方式压缩框的坐标(索引)，即只存储索引为i_1、i_2、...、<强>我是。由于存储在 tree[i] 中的值取决于 i 的二进制表示，我的想法是对索引 i_1、 进行排序j_1, i_2, j_2, ... , i_m, j_m 并用长度 O(m)。然后向树 添加一个新值将是直截了当的。此外，要计算该总和，我们只需找到不大于 e 的第一个索引和不小于 s 的最后一个索引。两者都可以用二分查找来完成。之后可以很容易地计算总和。

问题出现在 2D 情况下。现在，我们在平面上有一个由点(x,y) 组成的区域，0 < x,y < n。该区域有 m 个矩形。我们知道它们的左下角和右上角的坐标，我们想计算有多少个矩形包含一个点 (a,b)。最简单(也是我唯一)的想法是遵循 1D 情况下的方式:对于角的每个坐标 x_i 存储角的所有坐标 y_i。这个想法不是很聪明，因为它需要O(m^2) = 太多空间。我的问题是

How to store coordinates in the tree in a more efficient way?

首选使用分域树的问题解决方案，但欢迎任何解决方案!

Answer 1

1. 最简单的方法是使用 map/unordered_map 而不是二维数组。在那种情况下，您甚至不需要坐标压缩。 Map 只会在需要时创建一个键值对，因此它会为输入的每个点创建 log^2(n) 个键值对。
2. 您还可以基于指针(而不是数组)和惰性初始化对树进行分段(您应该只在需要时才创建节点)。
3. 使用二维线段树。可以注意到，对于 y 坐标的每个规范线段，您可以仅为位于 y_min <= y < y_max 区域的点构建 x 坐标的线段树 (1d)，其中 y_min 和 y_max 是 y 的规范线段的边界.这意味着每个输入点将仅在 x 坐标的 log(n) 段树中，这使得总共 O(n log n) 内存。