BAADSHAH - EDITORIAL (IEMCO16)

PROBLEM LINK:

Practice

Contest

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*=ar*+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*+=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*==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](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/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

5 Likes

thanks for the explanation !

1 Like

@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 1-2 days to garner views and upvotes. Cheers!

1 Like

I was searching for Seg-tree question for practice and really found this one as interesting to solve. Even great explanation!Thank you :slight_smile:

1 Like

@meooow may be he is trying to earn “popular question badge” :slight_smile:

@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.

@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.

1 Like

thanks bro :slight_smile: