How can I use prefix sum of an array to solve this problem?

Question

I attempted this question on hackerrank. It seemed simple enough, and my program ran on small inputs. But my approach was "naive". And failed for more computationally intensive inputs. Here is the question:

Problem Statement

You are given a list of size , initialized with zeroes. You have to perform operations on the list and output the maximum of final values of all the elements in the list. For every operation, you are given three integers , and and you have to add value to all the elements ranging from index to (both inclusive).

Input Format

First line will contain two integers and separated by a single space. Next lines will contain three integers , and separated by a single space. Numbers in list are numbered from to .

Constraints

2 ≤ N ≤ 10^7
1 ≤ M ≤ 2 * 10^5
1 ≤ a ≤ b ≤ N
0 ≤ k ≤ 10^9

Output Format

A single line containing maximum value in the updated list.

Here is the editorial describing how to solve the problem

You are given a list of size N, initialized with zeroes. You have to perform M queries on the list and output the maximum of final values of all the N elements in the list. For every query, you are given three integers a, b and k and you have to add value k to all the elements ranging from index a to b(both inclusive).

First thought which comes into mind after reading this problem will be segment tree with lazy propogation but that will not pass here as N <= 10^7 :)

So, We have to use some different kind of approach. We can do a O(1) update, i.e. given a b k add k to index a and add -k to index (b+1). By doing this kind of update ith number in array will be prefix sum of array from index 1 to i.

So, We can do all M updates in O(M) time. Now we have to check the largest number in the original array. i.e. the index i such that prefix sum attains maximum value.

We can calculate the all prefix sums as well as maximum prefix sum in O(N) time which will get Accepted. Another approach is we can do it in O(MlogM) time because we have to check the value of prefix sum at only 2*M indices. i.e. a and b values of all the updates. See setter's code.

I don't understand how adding k to index a and adding -k to index (b+1) gives us an array in which the the ith number in the array is the prefix sum of the array from index 1 to i.

Answer 1

Consider a new type of query (t2q, type 2 query) of the form $(index, value)$ where we add $value$ to all items from $index$ to the end.

Then the original type of query (t1q, type 1 query) is equivalent to 2 t2q. $(lower, upper, value) \equiv (lower, value) \oplus (upper+1, -value)$. Notice that the second t2q cancels the first t2q over all items that should not be affected

Now, 2 t2q with the same $index$ could be reduced to a single t2q easily. $(index, valueA) \oplus (index, valueB) \equiv (index, valueA+valueB)$. Therefore, we have at most $N=\text{size of our vector}$ type 2 queries. In other words, we can store all those queries in a vector. And if there is an $index$ with no query associated, we just create a "dummy query" using the identity element of our operation (zero in this particular problem).

$$ (index, value) \equiv t2q[index]=value $$

Next, a particular item in our vector $v[j]$ is only affected by a t2q iff $index <= j$. In other words, $v[j]$ is affected by all type 2 queries with lower $index$. To calculate the value of a particular $v[j]$ just add all $values$ of t2q with lower $index$ and add the value of $v[j]$ which is zero.

$$ v'[j] = v[j] + \sum_{i=0}^j{t2q[i]} = \sum_{i=0}^j{t2q[i]} $$

If we iterate from the beginning, then each item can be calculated in $\mathcal{O}(1)$ if we store the previous sum. And simultaneously, we look for the maximum.

$$ v'[j+1] = \sum_{i=0}^{j+1}{t2q[i]} = t2q[j+1] + v'[j] $$

Edit

This approach will take $\mathcal{O}(M+N)$-time and $\mathcal{O}(N)$-space, because we first process every query in $\mathcal{O}(1)$ (updating two positions in our vector), adding $\mathcal{O}(M)$, and then we spend $\mathcal{O}(N)$ looking for the maximum.

Like you said, there are $\mathcal{O}(M)$ values different than zero in $t2q$. We can ignore those zeros using a Self-balancing Binary Search Tree instead of a vector. Then we go from $\mathcal{O}(1)$ to $\mathcal{O}(lg\,M)$ while updating every entry (process every query) and from $\mathcal{O}(N)$ to $\mathcal{O}(M)$ for store all those entries.

So now, we first spend $\mathcal{O}(M\,lg\,M)$ to process all queries ($\mathcal{O}(M)$ insertions of $\mathcal{O}(lg\, M)$. Then we traverse in-order looking for the maximum using the previous idea in $\mathcal{O}(M)$.

$$ v'[j] = t2q[j] + v'[i] \, \text{iff} \, (index, 0) \, \forall i < index < j $$

Finally, this new approach takes $\mathcal{O}(M\,lg\,M)$-time ($\mathcal{O}(M\,lg\,M)$+$\mathcal{O}(M)$) and $\mathcal{O}(M)$-space. Even better, is (reasonably) independent $N$ (now we can handle $N \approx 2^{64}$).