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?