rayenhaf's blog

searching for 2D segment tree problems
By rayenhaf, history, 10 years ago, In English

Hi everyone , I am searching for problems that require a 2D segment tree / BIT or quad tree ( if it's possible , i want them in an increasing order of difficulty )... thanks in advance :)

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

Comments Comments (4)
| Write comment?
»
10 years ago, hide # |
← Rev. 4  
Vote: I like it +16 Vote: I do not like it

Here's a cute problem:

Build an online data structure that supports the following operations on a 2D array in :

  1. Increment each element in the rectangle with corners (a, b) and (c, d) by v.
  2. Output the sum of the elements in the rectangle with corners (a, b) and (c, d).

IOI '07 Pairs and IOI '13 Game are two others. And one more from POI XIII. The Ultimate Bamboo Eater is a pretty straightforward implementation.

→ Reply
  • »
    »
    10 years ago, hide # ^ |
     
    Vote: I like it +9 Vote: I do not like it

    thanks a lot ...

    → Reply
  • »
    »
    10 years ago, hide # ^ |
     
    Vote: I like it +4 Vote: I do not like it

    A really nice solution for the first one you gave is using 4x 2D binary index trees. Its actually really similar to range update and range query for 1D array using a BIT/Fenwick tree. Do you know any simpler solution? If you do, can you please share it. Thanks in advance :)

    → Reply
»
10 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

355D

→ Reply