This is a question from the 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?
The straight forward solution is too inefficient even in c++ for large data sets. Is there a more efficient way to solve this?
Currently i'm going through this for loop to construct the final array:
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);
}
}
P.S: Is my current implementation O(n^5)? My mistake, I can see how its O(n^3) now. Thank you
Edit: Answers so far have been helpful but with large datasets involving n = 200000 items, it appears that any solution that pre calculates the entire array of subarrays is too expensive. All the submitted solutions don't appear to calculate the entire array of subarrays
O(n^5)
, but simple solution will run inO(T*Q*N^2*logN)
.Is there a more efficient way to solve this?
then the answer is clearly yes, because some people solved it. If it isIs my current implementation O(n^5)?
then it is no. You have 3 loops it is O(n^3)