> For the complete documentation index, see [llms.txt](https://matthrew.gitbook.io/oliver/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://matthrew.gitbook.io/oliver/qian-zhui-he-wen-ti.md).

# 前缀和问题

### 什么是前缀和？

一维前缀和

假设`x`为一数组，`y`为数组`x`的前缀和数组，则`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\_2 \ +\ ... \ +\ x\_n
$$

二维前缀和

假设`x`为二维数组，`y`为数组`x`的二维前缀和数组，则`x`和`y`满足如下关系:

$$
y\_{0,0}=x\_{0,0},
y\_{0,1}=x\_{0,0}+a\_{0,1},
y\_{1,0}=x\_{0,0}+x\_{1,0},
y\_{1,1}=x\_{0,0}+x\_{0,1}+x\_{1,0}+x\_{1,1}\dots
$$

![二位前缀和数组示意图](/files/-Mhcb0oZFF503ZRwjf2g)

如上图，右侧二位前缀和数组标红元素 $$y\_{2, 2}$$ 的值等于左侧二维数组标红区域元素之和

### 如何计算

一维前缀和

$$
y\_n=y\_{n-1}+x\_n
$$

代码实现

```
for (let i = 0; i < n; i++) {
    if (i === 0) {
        y[i] = x[i]
    } else {
        y[i] = y[i - 1] + x[i]
    }
}
```

二位前缀和

$$
y\_{i, j}=y\_{i-1,j}+y\_{i,j-1}-y\_{i-1,j-1}+x\_{i,j}
$$

代码实现

```
// n * m
for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
        if (i === 0 && j === 0) {
            y[j][i] = x[j][i]
        } else if (j === 0) {
            y[j][i] = y[j][i - 1] + x[j][i]  // 一维数组前缀和
        } else if (i === 0) {
            y[j][i] = y[j - 1][i] + x[j][i]  // 一维数组前缀和
        } else {
            y[j][i] = y[j - 1][i] + y[j][i - 1] - y[j - 1][i - 1] + x[j][i]
        }
    }
}
```

### 前缀和应用

[参考链接](https://zhuanlan.zhihu.com/p/375675761)

* 连续子数组求和问题

> 给你一个正整数数组 arr ，请你计算所有可能的奇数长度子数组的和

```
let preSum = [arr[0]], res = 0, n = arr.length;
for (let i = 1; i < n; i++) {
    preSum[i] = preSum[i - 1] + arr[i]
}
preSum.unshift(0)
console.log('preSum', preSum)

for (let i = 0; i < n; i++) {
    for (let j = 1; i + j - 1 < n; j += 2) {
        // console.log('ele', arr.slice(i, i + j))
        // i = 0的时候，preSum[0]是人为补上的
        // S(i + j) - S(i)是{x(i), x(i + 1), x(i + 2), ..., x(i + j)的和
        res += preSum[i + j] - preSum[i]  
    }
}
return res;
```