Alex_Miller's blog

By Alex_Miller, 4 months ago, In English

Hi everyone, I'm currently studying BIT on Cp-Algorithms and got confused on the range updates and range queries part. So basically I saw them using a method that's relatively easy to understand to solve range updates and point queries, but suddenly change to another more confusing method to calculate range updates and range queries.

Their code for range updates and point queries

but later on they change to use ...

Another one

so my question is pretty obvious : If I can calculate point queries ( the point_query function from range updates and point queries method) for both the l-1 and r point, why bother changing the method ?

I'm well aware that this question occurred mean I've not fully understand BIT yet. Please answer my question if you can. Thank you for your time !!!

Link to the original code in case you want more details : link

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

4 months ago, # |
  Vote: I like it +20 Vote: I do not like it

Dunno why all the downvoting, the person even added comments to the code excerpts to remove ambiguous details for us.

Alex_Miller I didn't read into the details of how their 2-BIT approach works, so perhaps I'm not understanding the full extent of your question — but could you describe in detail how you plan to use the "point-query, range-update" approach to solve "range-query, range-update"? Getting the value at point R and subtracting the value at point L-1 does not give you sum(L..R), it just gives you a meaningless subtraction of two elements.

  • »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Uh thank you for reply. After reading your comment a while, I realized must have misunderstood to math behind i & (-i). I originally thought the point queries is for calculating sum from 1 to a certain point idx. Thank you for questioning the absurdity of my question. Wish you a good day !!