D****6
发帖数: 278 | 1 Given a matrix of integers. How to calculate the sum of a sub-matrix.
A sub-matrix is represented by x, y, h, w, where x and y is the position of
the upper-left corner, h is the height, w is the width.
int[][] matrix
int sum(int x, int y, int h, int w){...}
这个谁都会.
之后问如果这个函数会被调用多次,而且用在同一个matrix上, sub-matrix会与之前的
overlap, 怎么优化.
我就说用DP之类的, 把之前结果存下来, 有overlap那部分就直接用.
可具体我也不知道怎么做.
请高手指点下
多谢! | h**6
发帖数: 4160 | 2 二维二叉索引树 (2D Binary Indexed Tree)，对n*m的矩阵，预处理的时间复杂度为O(nmlognlogm)，此后每次求和效率可以达到O(lognlogm)，与子矩阵大小无关。 | r****o
发帖数: 1950 | 3 我的想法先计算sum0函数，sum0(int h, int w)表示从(0,0)左上角开始，height为h,
width为w的sub-matrix的sum。遍历matrix，将sum0的结果存到一个二维数组sum0[][]
里面。
计算sum0可以用如下方法:
sum0[x][y]=sum0[x-1][y]+sum0[x][y-1]-sum0[x-1][y-1]+A[x][y].
计算sum()用sum0矩阵的值就可以了。
sum(x,y,h,w)=sum0[x+w][h+y]-sum0[x+w][y]-sum0[x][y+h]+sum0[x][y]
不知道有没有更好的方法。
of
【在 D****6 的大作中提到】
: Given a matrix of integers. How to calculate the sum of a sub-matrix.
: A sub-matrix is represented by x, y, h, w, where x and y is the position of
: the upper-left corner, h is the height, w is the width.
: int[][] matrix
: int sum(int x, int y, int h, int w){...}
: 这个谁都会.
: 之后问如果这个函数会被调用多次,而且用在同一个matrix上, sub-matrix会与之前的
: overlap, 怎么优化.
: 我就说用DP之类的, 把之前结果存下来, 有overlap那部分就直接用.
: 可具体我也不知道怎么做.
| h**6
发帖数: 4160 | 4 楼上这个方法更好，单次求和复杂度是O(1)
用2D Binary Indexed Tree的优点是修改数据方便，如果矩阵数据始终固定不变，还是楼上
的方法更胜一筹。 | r****o
发帖数: 1950 | 5 还是你强，我只会些土方法。呵呵。
是楼上
【在 h**6 的大作中提到】
: 楼上这个方法更好，单次求和复杂度是O(1)
: 用2D Binary Indexed Tree的优点是修改数据方便，如果矩阵数据始终固定不变，还是楼上
: 的方法更胜一筹。
| h*h
发帖数: 23 | 6 这个算sum0的算法在sub-matrix 不是正方型的时候就不成立了吧.
【在 r****o 的大作中提到】
: 我的想法先计算sum0函数，sum0(int h, int w)表示从(0,0)左上角开始，height为h,
: width为w的sub-matrix的sum。遍历matrix，将sum0的结果存到一个二维数组sum0[][]
: 里面。
: 计算sum0可以用如下方法:
: sum0[x][y]=sum0[x-1][y]+sum0[x][y-1]-sum0[x-1][y-1]+A[x][y].
: 计算sum()用sum0矩阵的值就可以了。
: sum(x,y,h,w)=sum0[x+w][h+y]-sum0[x+w][y]-sum0[x][y+h]+sum0[x][y]
: 不知道有没有更好的方法。
:
: of
| D****6
发帖数: 278 | 7 也成立吧
【在 h*h 的大作中提到】
: 这个算sum0的算法在sub-matrix 不是正方型的时候就不成立了吧.
| w****m
发帖数: 146 | 8 second this
【在 r****o 的大作中提到】
: 我的想法先计算sum0函数，sum0(int h, int w)表示从(0,0)左上角开始，height为h,
: width为w的sub-matrix的sum。遍历matrix，将sum0的结果存到一个二维数组sum0[][]
: 里面。
: 计算sum0可以用如下方法:
: sum0[x][y]=sum0[x-1][y]+sum0[x][y-1]-sum0[x-1][y-1]+A[x][y].
: 计算sum()用sum0矩阵的值就可以了。
: sum(x,y,h,w)=sum0[x+w][h+y]-sum0[x+w][y]-sum0[x][y+h]+sum0[x][y]
: 不知道有没有更好的方法。
:
: of
| c******n
发帖数: 4965 | 9 查RMQ 找到这个，很有意思
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowest
of
【在 D****6 的大作中提到】
: Given a matrix of integers. How to calculate the sum of a sub-matrix.
: A sub-matrix is represented by x, y, h, w, where x and y is the position of
: the upper-left corner, h is the height, w is the width.
: int[][] matrix
: int sum(int x, int y, int h, int w){...}
: 这个谁都会.
: 之后问如果这个函数会被调用多次,而且用在同一个matrix上, sub-matrix会与之前的
: overlap, 怎么优化.
: 我就说用DP之类的, 把之前结果存下来, 有overlap那部分就直接用.
: 可具体我也不知道怎么做.
|
|
