heyyolol's blog

2D range add update, and range sum queries data structures.
By heyyolol, history, 5 years 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

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

2-D Fenwick:

→ Reply
  • »
    »
    5 years 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?

    → Reply
    • »
      »
      »
      5 years 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

      → Reply
  • »
    »
    5 years 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.

    → Reply