### 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 **10 ^{10}** 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

**10**. So, here is the optimised approach.

^{7}**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

**10**, which is enough to pass within

^{7}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