Subarray Sum Query

思路

对于subarray sum query的问题，我们和subarray sum equals k的问题用到了相同的思路，那就是使用prefix sum。只不过这里我们不需要HashMap来把sum作为key, index作为value。而是反过来，需要把index作为key, sum作为value。而又因为这种问题我们需要存储以每个点为subarray结尾的prefixSum，我们通常直接用和原array/matrix一样的int array/matrix来表示HashMap，而不用真正使用到HashMap。

步骤

• prepreprocess step，计算以每一个点为结尾的prefix sum。
• 根据题目的index，返回所求subarray的sum

题型变种

• Subarray sum query, immutable：这是最基础版的subarray sum query，直接使用prefix 数组然后做减法就可以。
• Subarray sum query, mutable: 没办法这种题我们只能使用树状数据结构，either segment tree or binary indexed tree。
• Submatrix sum query, immutable：在不变的matrix里面，我们只需要考虑使用overlapping rectangle去解决就可以了， 也就是sum = prefix[i][j] - top - left + topLeft
• Submatrix sum query, mutable: 这里头我们就要使用row prefix array，这样update的时间是O(col), query的时间是O(row)

题目

• Leetcode 303. Range Sum Query - Immutable
• Leetcode 304. Range Sum Query 2D - Immutable
• Leetcode 307. Range Sum Query - Mutable
• Leetcode 308. Range Sum Query 2D - Mutable
• Leetcode 396. Rotate Function