レム・咲く夜

LemuSakuya的个人博客网站堂堂登场

这一天终于来到了！！经过长期的策划以及愚蠢的大创项目策划书的拖延，我终于部署好了我的个人博客，真的很感谢Mizuki，用这么好的模版让我舒爽一整天！！！

標籤

レム・咲く夜

LemuSakuya的个人博客网站堂堂登场

这一天终于来到了！！经过长期的策划以及愚蠢的大创项目策划书的拖延，我终于部署好了我的个人博客，真的很感谢Mizuki，用这么好的模版让我舒爽一整天！！！

標籤

レム・咲く夜

LemuSakuya的个人博客网站堂堂登场

这一天终于来到了！！经过长期的策划以及愚蠢的大创项目策划书的拖延，我终于部署好了我的个人博客，真的很感谢Mizuki，用这么好的模版让我舒爽一整天！！！

標籤

🌸 咲夜の秘密メロディ

分類

站點統計

文章

79

分類

16

標籤

24

總字數

394,971

運行天數

0 天

最後活動

0 天前

12477 字

32 分鐘

枚举前缀和差分双指针

2026-06-03

Algorithm

Study Notes

/

Algorithm

第 4 章枚举、前缀和、差分与双指针#

本章目标：学习如何把朴素枚举优化成可通过的数据规模，掌握线性扫描中的常见加速技巧。

4.1 学习目标#

理解枚举的维度和复杂度来源。
掌握一维、二维前缀和。
掌握一维、二维差分。
掌握双指针和滑动窗口。
能判断一个窗口问题是否具有单调性。

4.2 枚举不是坏事#

很多算法从枚举开始。关键是枚举什么。

例如三数之和朴素枚举：

O(n^3)

排序后固定一个数，再用双指针找另外两个数：

O(n^2)

优化的本质是减少枚举维度，或让每个维度移动次数变少。

4.3 前缀和#

一维前缀和定义：

s_0=0, \quad s_i = \sum_{k=1}^{i} a_k

区间 $[l,r]$ 的和：

\sum_{i=l}^{r} a_i = s_r - s_{l-1}

使用 0-index 时常写成：

s_{i+1}=s_i+a_i

区间 $[l,r)$ 的和：

s_r-s_l

4.3.1 为什么建议左闭右开#

左闭右开 $[l,r)$ 有三个好处：

长度等于 $r-l$ 。
空区间可表示为 $l=r$ 。
和数组切片习惯一致。

4.4 二维前缀和#

对矩阵 $a$ ，定义：

S(x,y)=\sum_{i=1}^{x}\sum_{j=1}^{y}a(i,j)

递推：

S(x,y)=S(x-1,y)+S(x,y-1)-S(x-1,y-1)+a(x,y)

矩形 $(x_1,y_1)$ 到 $(x_2,y_2)$ 的和：

S(x_2,y_2)-S(x_1-1,y_2)-S(x_2,y_1-1)+S(x_1-1,y_1-1)

关键是减掉多加的左上角。

4.5 差分#

如果前缀和适合“多次查询区间和”，差分适合“多次区间修改”。

一维差分：

d_1=a_1, \quad d_i=a_i-a_{i-1}

对区间 $[l,r]$ 加 x：

d_l \leftarrow d_l + x

d_{r+1} \leftarrow d_{r+1} - x

最后做一次前缀和还原数组。

4.6 二维差分#

对矩形 $(x_1,y_1)$ 到 $(x_2,y_2)$ 加 v：

d[x_1][y_1] += v

d[x_2+1][y_1] -= v

d[x_1][y_2+1] -= v

d[x_2+1][y_2+1] += v

最后做二维前缀和还原。

4.7 双指针#

双指针通常分为两类：

相向双指针：左右往中间走。
同向双指针：维护一个窗口。

4.7.1 相向双指针#

有序数组两数和：

1
int l = 0, r = n - 1;
2
while (l < r) {
3
    int sum = a[l] + a[r];
4
    if (sum == target) return true;
5
    if (sum < target) l++;
6
    else r--;
7
}

正确性来自有序性：sum 小时只能增大左端，sum 大时只能减小右端。

4.7.2 滑动窗口#

当右端增加使条件单调变坏，左端增加使条件单调变好，就可以滑窗。

例：最短子数组和至少为 target。

1
int l = 0;
2
long long sum = 0;
3
for (int r = 0; r < n; r++) {
4
    sum += a[r];
5
    while (sum >= target) {
6
        ans = min(ans, r - l + 1);
7
        sum -= a[l++];
8
    }
9
}

如果数组有负数，上述单调性不成立，需要换思路。

4.8 离散化#

当坐标很大但点数很少，可以离散化。

流程：

收集所有会用到的坐标。
排序去重。
用下标代替原坐标。

离散化保留的是相对顺序，不保留原始距离。若题目需要区间长度，还要保留相邻坐标差。

4.9 易错点#

前缀和数组长度少开 1。
混用闭区间和左闭右开。
二维前缀和忘记减左上角。
差分忘记处理 r+1 越界。
有负数时错误使用滑动窗口。
离散化后忘记处理重复坐标。

4.10 练习#

用前缀和回答多次区间和查询。
用二维前缀和求矩形区域和。
用差分处理多次区间加法。
用双指针解决三数之和。
判断一个窗口问题是否能使用滑动窗口，并说明原因。

ACM/OI 扩展：扫描线、莫队与离线技巧#

本节补充 OIer 和 ACMer 常用的算法套路、模板、复杂度分析和易错点。写模板时默认使用 C++17，变量名尽量短，但注释要说明不变量和适用条件。

1. 二维差分模板#

矩形加法、多次操作后统一求值。

1
void add(int x1, int y1, int x2, int y2, int v) {
2
    d[x1][y1] += v;
3
    d[x2 + 1][y1] -= v;
4
    d[x1][y2 + 1] -= v;
5
    d[x2 + 1][y2 + 1] += v;
6
}
7
for (int i = 1; i <= n; ++i)
8
    for (int j = 1; j <= m; ++j)
9
        a[i][j] = d[i][j] + a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];

要点：

数组需要多开一圈。
适合离线多次矩形修改。

2. 扫描线处理区间事件#

把区间转化为两个事件，按坐标排序扫描。

1
struct Event { int x, type, id; };
2
vector<Event> ev;
3
// [l, r] 加入事件：l 处 +1，r+1 处 -1
4
sort(ev.begin(), ev.end(), [](auto& a, auto& b){ return a.x < b.x; });
5
long long cur = 0;
6
for (auto e : ev) {
7
    cur += e.type;
8
}

要点：

适合区间覆盖、会议室数量、差分思想推广。
二维矩形面积并需要线段树维护 y 方向覆盖长度。

3. 莫队算法#

静态区间询问可离线排序，使左右指针移动总成本约为 $O((n+q)\sqrt n)$ 。

1
int B;
2
struct Query { int l, r, id; };
3
sort(qs.begin(), qs.end(), [](const Query& a, const Query& b) {
4
    int A = a.l / B, C = b.l / B;
5
    if (A != C) return A < C;
6
    return (A & 1) ? a.r > b.r : a.r < b.r;
7
});
8
int L = 1, R = 0;
9
for (auto qu : qs) {
10
    while (L > qu.l) add(--L);
11
    while (R < qu.r) add(++R);
12
    while (L < qu.l) del(L++);
13
    while (R > qu.r) del(R--);
14
    ans[qu.id] = cur;
15
}

要点：

适合 add/del 都容易维护的区间统计。
块大小通常取 $\sqrt n$ 。

常见坑：

带修改莫队更复杂，需要第三维时间。
如果 add/del 不可逆，不适合莫队。

4. 尺取法与单调队列 DP#

双指针解决窗口可行性，单调队列还能优化 DP。

dp[i]=\min_{j<i,\ condition(j,i)}(dp[j]+cost(j,i))

要点：

当候选 j 的合法范围随 i 单调移动时，可以用队列维护。
当转移值可比较且过期条件明确时，可用单调队列。

5. 前缀和 + 哈希#

区间和等于 k 可转化为两个前缀和差值。

1
unordered_map<long long, int> cnt;
2
cnt[0] = 1;
3
long long s = 0, ans = 0;
4
for (int x : a) {
5
    s += x;
6
    ans += cnt[s - k];
7
    cnt[s]++;
8
}

要点：

可处理负数，因为不是滑动窗口。
统计方案数时先查再加当前前缀。

训练题型：

统计和为 k 的子数组数量。
统计异或为 k 的子数组数量。

本章模板背诵清单#

能在 5 分钟内写出本章第一个核心模板。
能说出每个模板的时间复杂度和空间复杂度。
能说明模板不适用的反例。
能为模板构造 3 个边界样例。
能把模板改成 0-index 或 1-index 版本。

离线与根号分治#

根号分治思想#

当一个参数有大小之分时，按阈值 B 分成小规模暴力、大规模预处理。

出现频率大于 B 的元素最多 n/B 个。
小步长暴力，大步长预处理。
常见于询问按模数、步长、出现次数分类。

分块基础#

把数组分成大小约 $\sqrt n$ 的块，块内暴力，整块维护信息。

B \approx \sqrt n

\text{query}=O(\sqrt n)

适合不容易写线段树的区间问题。
修改局部重构整块。
莫队也是根号思想的一种应用。

二维扫描线面积并#

矩形面积并：扫描 x 方向事件，用线段树维护 y 方向覆盖长度。

每个矩形产生左边 +1、右边 -1 两个事件。
相邻事件 x 差乘当前 y 覆盖长度。
y 坐标需要离散化。

前缀最值优化枚举#

很多二重枚举可把内层最优值转为前缀最大/最小。

ans_i=\max_{j<i}(A_j+B_i)=B_i+\max_{j<i}A_j

当转移中 j 和 i 可拆开时优先尝试。
这是 DP 优化和贪心优化的常见入口。

离线查询按右端点排序#

区间询问经常按右端点排序，边扫描边更新数据结构。

区间不同数个数。
最近相同位置贡献。
树状数组维护每个值最后出现位置。

高频模板训练卡#

这一组训练卡用于把“04_枚举_前缀和_差分_双指针”转化为赛场识别能力。每张卡都包含题目信号、模板选择、复杂度、反例和实现检查。

卡 1：一维前缀和#

题目信号：区间统计、批量修改或连续窗口中出现一维前缀和信号。
优先模板：优先尝试一维前缀和。
核心不变量：扫描过程中已处理部分的信息能完整回答当前问题。
复杂度目标：目标 O(n)、O(n log n) 或 O((n+q)sqrt n)。
不适用场景：窗口不单调、修改在线强制、信息无法撤销时不适用。
实现检查：检查区间开闭、数组多开一位、离散化后是否保留长度。
边界样例：空区间、单点区间、全覆盖、负数、重复坐标。
训练题型：用一维前缀和解决一道区间题并写出为什么不会漏算。

卡 2：二维前缀和#

题目信号：区间统计、批量修改或连续窗口中出现二维前缀和信号。
优先模板：优先尝试二维前缀和。
核心不变量：扫描过程中已处理部分的信息能完整回答当前问题。
复杂度目标：目标 O(n)、O(n log n) 或 O((n+q)sqrt n)。
不适用场景：窗口不单调、修改在线强制、信息无法撤销时不适用。
实现检查：检查区间开闭、数组多开一位、离散化后是否保留长度。
边界样例：空区间、单点区间、全覆盖、负数、重复坐标。
训练题型：用二维前缀和解决一道区间题并写出为什么不会漏算。

卡 3：一维差分#

题目信号：区间统计、批量修改或连续窗口中出现一维差分信号。
优先模板：优先尝试一维差分。
核心不变量：扫描过程中已处理部分的信息能完整回答当前问题。
复杂度目标：目标 O(n)、O(n log n) 或 O((n+q)sqrt n)。
不适用场景：窗口不单调、修改在线强制、信息无法撤销时不适用。
实现检查：检查区间开闭、数组多开一位、离散化后是否保留长度。
边界样例：空区间、单点区间、全覆盖、负数、重复坐标。
训练题型：用一维差分解决一道区间题并写出为什么不会漏算。

卡 4：二维差分#

题目信号：区间统计、批量修改或连续窗口中出现二维差分信号。
优先模板：优先尝试二维差分。
核心不变量：扫描过程中已处理部分的信息能完整回答当前问题。
复杂度目标：目标 O(n)、O(n log n) 或 O((n+q)sqrt n)。
不适用场景：窗口不单调、修改在线强制、信息无法撤销时不适用。
实现检查：检查区间开闭、数组多开一位、离散化后是否保留长度。
边界样例：空区间、单点区间、全覆盖、负数、重复坐标。
训练题型：用二维差分解决一道区间题并写出为什么不会漏算。

卡 5：前缀异或#

题目信号：区间统计、批量修改或连续窗口中出现前缀异或信号。
优先模板：优先尝试前缀异或。
核心不变量：扫描过程中已处理部分的信息能完整回答当前问题。
复杂度目标：目标 O(n)、O(n log n) 或 O((n+q)sqrt n)。
不适用场景：窗口不单调、修改在线强制、信息无法撤销时不适用。
实现检查：检查区间开闭、数组多开一位、离散化后是否保留长度。
边界样例：空区间、单点区间、全覆盖、负数、重复坐标。
训练题型：用前缀异或解决一道区间题并写出为什么不会漏算。

卡 6：前缀和 + 哈希#

题目信号：区间统计、批量修改或连续窗口中出现前缀和 + 哈希信号。
优先模板：优先尝试前缀和 + 哈希。
核心不变量：扫描过程中已处理部分的信息能完整回答当前问题。
复杂度目标：目标 O(n)、O(n log n) 或 O((n+q)sqrt n)。
不适用场景：窗口不单调、修改在线强制、信息无法撤销时不适用。
实现检查：检查区间开闭、数组多开一位、离散化后是否保留长度。
边界样例：空区间、单点区间、全覆盖、负数、重复坐标。
训练题型：用前缀和 + 哈希解决一道区间题并写出为什么不会漏算。

卡 7：滑动窗口#

题目信号：区间统计、批量修改或连续窗口中出现滑动窗口信号。
优先模板：优先尝试滑动窗口。
核心不变量：扫描过程中已处理部分的信息能完整回答当前问题。
复杂度目标：目标 O(n)、O(n log n) 或 O((n+q)sqrt n)。
不适用场景：窗口不单调、修改在线强制、信息无法撤销时不适用。
实现检查：检查区间开闭、数组多开一位、离散化后是否保留长度。
边界样例：空区间、单点区间、全覆盖、负数、重复坐标。
训练题型：用滑动窗口解决一道区间题并写出为什么不会漏算。

卡 8：相向双指针#

题目信号：区间统计、批量修改或连续窗口中出现相向双指针信号。
优先模板：优先尝试相向双指针。
核心不变量：扫描过程中已处理部分的信息能完整回答当前问题。
复杂度目标：目标 O(n)、O(n log n) 或 O((n+q)sqrt n)。
不适用场景：窗口不单调、修改在线强制、信息无法撤销时不适用。
实现检查：检查区间开闭、数组多开一位、离散化后是否保留长度。
边界样例：空区间、单点区间、全覆盖、负数、重复坐标。
训练题型：用相向双指针解决一道区间题并写出为什么不会漏算。

卡 9：三指针#

题目信号：区间统计、批量修改或连续窗口中出现三指针信号。
优先模板：优先尝试三指针。
核心不变量：扫描过程中已处理部分的信息能完整回答当前问题。
复杂度目标：目标 O(n)、O(n log n) 或 O((n+q)sqrt n)。
不适用场景：窗口不单调、修改在线强制、信息无法撤销时不适用。
实现检查：检查区间开闭、数组多开一位、离散化后是否保留长度。
边界样例：空区间、单点区间、全覆盖、负数、重复坐标。
训练题型：用三指针解决一道区间题并写出为什么不会漏算。

卡 10：离散化#

题目信号：区间统计、批量修改或连续窗口中出现离散化信号。
优先模板：优先尝试离散化。
核心不变量：扫描过程中已处理部分的信息能完整回答当前问题。
复杂度目标：目标 O(n)、O(n log n) 或 O((n+q)sqrt n)。
不适用场景：窗口不单调、修改在线强制、信息无法撤销时不适用。
实现检查：检查区间开闭、数组多开一位、离散化后是否保留长度。
边界样例：空区间、单点区间、全覆盖、负数、重复坐标。
训练题型：用离散化解决一道区间题并写出为什么不会漏算。

卡 11：扫描线#

题目信号：区间统计、批量修改或连续窗口中出现扫描线信号。
优先模板：优先尝试扫描线。
核心不变量：扫描过程中已处理部分的信息能完整回答当前问题。
复杂度目标：目标 O(n)、O(n log n) 或 O((n+q)sqrt n)。
不适用场景：窗口不单调、修改在线强制、信息无法撤销时不适用。
实现检查：检查区间开闭、数组多开一位、离散化后是否保留长度。
边界样例：空区间、单点区间、全覆盖、负数、重复坐标。
训练题型：用扫描线解决一道区间题并写出为什么不会漏算。

卡 12：矩形面积并#

题目信号：区间统计、批量修改或连续窗口中出现矩形面积并信号。
优先模板：优先尝试矩形面积并。
核心不变量：扫描过程中已处理部分的信息能完整回答当前问题。
复杂度目标：目标 O(n)、O(n log n) 或 O((n+q)sqrt n)。
不适用场景：窗口不单调、修改在线强制、信息无法撤销时不适用。
实现检查：检查区间开闭、数组多开一位、离散化后是否保留长度。
边界样例：空区间、单点区间、全覆盖、负数、重复坐标。
训练题型：用矩形面积并解决一道区间题并写出为什么不会漏算。

卡 13：莫队#

题目信号：区间统计、批量修改或连续窗口中出现莫队信号。
优先模板：优先尝试莫队。
核心不变量：扫描过程中已处理部分的信息能完整回答当前问题。
复杂度目标：目标 O(n)、O(n log n) 或 O((n+q)sqrt n)。
不适用场景：窗口不单调、修改在线强制、信息无法撤销时不适用。
实现检查：检查区间开闭、数组多开一位、离散化后是否保留长度。
边界样例：空区间、单点区间、全覆盖、负数、重复坐标。
训练题型：用莫队解决一道区间题并写出为什么不会漏算。

卡 14：带修莫队#

题目信号：区间统计、批量修改或连续窗口中出现带修莫队信号。
优先模板：优先尝试带修莫队。
核心不变量：扫描过程中已处理部分的信息能完整回答当前问题。
复杂度目标：目标 O(n)、O(n log n) 或 O((n+q)sqrt n)。
不适用场景：窗口不单调、修改在线强制、信息无法撤销时不适用。
实现检查：检查区间开闭、数组多开一位、离散化后是否保留长度。
边界样例：空区间、单点区间、全覆盖、负数、重复坐标。
训练题型：用带修莫队解决一道区间题并写出为什么不会漏算。

卡 15：分块#

题目信号：区间统计、批量修改或连续窗口中出现分块信号。
优先模板：优先尝试分块。
核心不变量：扫描过程中已处理部分的信息能完整回答当前问题。
复杂度目标：目标 O(n)、O(n log n) 或 O((n+q)sqrt n)。
不适用场景：窗口不单调、修改在线强制、信息无法撤销时不适用。
实现检查：检查区间开闭、数组多开一位、离散化后是否保留长度。
边界样例：空区间、单点区间、全覆盖、负数、重复坐标。
训练题型：用分块解决一道区间题并写出为什么不会漏算。

卡 16：根号分治#

题目信号：区间统计、批量修改或连续窗口中出现根号分治信号。
优先模板：优先尝试根号分治。
核心不变量：扫描过程中已处理部分的信息能完整回答当前问题。
复杂度目标：目标 O(n)、O(n log n) 或 O((n+q)sqrt n)。
不适用场景：窗口不单调、修改在线强制、信息无法撤销时不适用。
实现检查：检查区间开闭、数组多开一位、离散化后是否保留长度。
边界样例：空区间、单点区间、全覆盖、负数、重复坐标。
训练题型：用根号分治解决一道区间题并写出为什么不会漏算。

卡 17：离线按右端点#

题目信号：区间统计、批量修改或连续窗口中出现离线按右端点信号。
优先模板：优先尝试离线按右端点。
核心不变量：扫描过程中已处理部分的信息能完整回答当前问题。
复杂度目标：目标 O(n)、O(n log n) 或 O((n+q)sqrt n)。
不适用场景：窗口不单调、修改在线强制、信息无法撤销时不适用。
实现检查：检查区间开闭、数组多开一位、离散化后是否保留长度。
边界样例：空区间、单点区间、全覆盖、负数、重复坐标。
训练题型：用离线按右端点解决一道区间题并写出为什么不会漏算。

卡 18：贡献法枚举#

题目信号：区间统计、批量修改或连续窗口中出现贡献法枚举信号。
优先模板：优先尝试贡献法枚举。
核心不变量：扫描过程中已处理部分的信息能完整回答当前问题。
复杂度目标：目标 O(n)、O(n log n) 或 O((n+q)sqrt n)。
不适用场景：窗口不单调、修改在线强制、信息无法撤销时不适用。
实现检查：检查区间开闭、数组多开一位、离散化后是否保留长度。
边界样例：空区间、单点区间、全覆盖、负数、重复坐标。
训练题型：用贡献法枚举解决一道区间题并写出为什么不会漏算。

卡 19：子数组计数#

题目信号：区间统计、批量修改或连续窗口中出现子数组计数信号。
优先模板：优先尝试子数组计数。
核心不变量：扫描过程中已处理部分的信息能完整回答当前问题。
复杂度目标：目标 O(n)、O(n log n) 或 O((n+q)sqrt n)。
不适用场景：窗口不单调、修改在线强制、信息无法撤销时不适用。
实现检查：检查区间开闭、数组多开一位、离散化后是否保留长度。
边界样例：空区间、单点区间、全覆盖、负数、重复坐标。
训练题型：用子数组计数解决一道区间题并写出为什么不会漏算。

卡 20：区间众数近似#

题目信号：区间统计、批量修改或连续窗口中出现区间众数近似信号。
优先模板：优先尝试区间众数近似。
核心不变量：扫描过程中已处理部分的信息能完整回答当前问题。
复杂度目标：目标 O(n)、O(n log n) 或 O((n+q)sqrt n)。
不适用场景：窗口不单调、修改在线强制、信息无法撤销时不适用。
实现检查：检查区间开闭、数组多开一位、离散化后是否保留长度。
边界样例：空区间、单点区间、全覆盖、负数、重复坐标。
训练题型：用区间众数近似解决一道区间题并写出为什么不会漏算。

卡 21：小大分类#

题目信号：区间统计、批量修改或连续窗口中出现小大分类信号。
优先模板：优先尝试小大分类。
核心不变量：扫描过程中已处理部分的信息能完整回答当前问题。
复杂度目标：目标 O(n)、O(n log n) 或 O((n+q)sqrt n)。
不适用场景：窗口不单调、修改在线强制、信息无法撤销时不适用。
实现检查：检查区间开闭、数组多开一位、离散化后是否保留长度。
边界样例：空区间、单点区间、全覆盖、负数、重复坐标。
训练题型：用小大分类解决一道区间题并写出为什么不会漏算。

卡 22：bitset 批量枚举#

题目信号：区间统计、批量修改或连续窗口中出现 bitset 批量枚举信号。
优先模板：优先尝试 bitset 批量枚举。
核心不变量：扫描过程中已处理部分的信息能完整回答当前问题。
复杂度目标：目标 O(n)、O(n log n) 或 O((n+q)sqrt n)。
不适用场景：窗口不单调、修改在线强制、信息无法撤销时不适用。
实现检查：检查区间开闭、数组多开一位、离散化后是否保留长度。
边界样例：空区间、单点区间、全覆盖、负数、重复坐标。
训练题型：用 bitset 批量枚举解决一道区间题并写出为什么不会漏算。

本章赛前默写任务#

04_枚举_前缀和_差分_双指针：详细训练清单#

本清单用于把章节知识拆成可执行的小任务，偏 OI/ACM 赛场使用。

训练点 1：暴力枚举降维#

识别信号：题面出现与“暴力枚举降维”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“暴力枚举降维”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 2：贡献法#

识别信号：题面出现与“贡献法”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“贡献法”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 3：一维前缀和#

识别信号：题面出现与“一维前缀和”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“一维前缀和”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 4：二维前缀和#

识别信号：题面出现与“二维前缀和”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“二维前缀和”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 5：前缀异或#

识别信号：题面出现与“前缀异或”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“前缀异或”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 6：前缀哈希计数#

识别信号：题面出现与“前缀哈希计数”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“前缀哈希计数”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 7：一维差分#

识别信号：题面出现与“一维差分”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“一维差分”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 8：二维差分#

识别信号：题面出现与“二维差分”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“二维差分”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 9：相向双指针#

识别信号：题面出现与“相向双指针”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“相向双指针”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 10：滑动窗口#

识别信号：题面出现与“滑动窗口”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“滑动窗口”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 11：离散化#

识别信号：题面出现与“离散化”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“离散化”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 12：扫描线#

识别信号：题面出现与“扫描线”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“扫描线”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 13：莫队#

识别信号：题面出现与“莫队”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“莫队”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 14：分块#

识别信号：题面出现与“分块”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“分块”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 15：根号分治#

识别信号：题面出现与“根号分治”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“根号分治”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 16：离线查询#

识别信号：题面出现与“离线查询”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“离线查询”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 17：暴力枚举降维#

识别信号：题面出现与“暴力枚举降维”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“暴力枚举降维”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 18：贡献法#

识别信号：题面出现与“贡献法”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“贡献法”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 19：一维前缀和#

识别信号：题面出现与“一维前缀和”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“一维前缀和”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 20：二维前缀和#

识别信号：题面出现与“二维前缀和”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“二维前缀和”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 21：前缀异或#

识别信号：题面出现与“前缀异或”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“前缀异或”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

如果這篇文章對你有幫助，歡迎分享給更多人！

枚举前缀和差分双指针

https://lemusakuya.com/posts/study-notes/algorithm/04_枚举_前缀和_差分_双指针/

作者

レム・咲く夜

發布於

2026-06-03

許可協議

部分資訊可能已經過時

相關文章智能推薦

Algorithm 《算法》学习笔记：01_算法学习总览与复杂度分析

2

基础数据结构与语言工具

Algorithm 《算法》学习笔记：02_基础数据结构与语言工具

3

递归分治二分

Algorithm 《算法》学习笔记：03_递归_分治_二分

4

排序贪心构造

Algorithm 《算法》学习笔记：05_排序_贪心_构造

5

栈队列堆哈希

Algorithm 《算法》学习笔记：06_栈_队列_堆_哈希

隨機文章隨機推薦

1

Chapt3

Digital Image Processing 2026-06-03

2

神经网络学习总览与路线

Neural Networks 2026-06-03

Neural Networks 2026-06-03

ぬくぬくうちにゃ💤

第 4 章 枚举、前缀和、差分与双指针#

4.1 学习目标#

4.2 枚举不是坏事#

4.3 前缀和#

4.3.1 为什么建议左闭右开#

4.4 二维前缀和#

4.5 差分#

4.6 二维差分#

4.7 双指针#

4.7.1 相向双指针#

4.7.2 滑动窗口#

4.8 离散化#

4.9 易错点#

4.10 练习#

ACM/OI 扩展：扫描线、莫队与离线技巧#

1. 二维差分模板#

2. 扫描线处理区间事件#

3. 莫队算法#

4. 尺取法与单调队列 DP#

5. 前缀和 + 哈希#

本章模板背诵清单#

离线与根号分治#

根号分治思想#

分块基础#

二维扫描线面积并#

前缀最值优化枚举#

离线查询按右端点排序#

高频模板训练卡#

卡 1：一维前缀和#

卡 2：二维前缀和#

卡 3：一维差分#

卡 4：二维差分#

卡 5：前缀异或#

卡 6：前缀和 + 哈希#

卡 7：滑动窗口#

卡 8：相向双指针#

卡 9：三指针#

卡 10：离散化#

卡 11：扫描线#

卡 12：矩形面积并#

卡 13：莫队#

卡 14：带修莫队#

卡 15：分块#

卡 16：根号分治#

卡 17：离线按右端点#

卡 18：贡献法枚举#

卡 19：子数组计数#

卡 20：区间众数近似#

卡 21：小大分类#

卡 22：bitset 批量枚举#

本章赛前默写任务#

04_枚举_前缀和_差分_双指针：详细训练清单#

训练点 1：暴力枚举降维#

训练点 2：贡献法#

训练点 3：一维前缀和#

训练点 4：二维前缀和#

训练点 5：前缀异或#

训练点 6：前缀哈希计数#

训练点 7：一维差分#

训练点 8：二维差分#

训练点 9：相向双指针#

训练点 10：滑动窗口#

训练点 11：离散化#

训练点 12：扫描线#

训练点 13：莫队#

训练点 14：分块#

训练点 15：根号分治#

训练点 16：离线查询#

训练点 17：暴力枚举降维#

训练点 18：贡献法#

训练点 19：一维前缀和#

训练点 20：二维前缀和#

训练点 21：前缀异或#

目錄

第 4 章枚举、前缀和、差分与双指针#