假设我们连续有n 个空框。我们将把m组硬币放入预先知道的一些连续的盒子中。我们将第一组硬币放入从i_1到j_1的盒子中，将第二组硬币放入从i_2到j_2的盒子中，依此类推。
在将所有硬币放入盒子后，让c_i盒子i中的硬币数量。我们希望能够快速确定索引为 i = s, s + 1, ... e - 1, e的框中有多少硬币 ，即我们要计算总和
c_s +c_(s+1) + ... + c_e
有效率的。这可以通过使用Fenwick 树来完成。在没有任何改进的情况下，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、 ... 、i_m的框就足够了。由于存储在tree[i]中的值取决于 i 的二进制表示，我的想法是对索引i_1、j_1、i_2、j_2、 ... 、i_m、j_m进行排序，并制作一棵长度为O(m)的树。然后向树中添加新值将是直截了当的。此外，为了计算总和，我们只需要找到不大于e的第一个索引最后一个不小于s。两者都可以通过二分搜索来完成。之后，可以很容易地计算总和。
问题发生在二维情况下。现在，我们在平面上有一个点(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 树的问题的解决方案是首选，但每个解决方案都是受欢迎的！