前缀和与记忆化

Quote

1. 前缀和数组（Prefix Sum）

前缀和是一种 预处理数组区间和 的技巧。它的作用是：

快速求任意一段连续区间的总和。

如果没有前缀和，每次求区间和都要循环累加，效率低。

2. 前缀和的核心思想

设原数组：

a = [2, 4, 1, 6, 3]

定义前缀和数组 sum[i]：

sum[i] = 前 i 个数的总和

即：

sum[0] = 0
sum[1] = 2
sum[2] = 6
sum[3] = 7
sum[4] = 13
sum[5] = 16

3. 区间和公式

要求区间 [l, r] 的和（下标从1开始）：

sum[r] - sum[l - 1]

例如求第2到4个数：

4 + 1 + 6 = 11

计算：

sum[4] - sum[1] = 13 - 2 = 11

4. C++ 模板

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;

    int a[1005], sum[1005];

    sum[0] = 0;

    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
    }

    int l, r;
    cin >> l >> r;

    cout << sum[r] - sum[l - 1];
}

5. 常见用途

5.1 多次查询区间和

例如：

查询 1~5
查询 3~8
查询 2~9

前缀和非常快。

5.2 二维前缀和

用于矩阵求子矩形和。

5.3 配合枚举优化

很多 O(n²) 题目会用到。

6. 常见错误

6.1 下标混乱

建议统一从 1 开始存数组。

6.2 忘记初始化

sum[0] = 0;

6.3 区间公式写错

正确：

sum[r] - sum[l - 1]

7. 记忆化搜索（Memoization）

记忆化搜索本质是：

递归 + 保存已经算过的答案，避免重复计算。

适合：

递归问题
状态重复出现
DFS + DP 类型题目

8. 为什么需要记忆化

例如斐波那契：

f(5)
= f(4) + f(3)

而：

f(4) 又会算 f(3)
f(3) 又被重复算很多次

导致大量重复计算。

9. 核心思想

第一次算：

f(6)

得到结果后存起来：

memo[6] = 8

下次再求 f(6)：

直接返回 memo[6]

不用重新递归。

10. 斐波那契模板

#include <iostream>
using namespace std;

long long memo[1005];

long long f(int n)
{
    if(n == 1 || n == 2) return 1;

    if(memo[n]) return memo[n];

    return memo[n] = f(n - 1) + f(n - 2);
}

int main()
{
    int n;
    cin >> n;

    cout << f(n);
}

11. 记忆化搜索常见用途

11.1 斐波那契数列

经典入门题。

11.2 网格走路问题

从 (1,1) 到 (n,m) 有多少走法。

11.3 最长路径问题

DFS 搜索时记录答案。

11.4 状态压缩搜索

高阶题常见。

12. 前缀和 vs 记忆化

技巧	本质	用途
前缀和	预处理累计信息	快速求区间
记忆化	保存递归结果	避免重复计算

13. 如何选择

如果题目是：

连续区间求和

用前缀和。

递归重复状态

用记忆化。

14. 一句话理解

前缀和

提前把前面的和算好，后面直接减。

记忆化

算过一次的结果记下来，下次直接拿。