Given a sparse matrix, implement below two methods: void set(int row, int col, int val) //Update value at given row and col; int sum(int row, int col) //Get sum from top left corner to given row, col sub-matrix.
给出一个稀疏矩阵，要求实现两个方法：第一个是更新指定行列的元素值，第二个是给出行列值，求从左上到该坐标的子矩阵的元素值之和。
1. 询问
假如不明白稀疏矩阵是什么意思，应该要问清楚。
2. 分析
常规方法
一个非常自然的想法就是存储[row, col, val]这样的元素。那么空间复杂度上是O(n)。
假如用这种存储方法，set函数就必须遍历所有元素来找到对应的row和col值，复杂度O(n)；而sum函数，也需要遍历所有元素把范围内的挑出来相加，复杂度还是O(n)。
如何改进
在上面这种解法中，瓶颈主要是在查找。可以考虑利用哈希表来降低查找的时间复杂度。
但是，这道题里面行和列两者是并列的，如何映射？
解法1
一种思路是把行和列映射成为一个值，而且不同的行列值这个值必须不同。例如，我们知道mxn的矩阵里面有m*n个元素，因此可以用序号0~m*n-1来唯一确定这些元素，也就是说:
hash(row, col) = row*n + col，同样从hash到row和col: row = hash(row, col)//n, col = hash(row, col)%n。
建立如上映射关系之后，set方法就可以直接查找，时间复杂度降为O(1)；而对于sum方法，还是要遍历所有元素，O(n)。此外，因为使用了哈希表，空间复杂度为O(n)。
解法2
此外，因为有row和col两个查询参数，可以用两层哈希表。第一层是row为key，value则是下一层的哈希表；第二层是col为key，然后给的元素值作为value。也就是{row:{col:val}}。
该方法复杂度和方法1还是一样。
拓展
上面两种方法，set函数都已经达到了理论最优，但是sum函数和最直接的解法相比较也没有任何改进。可不可以提高sum函数的复杂度呢？
其实如果是普通的矩阵，可以用二维的Fenwick Tree来实现，查询复杂度O(logm*logn)，不过代码比较难写，还需要构造时间O(m*n)和更新数据O(logm*logn)，对于稀疏矩阵而言，并不算太合适。
3. 代码
class Solution:
def __init__(self, m, n):
self.m, self.n, self.d = m, n, {}
def set(self, row, col, val):
h = (row - 1) * self.n + col
self.d[h] = val
def sum(self, row, col):
s = 0
for key in self.d.keys():
r, c = key // self.n, key % self.n
if r <= row and c <= col:
s += self.d[key]
return s
4. 总结
难度Easy，主要是考察哈希表的使用。
