Search code examples
rangebinary-indexed-tree

Range update in Binary Indexed Tree

How can I use Binary Indexed Tree for range update such that each element A[k] in a range say [i..j] is updated to A[k]*c where c is some constant.

And I need to do point queries after such update operations.

I tried with the function below but it wasn't working, here n is size of array,c is the constant I want to multiply each element of range with.

def updateM(x, c, n):
while x <= n:
    BIT[x] *= c
    x += (x & -x)

and these are my calls to update the range:

updateM(i, c, n)
updateM(j+1, -c, n)

Any kind of help would be appreciated. :)

Solution

  • The multiplicative inverse of c is not -c but 1/c. Also, I don't understand, what you're trying to accomplish by x += (x & -x).