c++ - 查找子数组的总和

Question

这是 2017 年 Google APAC 的一个问题。 Problem D: Sum of Sum

Alice presented her friend Bob with an array of N positive integers, indexed from 1 to N. She challenged Bob with many queries of the form "what is the sum of the numbers between these two indexes?" But Bob was able to solve the problem too easily.Alice took her array and found all N*(N+1)/2 non-empty subarrays of it. She found the sum of each subarray, and then sorted those values (in nondecreasing order) to create a new array, indexed from 1 to N*(N+1)/2. For example, for an initial array [2, 3, 2], Alice would generate the subarrays [2], [3], [2], [2, 3], [3, 2], and [2, 3, 2] (note that [2, 2], for example, is NOT a subarray). Then she'd take the sums -- 2, 3, 2, 5, 5, 7 -- and sort them to get a new array of [2, 2, 3, 5, 5, 7].Alice has given the initial array to Bob, along with Q queries of the form "what is the sum of the numbers from index Li to Ri, inclusive, in the new array?" Now Bob's in trouble! Can you help him out?

对于大型数据集，即使在 C++ 中，直接的解决方案也太低效了。有没有更有效的方法来解决这个问题？

目前我正在通过这个 for 循环来构建最终数组:

    multiset<int> sums;
    long long int temp = 0;
    for (long long int len = 1; len <= n; ++len)
    {
        for (int start = 0; start+len <= n; ++start)
        {
            temp = 0;
            for (int i = 0; i < len; ++i)
            {
                temp += arr[start + i]; //arr stores the original array of n digits
            }
            sums.insert(temp);
        }
    }

附言:我当前的实现是 O(n^5) 吗？ 我的错误，我现在可以看到它的 O(n^3) 了。谢谢编辑:到目前为止的答案很有帮助，但对于涉及 n = 200000 项的大型数据集，似乎任何预先计算整个子数组数组的解决方案都太昂贵了。所有提交的解决方案似乎都没有计算子数组的整个数组

Answer 1

如评论中所述，您的解决方案是 O(N^3)，计算为 O(N^2) 乘以 O(N) 总和和多集插入(与 O(N) 相比，您可以忽略) ，请参阅此答案的底部)。

但是交换你的前两个循环，你做的是完全相同的 N*(N+1)/2 求和和插入:

for (int start = 0; start < n; ++start)
{
    for (long long int len = 1; start + len <= n; ++len)
    {
        temp = 0;
        for (int i = 0; i < len; ++i)
        {
            temp += arr[start + i]; //arr stores the original array of n digits
        }
        sums.insert(temp);
    }
}

现在，如果您查看您的 temp 总和，您似乎很明显在做多余的工作。从 start + 1 到 start + 1，然后从 start + 1 到 start + 2，然后从start + 1 到 start + 3 等。对于每个新的 len，您计算的总和是先前值的总和len，加上一项。因此你可以删除这个内部循环:

for (int start = 0; start < n; ++start)
{
    temp = 0;
    for (long long int len = 1; start + len <= n; ++len)
    {
        temp += arr[start + len]; //arr stores the original array of n digits
        sums.insert(temp);
    }
}

所以在 N*(N+1)/2 中你生成了一组值。当然，使用多重集可以隐藏数据排序，但插入通常会花费 log(sums.size())。

单独排序，因为对大小为 S 的集合进行排序需要 S * log(S)，将花费 N*(N+1)/2 * log ( N*(N+1)/2 ) 小于 N*(N+1) * log((N+1)/sqrt(2))。

请注意，因为您有正整数，所以您使用内部循环生成的每组 len 整数都已经排序，因此也许您可以使用它们做一些聪明的事情来加速排序。这也是 multiset 所做的 according to cplusplus.com :

If N elements are inserted, Nlog(size+N) in general, but linear in size+N if the elements are already sorted according to the same ordering criterion used by the container.