PROBLEM LINK:Author: Aniket Marlapalle DIFFICULTY:easy PREREQUISITES:binary indexed trees, binary search PROBLEM:You have an array of n numbers. You need to perform q queries of following type:
EXPLANATION:
Bruteforce : For every query of the first type just update the value in the array. For every second query iterate from the end of the array to see if the suffix sum is equal to some given value. Now we can see that the suffix sums if ordered from right to left follow the nondecreasing order. So we can use binary search to speed up the calculations. Do a binary search on the length of the suffix and check the sum of the suffix corresponding to this length, if it is greater that the required sum then check on lower lengths else continue the search on higher lengths. Time Complexity : $O(N*log(N) + Q*log(N)*log(N))$ AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here
This question is marked "community wiki".
asked 09 Nov '16, 22:36
