# 01.前缀和

## 一、什么是前缀和？

### 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 一维前缀和

```swift
let nums: [Int] = [...]
// 前缀和数组
var pSum: [Int] = Array(repeating: 0, count: nums.count)

for i in 0..<nums.count {
    if i == 0 {
        pSum[0] = nums[0]
    }
    else {
        pSum[i] = pSum[i - 1] + nums[i]
    }
}
```

### 2.2 二维前缀和

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

```swift
let nums: [[Int]] = [...]
var pSum: [[Int]] = Array(repeating: Array(repeating: 0, count: nums.first?.count ?? 0),
                            count: nums.count)

for y in 0..<nums.count {
    for x in 0..<nums[y].count {
        if x == 0 && y == 0 {
            pSum[0][0] = nums[0][0]
        }
        else if x == 0 {
            pSum[0][y] = pSum[0][y-1] + nums[x][y]
        }
        else if y == 0 {
            pSum[x][0] = pSum[x-1][0] + nums[x][y]
        }
        else {
            pSum[x][y] = pSum[x-1][y] + pSum[x][y-1] - pSum[x-1][y-1] + nums[x][y]
        }
    }
}
```

## 三、前缀和的应用

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

## 参考

> [前缀和技巧](https://zhuanlan.zhihu.com/p/107778275)
>
> [【朝夕的ACM笔记】算法基础-前缀和](https://zhuanlan.zhihu.com/p/117569086)