PROBLEM LINK:Author: Rohit Anand
DIFFICULTY:EASYMEDIUM PREREQUISITES:BIT/SEGMENT TREE,BINARY SEARCH PROBLEM:You have been provided with an array of numbers.Two types of query are there. In first query, you have to update a particular index of array with a given number. In second query, a prefix sum S is given.You have to check, whether this prefix sum exists in array or not, and hence if exists, print the last index of prefix sum. QUICK EXPLANATION:Construct a Segment Tree or BIT(Binary Indexed Tree) from the given array, where internal nodes represents range sum.Use Point updates for query 1, and for query 2,using Binary search on rangequery sums, where starting range is 1 to n, check if the prefix sum exists or not. EXPLANATION:Given array has n elements and we have to perform two kinds of operations.Lets start from worst complexity solutions. Naive Approach
prefix[1]=ar[1];
Before updation, let prev=ar[p]
OPTIMISED APPROACH
void update(int x, int val) {
long long query(int x) {
So, Overall Time complexity for m queries will be O(m(logn)^{2}).Clearly, we can see that we have reduced number of operations to less than 10^{7}, which is enough to pass within given time constraints(1 sec). For better understanding of BIT concepts, you can refer BIT.Also you can use Segment tree for above operations. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here
asked 13 Nov '16, 17:48

I was searching for Segtree question for practice and really found this one as interesting to solve. Even great explanation!Thank you :) answered 08 Dec '16, 03:11

@rohit_0801 this is surely a nice problem, however I don't think I (and probably others) want to see this editorial at the top of the forum every few days when other unanswered questions get pushed down the list. So I'll be glad if you stop making minor and rather insignificant edits every 12 days to garner views and upvotes. Cheers! answered 29 Nov '16, 18:28
@meooow may be he is trying to earn "popular question badge" :)
(29 Nov '16, 19:16)
@meooow thanks!i have to do some insignificant edits because CP is not popular in my college and when some student from my college asks for solution, i have to refer him/her to Editorial.But, if editorial is not found on first page of discussion, i am very sure they will not go for deeper search.
(29 Nov '16, 22:14)
2
@rohit_0801 If this is the only reason, then instead of editing every single time you can share the link to your editorial with them.
(29 Nov '16, 22:18)
