# 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)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://ryukiedev.gitbook.io/wiki/shu-ju-jie-gou-yu-suan-fa/ji-qiao/01.-qian-zhui-he.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.