Update it problem doubt in vedio

#1

sir we know in BIT update is done after (I&-I) index(signifying change in cum_sum due to addition in singlle element in array) but in ques we have to upadte each element from left to right of an array so for that dont we need to call update function for(left-right) times ,to signify change in cumsum due to addition in all elements from left to right,moreover why we update(r+1,-val)

#2

i to want to ask if we do updtae(r+1,-val)

#3

i to want to ask if we do updtae(r+1,-val) then by doing it we nullify the effect of addition that we had did for elements from (l,r) from cumsum of BIT ie BIT’s cumsum because of addition in elements now will we wrong as we have not propagated the addition value in elements to the end of array

#4

Hi @Tanna , I’ll try my best to explain this to you.
So we have u updates of the form add val to all elements in the range l to r.
We know in a BIT : SUM_QUERY(X) = SUM(X) = ar[1] + ar[2] + … + ar[X].
Now what we are going to do is that we will store our indiviual elements in SUM(i) instead of ar[i].
So SUM[3] will represent the 3rd element and likewise for all other elements.
Initially all elements of the array are 0 and so are all SUM(i).
Consider,
we have the query RANGE_UPDATE(L, R, V).
Let us say I do a point update UPDATE(L, V).
After this SUM(X) (for X >= L) will be SUM(X) = S’ + V if S’ was the sum before this query, since ar[L] is now ar[L] + V.
Effectively with that point update at L we have added V to all the SUM(X) wherever X is greater than L.
Since we do not wish to add V to the elements where X > R as our range is L to R, so we do a -V update at R + 1.
Since after the 1st update SUM(X) had changed to SUM(X) + V, after the 2nd update SUM(X) + V changes back to SUM(X) for all X > R.

I hope you find this helpful.

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.