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.