https://gist.github.com/gcrfelix/ca460f4870c779f855be
让你设计个matrix class，提供两个方法：update(x, y) & query(x1, y1, x2, y2)，
update方法是update matrix上一个cell的值，
query方法是查询matrix上用(x1, y1)和(x2, y2)确定的矩形内所有值的总和。
有三种scenario，
第一种是update方法调用的次数远大于query方法的调用次数，
第二种是query方法的调用次数远大于update方法的调用次数，
第三种是两种方法调用次数一样多。
第一种情况，因为update次数多，那就不⽤用对matrix做任何预处理，这样update是O(1)，query是O(N^2)。
第二种情况，因为query次数多，那就预处理⼀下matrix，新建一个辅助二维数组dp,使得dp[x][y]等于以(0,0)和(x,y)两点确定的矩阵内的值的总和。
这样update是O(N^2), query是O(1) query(x1, y1, x2, y2) = dp[x2][y2] - dp[x1][y2] - dp[x2][y1] + dp[x1][y1]
update: x for [x2, m - 1], y for [y2, n - 1] update
第三种情况，我们可以改变辅助二维数组dp的构成，使得dp[x][y]等于(0,y)到(x,y)的所有值的和，
这样update是O(N)，如果(x1, y1)更新的话
for(int x=x1; x<m; x++) {
if(x != 0) {
dp[x][y1] = dp[x-1][y1] + matrix[x][y1];
}
}
query也是O(N)
int sum = 0;
for(int y=y1; y<=y2; y++) {
sum += dp[x2][y];
sum -= dp[x1][y];
}
改进：Binary Indexed Tree -> Query & Update O(lgn)
