CODEWITHSUNDEEP
rangebinary-indexed-tree
Chandan Mittal
Chandan Mittal

Reputation: 75

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. :)

Upvotes: 1

Views: 361

Answers (2)

user3249319
user3249319

Reputation: 11

It's simple. You just have to run a loop.

But this method is over kill.

It would be best to use segment tree and update the appropriate range, not just a single value.

Upvotes: 0

Kai
Kai

Reputation: 110

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).

Upvotes: 1

Related Questions