我有一个很大的间隔[0 ... 2^32 - 1]。大约有2个20点，有一些坐标和值，例如：
1; 435
5; 5454
345345; 5485;
9999999; 43435
4294967294; 35353
我也有一套时间间隔间隔数小于
2^22例如，1 3; // sum is 435
1 3535; // sum is 435 + 5454
99994 4294967294; // sum is 5485 + 43435 + 35353
对于每个区间，我必须计算和模
2^32。有一个简单的算法我可以在每个间隔的所有点上迭代它需要O（查询数*点数）。太慢了。
有更快的算法吗？
最佳答案
把要点分类在这些点上迭代并计算到每个点的值的运行和将总和存储在数组中当你想计算一个区间的和时，通过二进制搜索找到上下限，然后查找上下限和。这些和的差就是区间的和。
对于您给出的示例，这些点的索引如下：
{0: 1, 1: 5, 2: 345345, 3: 9999999, 4: 4294967294}
总数如下：
{0: 0, 1: 435, 2: 5889, 3: 11374, 4: 54809, 5: 90162}
计算区间的和，找出不大于
[a..b]和p(a)的最小点的指数p(b)和a，并返回b。对于1和3，我们找到索引0和0结果是
sums[p(b)+1] - sums[p(a)]。对于1和3535，我们找到指数0和1结果是
sums[1] - sums[0]。对于99994和4294967294，我们找到了索引2和4结果是
sums[2] - sums[0]。准备和的数组需要O（点数）。每个查询取o（log（点数））。