# 前缀和问题

### 什么是前缀和？

一维前缀和

假设`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;
```


---

# 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://matthrew.gitbook.io/oliver/qian-zhui-he-wen-ti.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.