SkyMagic's blog

2d range update & range queries with compressed memory?
By SkyMagic, history, 5 hours ago, In English

Here's a question, is it possible to implement a data structures that supports these operations online:

  • 2d Range update(only the add operation, no negative number for adding)
  • 2d Range queries(get the sum)
  • use Low memory(possibly $$$O(nlogn)$$$)

Here are the constraints:

  • $$$n \leq 10^5$$$
  • $$$q \leq 10^5$$$

I think a fenwick tree could work but I'm not sure if it will TLE or not.

If anyone could verify that using a fenwick tree could work please let me know. Thanks in advance!

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 hours ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

You can check out this source. O(N log N) memory is possible, but only with offline updates.

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

    It has to be online updates, there are things I forgot to mention, there are $$$q$$$ queries which have 2 types:

    • 2d Range update(only the add operation, no negative number for adding)
    • 2d Range queries(get the sum)
    → Reply
    • »
      »
      »
      3 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Still doable in $$$O(q)$$$ memory.

      → Reply
»
4 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Yes, it is possible. You can do it even in $$$O(q)$$$ memory btw.

→ Reply