heyyolol's blog

By heyyolol, history, 3 weeks ago, In English,

Hi everyone, does (2D range add update, and range sum queries) fenwick and segment tree exist?

If there is could someone kindly provide me ur code? Thanks :)

I tried googling but I didn't find anything really useful. :( Edit: Like by range I mean for e.g. (a,b) to (c,d), for a<=c && b<=d.

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

»
3 weeks ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

2-D Fenwick:

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    i = (i & (i + 1)) - 1 and i = (i | (i + 1))? Why not i -= i & -i and i += i & -i?

    • »
      »
      »
      3 weeks ago, # ^ |
      Rev. 3   Vote: I like it +5 Vote: I do not like it

      i = (i & (i + 1)) - 1 and i = (i | (i + 1)) for 0-indexation; i -= i & -i and i += i & -i for 1-indexation

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    hmm the inc part looks like point update to me? R u sure that's range update?? Like by range I mean for e.g. (a,b) to (c,d), for a<=c && b<=d.