algorithm - 范围内不同元素的总和

Question

考虑一个数组(基于 0 的索引)我必须找到不同的总和所有可能范围 [i,n] 的元素，其中 0< i < n

示例:

arr={1,2,1,3}

sum_range[0,3]={1,2,3}=6
sum_range[1,3]={1,2,3}=6
sum_range[2,3]={1,3}=4
sum_range[3,3]={3}=3  

O(n^2) 解决方案是一种可能的解决方案，虽然我找不到好的教程，但我已经阅读了持久线段树也可以做到这一点。

能否在小于 O(N^2) 的时间内解决？

如果有人指出持久线段树请解释或提供一些好的链接？

Answer 1

这可以通过简单的动态规划算法在 O(n) 中完成。

从数组的后面开始，使用一个基于散列的容器来存储你已经遇到过的数字。最后一个元素的值，即 sum_range[n-1] 设置为 arr[n-1]。之后，sum_range[i] 的值应计算如下:

• 如果 arr[i] 不在所见数字的集合中，sum_range[i] = sum_range[i+1]+arr[i]
• 否则，sum_range[i] = sum_range[i+1]

由于检查散列容器中的值的成本是 O(1) 并且将项目添加到散列容器的成本对于 n 个项目分摊 O(1)，因此该算法的总成本是 O(n) .

与使用O(1)空间的O(n²)算法相比，该算法为哈希容器使用了额外的O(n)空间。