Please help~What if the index of the two-D array is infinite


  • 0
    O

    This question is actually an interview question I had last week with Google.

    However, the interviewer told me to assume that the index of the two-D array is infinite, so you can't use a two-D vector to store all the information.

    And you are asked to implement two api:

    update(x, y, v) : set the value in position (x, y) to v

    sum(x1, y1, x2, y2): return the sum of value between rectangle from (x1, y1) to (x2, y2)

    Can anyone provide any thoughts?


  • 0
    D

    In 1D, we can use binary index tree (BIT). Maybe we can try to extend it to 2D?


  • 0

    You're getting a little ahead :)

    If the 2d array is finite, you may use a Segment Tree. But since it is infinite, I think a data structure called Binary Indexed Tree may be more appropriate. Topcoder has a nice tutorial here.

    But seriously, not everyone knows these fancy data structures that is mostly used in competitive programming.


  • 0

    Yeah, the topcoder link I posted has a section about 2D BIT.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.