引入

给定一个很大的数组 nums = [-1, 22, 89, .... ]，对这个数组的一种操作：求区间 [i, j] 内所有数的和。

朴素的想法当然是遍历区间 [i, j] 求和。

func sumRange(nums []int, i, j int) int {
    sum := 0
    for limit := i; limit <= j; limit++ {
        sum += nums[limit]
    }
    return sum
}

但是当 sumRange 这个函数调用非常频繁的时候，每次都需要花费大量时间遍历求解，不能满足实际需求。
这时引入一个“前缀和”概念。

前缀和：数组某元素以及它之前所有元素的和。 如 nums = [1, 2, 3, 4, 5]，元素 4 的前缀和为 1 + 2 + 3 + 4 = 10

假设数组 nums 的前缀和数组为 sums。
定义式：
递推式：

因此，如果我们根据递推式求出 nums 的前缀和数组 sums，便很容易得到区间 [i, j] 内所有数的和：

由此改写代码：

var sums []int

func perfixSum(nums []int) {
    // 多 1 个空间的妙处
    // sums[2] 即表示第 1,2 个元素的和
    // sums[0] 无意义
    sums = make([]int, len(nums)+1)    
    for i := range nums {
         sums[i+1] = sums[i] + nums[i]  
    }
}

func sumRange(i, j int) int {
    return sums[j+1] - sums[i]
}

这样只需要 O(n) 的时间计算一次前缀和，然后求区间和就是 O(1) 时间。

推广

二维数组的前缀和。
由一维到二维，易知：
定义式：
递推式：

求：给出区域左上角和右下角坐标，求该区域内所有元素的和。
如下图，区域和为：ans = 6 + 7 + 10 + 11 = 34

利用前缀和求解：
如图理解：

例题

原题链接：二维区域和检索
代码实现：

type NumMatrix struct {
    sums [][]int
}


func Constructor(matrix [][]int) NumMatrix {
    var numMatrix NumMatrix
    m := len(matrix)
    if m == 0 { return numMatrix }
    n := len(matrix[0])
    numMatrix.sums = make([][]int, m+1)
    for i := 0; i <= m; i++ {
        numMatrix.sums[i] = make([]int, n+1)
    }

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            numMatrix.sums[i][j] = numMatrix.sums[i-1][j] + numMatrix.sums[i][j-1] - 
                                   numMatrix.sums[i-1][j-1] + matrix[i-1][j-1]
        }
    }

    return numMatrix
}


func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
    return this.sums[row2+1][col2+1] - this.sums[row1][col2+1] - this.sums[row2+1][col1] + 
           this.sums[row1][col1]
}

sums 多一行多一列的妙用：无需进行越界判断，省掉一堆 if else 。