Sum of distinct element in a range

Question

Consider a array (0 based index) i have to find the sum of distinct element of all possible range[i,n] where 0< i < n

Example:

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) solution is one possible solution and i have read persistent segment tree can also do this though i can't find good tutorial.

Can it be solved in less than O(N^2) time?

If someone points persistent segment tree please explain or provide some good link?

Answer 1

This can be done in O(n) with a simple dynamic programming algorithm.

Start from the back of the array, and use a hash-based container to store the numbers that you have already encountered. The value of the last element, i.e. sum_range[n-1] is set to arr[n-1]. After that, values of sum_range[i] should be computed as follows:

• If arr[i] is not in the set of seen numbers, sum_range[i] = sum_range[i+1]+arr[i]
• Otherwise, sum_range[i] = sum_range[i+1]

Since the cost of checking a hash container for a value is O(1) and the cost of adding an item to hash container is amortized O(1) for n items, the overall cost of this algorithm is O(n).

Compared to O(n²) algorithm that uses O(1) space, this algorithm uses additional O(n) space for the hash container.

Answer 2

Slice the array (O(n)), then use a set and add values to the set.

In python3.x code, edited after a comment:

array = [1, 2, 1, 3, 5]
range_sum = 0
total_sum = 0
valueset = set ()
for val in reversed(array):
    if val not in valueset :
        valueset.add (val)
        range_sum += val
    total_sum += range_sum

print (total_sum)

Answer 3

There are multiple ways to solve this.

1. sort the array by Arrays.sort();

2. Using set

   long sumOfDistinct(long arr[], int N)
   {
        int size = arr.length;
        HashSet<Long> unique = new HashSet<Long>(); 
        long sum = 0;
        for(int i=0;i<size;i++){
                if(!unique.contains(arr[i])){
                    sum = sum + arr[i];
                    unique.add(arr[i]);
                }
        }
   
        return sum;
    }