Range Update in BIT

#1

I cannot able to get if we want to add 2 between range l to r. Then, how adding 2 to l
in BIT result in cummulative sum from l to n?

#2

So you are asking how BIT works? Because this is a basic operation when it comes binary indexed trees.

#3

I know that updating the index in bit will lead to all updates containing this index further. For example,
if i want to update index 4 in array then i will update bit[4] which stores the information from 1 to 4 and all other indices further which include 4.

#4

But how the addition of a number at index l will lead to addition of all indices from l to n.

#5

Yeah it updates all indices from 4 and greater than 4.

#6

You just said you know how bit works, so n>l, so if you update BIT[l] it would also update BIT[n] as n>=l

#7

Okay I think I found what part you found confusing.
We are not exactly adding elements, we are just summing up the updates at that point.
So when we query Bit[n] and we find sum as let’s say x, then we know effective update at this point has been x, so when asked to print value at index n, we need to print arr[n] (the original value) + x.
Read the concept about difference array to see how this works

#8

Got it. Thanks for help.

#9

I did not get range update and range queries. Pls help

#10

What part did you not understand now?

#11

What is the use of second bit ?

#12

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.