r****7
发帖数: 2282 | 1 版上看到的面经，我怎么觉得好难啊
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 ? （二维线段树 说算法+分析复杂度） | y****e
发帖数: 25 | 2 Kd-Tree.
【在 r****7 的大作中提到】
: 版上看到的面经，我怎么觉得好难啊
: 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 ? （二维线段树 说算法+分析复杂度）
| T******7
发帖数: 1419 | 3 Mark
★ 发自iPhone App: ChineseWeb 8.7
【在 y****e 的大作中提到】
: Kd-Tree.
| i*********e
发帖数: 21 | 4 2D Binary Index Tree, which is a simpler version of segment tree. | s****a
发帖数: 794 | 5 这个要问面试官 update和query哪个频繁
updata频繁的话 就直接暴力加和。update(O(1)) query(O(N^2))
query频繁 用到左上角的举行加和 update(O(N^2)) query(O(1))
如果差不多 就应该建树吧 | k***7
发帖数: 6 | 6 这个怎么样？
每个点(Xi,Yi)存sumX0~Xi , Yi不变，即每行前面点的sum
Update: O(n) 需要更新所有Xj, j大于i
Query:O(n) 每行的sum=Xj-Xi
【在 r****7 的大作中提到】
: 版上看到的面经，我怎么觉得好难啊
: 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 ? （二维线段树 说算法+分析复杂度）
|
|
