NeverSayNever's blog

Binary Indexed Tree
By NeverSayNever, 9 years ago, In English

Hello Everyone,

I would like to ask something about range update in Binary Indexed Tree. I am familiar with the range update in BIT in log(N).

adding of function F(x) = x*(x+1)/2 or other polynomial function to the range can be easily handled with bit.

But what if we need to replace the old values with the new values in the range like instead of adding x to every number in the range [L,R] we need to replace every number in the range [L,R] by x.

I also know that this can be handled using lazy propagation in segment tree. But i want to know if there exists any approach which make use of BIT.

If somehow we are able to make every element in range[L,R] zero then we can simply add the number x to the range[L,R].

If anyone has some idea or can help me ....

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am also finding such techniques. Can anyone help please ?? @xellos , @enchom any one

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I think replacing numbers can be handled better with map (and there was a similar CF problem), since at most 2 intervals aren't added/deleted at each step.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you please elaborate the idea bit more and provide link to that problem. It will really be helpfull ....

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Think about it, and look for it (if I knew which one it is, I'd have posted the link before).

      → Reply