范围内不同元素的总和

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 2} ) 算法相比，该算法使用额外的 O(n) 空间作为哈希容器。