PROBLEM LINK:
Author: Rohit Anand
Tester: Ankit Raj Gupta
Editorialist: Rohit Anand
DIFFICULTY:
EASY-MEDIUM
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 range-query 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
For the given array, first we will store the prefix sum in another array as,
prefix[1]=ar[1];
for(int i=2;i<=n;i++)
prefix[i]=ar[i]+prefix[i-1];
Here, for query 1, we can update the array in constant time ie we can directly do ar[p]=q.But, now we can see that after updating an index of array, the prefix array will also get modified.
So, we also we have to modify prefix array as,
Before updation, let prev=ar[p]
After updation,
ar[p]=q,diff=q-prev;
for(int i=p;i<=n;i++)
prefix[i]+=diff;
Now, for query 2, the given sum to be found is S. We can perform a linear search on prefix array to check if S exists or not.
bool found=false;
for(int i=1;i<=n;i++)
if(prefix[i]==S)
found=true,pos=i;
To further optimise, we can use Binary Search on prefix array also.
After doing all these operations, when you submit your code, it shows Time Limit Exceeded. So sad 
Now, have a look at Constraints section.Isn’t the values of m and n are too high to pass
in 1 sec with the above approach ? Answer is Yes! Time complexity of above code is O(m$*$n) ie you are performing approx 1010 operations, which never executes in 1 sec. In order to get it pass within 1 sec,
we have to reduce number of operations to approx 107. So, here is the optimised approach.
OPTIMISED APPROACH
For the given array, first we will construct the Segment tree or BIT(Fenwick tree).Here, the internal nodes will store the sum of leaf nodes as well as other internal nodes ie merging of nodes will be on
the basis of summation of its two children nodes.
For, first query we will perform point updates using BIT as,
//Point update in BIT-------
void update(int x, int val) {
while (x <= n) {
bit[x] += val;
x += x & -x;
}
}
Time Complexity of update is O(logn).
For query 2,we can query the given sum S by defining our range using Binary Search as follows:
Pseudo Code:
l=1;
r=n;
int mid;
bool flag=0;
//Binary Search-----
while(l<=r)
{
mid=l+(r-l)/2;
ans=query(mid);
if(ans>S)
r=mid-1;
else if(ans< S)
l=mid+1;
else
{
pos=mid;
flag=1;
break;
}
}
//Range-Sum query ------
long long query(int x) {
long long sum = 0;
while (x) {
sum += bit[x];
x -= x & -x;
}
return sum;
}
Time complexity of query is O((logn)2). logn for query and logn for Binary search.Because of monotonic nature of function,we can easily use Binary Search here.
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 107, 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
Tester’s solution can be found here
