Https://online.codingblocks.com/player/9269/content/200?s=1278

#1

https://online.codingblocks.com/player/9269/content/200?s=1278

Hi,
I am not able to understand how This BIT calculating the cumulative sum when we are performing range update on it,
for ex: suppose we have a={1, 7, 3, 5, 2, 9} as we know our BIT contains the sum of indexes on every index
BIT={(1, 1),(1, 2), (3, 3), (1, 4), (5,5) …}
if am performing an update of +10 over the rage (3, 5)
so our array will look like something a ={1, 2, 13, 15, 12, 9}
BIT will contain ={1, 8, 13, 26, 2, 11}.
and suppose my query is: 4 mean I am asking cumulative sum till index 4;
Then BIT returns 26 but the cumulative sum should be 36.

Thank you for any effort in advance.

#2

initially :slight_smile:
a={1,7,3,5,2,9}
BIT={(1,1),(1,2),(3,3),(1,4),(5,5),(5,6)}

After adding +10 over range (3,5)
a={1,7,13,15,12,9}
BIT={1,8,13,36,12,21}
So BIT(4) is the required answer.

when u are updating BIT(4) when +10 over (3,5)
BIT[4]= BIT[4]+ 10*(4-3+1)= 16+20=36
Hit like if u get it

#3

could you please explain briefly with an example how the value at each index in BIT is getting calculated in case of range update. still i did’n get your point.

Thanks in Advance!:slight_smile:

#4

Forget whatever written above : just go with basics in next lines
Range update and point query :slight_smile:

NORMAL ARRAY APPROACH
…{0,0,0,0,0} Array

TO UPDATE ARRAY l to r with value v i,e, index 2 to 3 with value 1
we will add 1 at index l i.e. at index 2 and we will subtract 1 at index r+1, i.e. 4
So
array
…{0,0,1,0,-1}
Now to get value at index 3 we are finding the sum of all values upto index 3 i.e. 0+0+1+0=1
so 1 is value at index 3.
Now to get value at index 4 we are finding the sum of all values upto index 4 i.e. 0+0+1+0-1=0
so 0 is value at index 4.
We are doing this thing using BIT.
If u get this and try to implement this approach on
on
Array ={0,0,0,0,0,0,0,0,0,0,0,0}
update range (0,4) by 5
update range (1,7) by 9
update range (0,6) by 5
find value at index 4
find value at index 3
update range (3,8) by 4
find value at index 8.

If u get this then read this article.

#5

Hi Anubhav,
Thank you so much for the effort.
I have the confusion that how the value at each index is getting calculated.
because suppose we have BIT={0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
if i am performing update(1, 4) with +5
then our BIT would become BIT={5, 5, 0, 5, -5, -5, 0, 0, 0, 0}
and our original array ={5, 5, 5, 5, 0, 0, 0, 0, 0, 0}
if am doing range query on (1, 3) then our ans should be 15 but BIT would return 10 only.
I have gone through many articles but everywhere I am getting the same. I had gone through your attached
article This is also doing the same. it will also return same 10 as the ans.

My actual confusion is how the BIT is adding +v at every index in original array of the given range.
if update is (1, 4, +v) : it means our original array is something a={+v, +v, +v, +v, 0, 0, 0, 0, …}

please correct me where i am wrong.:slight_smile:
I appriciate your effort.

Thank you.

#6

there are two type of query:

  1. Range update and point query
    You want to update a range and ask for element at perticular index.
  2. Range update and range query
    You want to update range and ask for answer of perticular range.

You are reading the article of type 1 and implementing on type 2 query.
For Range update and range query, you will need two BIT.
The above mentioned article is for range update and point query.