algorithm - 压缩 Fenwick 树中的坐标

Question

假设我们有 n 个连续的空盒子。我们将把 m 组硬币放入一些连续的盒子中，这些盒子是预先知道的。我们将第一组硬币放入 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 来完成。在没有任何改进的情况下，芬威克树需要 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)。最简单(也是我唯一)的想法是遵循一维情况的方式:对于角点的每个坐标x_i，存储角点的所有坐标y_i。这个想法并不是那么聪明，因为它需要O(m^2) = 太多空间。我的问题是

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

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

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) 。