Given a 2D space of maximum size NxN which supports two operations:
  [1] void UPDATE(x,y,v) - sets the value of cell [x,y] to v
  [2] int QUERY(x1,y1,x2,y2) - returns sub-rectangle sum (x1,y1) to (x2,
y2) inclusive, and there is an infinite stream of such 2 types of
operations which have to supported. How would you store the values for
efficient updates and retrievals? 

如果只考虑[1], 二维数组就可以. 

如果只考虑[2], 以下解法简单直接(by ParanoidPark):

先建一个NxN的pre-sum数组，然后这个数组的(i,j)元素存的是从(0, 0)到(i, j)的subarray的和，这样每次query任意sub-array的和，只用取出对应这个pre-sum数组的四个顶点的值, 然后计算A+D-B-C就行了,这样query就是O(1). 如图:

A-----B
|     |
|     |
C-----D

但是如果考虑[1], 效率就低了, 因为要更新所有相关矩形. 

原文作者说二维线段树似乎可以解. 不知道具体如何.

解法似乎可以用树状数组(Binary Indexed Trees).

-- 

来自: http://www.mitbbs.com/article_t1/JobHunting/32574909_0_2.html