前缀和与差分 复习笔记

核心思想：预处理优化查询，将多次重复的区间操作从 O(n) 降至 O(1)，是数组类题目最常用的基础技巧。

---

一、一维前缀和

1. 核心作用

快速计算数组任意区间的元素总和，替代每次遍历求和。

• 预处理时间：O(n)
• 单次查询时间：O(1)

2. 基础定义

约定数组下标从 1 开始（简化边界处理，s[0] = 0 天然处理左边界）

• 原数组：a[1], a[2], ..., a[n]
• 前缀和数组 s[i]：原数组前 i 项的累加和，即 a[1] + a[2] + ... + a[i]

3. 核心公式

• 递推构造（预处理）： s[i] = s[i-1] + a[i]
• 区间和查询（计算 [L, R] 的总和）： sum(L,R) = s[R] - s[L-1]

4. 代码模板

// 数组大小根据题目数据范围开，这里以n≤1000为例
int a[1005];   // 原数组，下标从1开始
int s[1005] = {0}; // 前缀和数组，全局/初始化默认为0

// 1. 预处理前缀和
for(int i = 1; i <= n; i++){
    s[i] = s[i-1] + a[i];
}
// 2. 查询区间[L, R]的和
int res = s[R] - s[L-1];

---

二、前缀最值（前缀最大值/最小值）

1. 核心作用

前缀和的拓展用法，快速查询前 i 项的最大/最小值，常用于单侧最值类问题。

2. 基础定义

• ma[i]：原数组前 i 项的最大值
• mi[i]：原数组前 i 项的最小值

3. 核心公式

ma[i] = max(ma[i-1], a[i]);
mi[i] = min(mi[i-1], a[i]);

4. 典型应用

• 寻找每个位置左侧的最大/最小值
• 结合后缀最值，解决“接雨水”“股票最佳买卖时机”等经典问题

---

三、二维前缀和（字符计数专项）

1. 核心作用

快速统计字符串任意区间内，每个小写字母的出现次数，本质是26组并行的一维前缀和。

2. 数组定义

s[i][j]：字符串前 i 个位置中，第 j 个字母的出现总次数

• j = 0 对应字母 a，j = 1 对应 b，……，j = 25 对应 z

3. 核心公式

• 递推构造：先继承上一行的所有计数，再给当前字母计数+1
• 区间查询（[L, R] 内字母 j 的出现次数）： cnt[j] = s[R][j] - s[L-1][j]

4. 代码模板

string str = "abcawdojawwjawoidajwiowdjoawjodiawjoidawojidoawji";
str = "@" + str;  // 下标从1开始，前面补占位符
int n = str.size() - 1;

// 第一维是字符串长度，第二维固定26个字母
int s[1005][26] = {0}; 

// 1. 预处理
for(int i = 1; i <= n; i++){
    // 继承前i-1个位置的所有字母计数
    for(int j = 0; j < 26; j++){
        s[i][j] = s[i-1][j];
    }
    // 当前字母计数+1
    int c = str[i] - 'a';
    s[i][c]++;
}

// 2. 查询[L,R]区间各字母出现次数
int cnt[26];
for(int j = 0; j < 26; j++){
    cnt[j] = s[R][j] - s[L-1][j];
}

---

四、一维差分

1. 核心概念

差分与前缀和是互逆运算，专门解决批量区间加减问题。

• 单次区间修改：O(1)
• 最终还原数组：O(n)

2. 差分四步走

第1步：构造差分数组

设原数组为 a[1..n]，差分数组为 c[1..n+1]（多开空间防止越界） 定义式：c[i] = a[i] - a[i-1]（默认 a[0] = 0）

理解：差分数组记录原数组相邻两项的“变化量”

第2步：执行区间修改

需求：将原数组 [L, R] 区间内所有元素统一加上 k。 操作：c[L] += k; c[R+1] -= k;

原理：对差分数组求前缀和时，L 及之后都会加上 k，R+1 及之后会抵消 k，最终只影响 [L,R] 区间。

第3步：还原原数组

对差分数组做前缀和，得到修改后的原数组： a[i] = a[i-1] + c[i]（本质就是求前缀和）

第4步：统计答案

根据题目要求，对最终数组求和、求最值、输出结果等。

3. 完整代码模板

int a[1005];    // 原数组，下标1~n
int c[1005] = {0}; // 差分数组，空间开足，防止R+1越界

// 1. 构造差分数组
for(int i = 1; i <= n; i++){
    c[i] = a[i] - a[i-1];
}

// 2. 执行m次区间[L,R]加k操作
while(m--){
    int L, R, k;
    cin >> L >> R >> k;
    c[L] += k;
    c[R+1] -= k;
}

// 3. 前缀和还原为修改后的原数组
for(int i = 1; i <= n; i++){
    a[i] = a[i-1] + c[i];
}

// 4. 统计答案（示例：求最终数组最大值）
int ans = 0;
for(int i = 1; i <= n; i++){
    ans = max(ans, a[i]);
}

---

五、核心对比总结

技巧	核心能力	时间复杂度	关键公式
一维前缀和	O(1) 计算区间和	预处理O(n)，查询O(1)	s[R] - s[L-1]
前缀最值	O(1) 查询前i项最值		ma[i] = max(ma[i-1], a[i])
字符前缀和	O(1) 查询区间字母频次	预处理O(n×26)，查询O(26)	s[R][j] - s[L-1][j]
一维差分	O(1) 完成区间批量加减	修改O(1)，还原O(n)	c[L]+=k, c[R+1]-=k

易错提醒

1. 所有技巧优先使用下标从1开始的数组，避免边界越界
2. 数组大小要根据题目数据范围开够，通常比最大值多开5~10个位置
3. 差分数组一定要多开空间，防止 R+1 访问越界
4. 前缀和适合静态数组多次查询，频繁区间修改优先用差分