Блог пользователя NeverSayNever

Автор NeverSayNever, 10 лет назад, По-английски

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

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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