一、什么是前缀和？#

1.1 一维前缀和#

一个一维数组X，和它的前缀和数组Y。
那么满足：
- Y[0] = X[0]
- Y[1] = X[0] + X[1]
- Y[2] = X[0] + X[1] + X[2]
- ...
- Y[n] = X[0] + X[1] + ... + X[n]

1.2 二维前缀和#

一个二维数组A，和他的前缀和数组B
那么满足：
- B[0,0] = A[0,0]
- B[0,1] = A[0,0] + A[0,1]
- B[1,0] = A[0,0] + A[1,0]
- B[1,1] = A[0,0] + A[0,1] + A[1,0] + A[1,1]
- ...
- 简单描述就是一片矩形区域内的和

二、计算前缀和#

2.1 一维前缀和#

1
let nums: [Int] = [...]
2
// 前缀和数组
3
var pSum: [Int] = Array(repeating: 0, count: nums.count)
4

5
for i in 0..<nums.count {
6
    if i == 0 {
7
        pSum[0] = nums[0]
8
    }
9
    else {
10
        pSum[i] = pSum[i - 1] + nums[i]
11
    }
12
}

2.2 二维前缀和#

二维前缀和其实就是一个矩阵内值的和，而矩阵又可以由两个列数或行数少一的子矩阵组合后，去除重复的部分，然后再加上右下角的值来构成。
即
- B[x,y] = B[x-1,y] + B[x,y-1] - B[x-1, y-1] + A[x,y]

1
let nums: [[Int]] = [...]
2
var pSum: [[Int]] = Array(repeating: Array(repeating: 0, count: nums.first?.count ?? 0),
3
                            count: nums.count)
4

5
for y in 0..<nums.count {
6
    for x in 0..<nums[y].count {
7
        if x == 0 && y == 0 {
8
            pSum[0][0] = nums[0][0]
9
        }
10
        else if x == 0 {
11
            pSum[0][y] = pSum[0][y-1] + nums[x][y]
12
        }
13
        else if y == 0 {
14
            pSum[x][0] = pSum[x-1][0] + nums[x][y]
15
        }
16
        else {
17
            pSum[x][y] = pSum[x-1][y] + pSum[x][y-1] - pSum[x-1][y-1] + nums[x][y]
18
        }
19
    }
20
}

三、前缀和的应用#

前缀和是一种预处理，用来降低数据查询的时间复杂度。
例如：
- 一个n长度的数组，进行m次查询，每次随机长度，输出每次的和
上面的例子如果暴力解的话，每次都要重头开始到指定下标进行遍历
如果使用前缀和，进行了预处理之后，可以直接查出结果
- 假设l r 为给定的区间，计算区间内的和
- result = x[r] - x[l-1]
- 时间复杂度为O(n+m)