假设我们连续有N个空盒子。我们将把M组硬币放在一些已知的消费盒子里。我们把第一组硬币放在i_1到j_1的盒子里，第二组放在i_2到j_2的盒子里，以此类推。
把所有的硬币放进盒子里后，设为第一盒子里硬币的数量。我们希望能够快速确定，索引i=s，s+1，…的盒子里有多少硬币e-1，e，也就是说，我们要计算和
c_s +c_(s+1) + ... + c_e
很有效率这可以通过使用Fenwick tree来完成。在没有任何改进的情况下，fenwick tree需要o（n）空间来存储c_i（在表中；实际上，tree[i]！=c_i，值存储得更智能）和o（log n）计算上和的时间。
如果我们有案子
n对我们来说太大了，不能做一个n长度的表（比如说~10000 000 000 000）
m足够小（假设约50万）
有一种方法可以以某种方式压缩框的坐标（索引），即只存储索引为i_1、i_2的框就足够了，…因为存储在树[i]中的值依赖于i的二进制表示，所以我的想法是对索引i_1、j_1、i_2、j_2、，iúm，júm，并制作一棵长度为O（m）的树为树添加一个新值就可以了。另外，要计算这个和，我们只需要找到第一个不大于e的索引和最后一个不小于s的索引，这两个都可以用二进制搜索来完成。在那之后，总和可以很容易地计算出来。
在二维情况下出现问题。现在，我们在平面上有一个点（x，y）的区域，0
How to store coordinates in the tree in a more efficient way?
使用Fenwick树的问题的解决方案是首选的，但是每个解决方案都是受欢迎的！
最佳答案
最简单的方法是使用map/无序映射而不是2d数组。在这种情况下，你甚至不需要坐标压缩。映射将仅在需要时创建键值对，因此它将为输入的每个点创建日志^2（n）键值对。
您还可以使用延迟初始化（您应该仅在需要时创建节点）基于指针（而不是数组）对树进行分段。
使用二维段树可以注意到，对于每个Y坐标的标准段，只能为位于Y最小
关于algorithm - 在Fenwick树中压缩坐标，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/23534356/