https://leetcode.com/problems/range-sum-query-2d-immutable/
条件说sumRegion 会调很多次，如果每次都用双for 循环去累加的话就有太多重复计算了，所以可以实现cache 一下。
可以有两种cache 机制，一种是在初始化的时候就生成cache 这样初始化时间比较长应该是O(n*m) 但是sumRegion 方法就方便和高效多了，大概是O(1)
另一种是动态更新cache，随着sumRegion 的调用慢慢建立cache，这样处理起来会比较麻烦，但是初始化时间就可以忽略不计了，在sumRegion 的多次调用中慢慢的速度越来越快。
我才用第一种方式，初始化时候建立cache，cache 同样是n*m 的矩阵，每个元素是当前行的累加和。
调用sumRegion 的时候把每行的指定列范围内的和加起来就行了，而每行的和就用两个边际列的cache 值只差加上左边际列的原始值就行了，即：
rowSum = cache[endCol] - cache[starCol] + origin[starCol]
/** * @constructor * @param {number[][]} matrix */ var NumMatrix = function(matrix) { if (matrix.length === 0) return; this.cache = []; this.matrix = matrix; this.row = matrix.length; this.col = matrix[0].length; for (var i = 0; i < this.row; i++) { var acc = 0; this.cache.push([]); for (var j = 0; j < this.col; j++) { acc += matrix[i][j]; this.cache[i].push(acc); } } // console.log(this.cache); }; /** * @param {number} row1 * @param {number} col1 * @param {number} row2 * @param {number} col2 * @return {number} */ NumMatrix.prototype.sumRegion = function(row1, col1, row2, col2) { var sum = 0; if (!this.matrix) return 0; for (var i = row1; i <= row2; i++) { sum += this.cache[i][col2] - this.cache[i][col1] + this.matrix[i][col1]; } return sum; };
Range Sum Query 2D - Immutable
原文：http://www.cnblogs.com/agentgamer/p/6237366.html