用一句话来说线性算法就是：“别再傻傻用双重循环去重复数数了，一招把 O(n^2) 降到 O(n)！”
1. 把它想象成“排队报数与分发糖果”的故事
想象一下，你是一位带队的班主任，面前排了 n 个小朋友，主任经常让你干两件事：
1. “疯狂打听某一段队伍一共有多少人”
2. “疯狂给某一段区间的小朋友发糖果”
没有线性算法（前缀和/差分/双指针）的程序：校长问你 500 次：“从第 3 个到第 100 个小朋友，一共带了多少个苹果？”你每次都得从小明（第3个）一个一个数到小红（第100个），数得头昏眼花。校长又让你操作 500 次：“给第 10 到 50 个小朋友一人发 2 颗糖。”你又得苦哈哈地跑去，给这 40 个人每人手里塞两颗糖。这样来回折腾，人直接累瘫（导致TLE的根本原因）。
开启了线性算法：
前缀和（小本子 
）： 你提前拿个本子，记录下“从第 1 个到当前这个人，一共带了多少苹果”。校长再问你第 3 到第 100 个人有多少苹果时，你根本不用去数，拿第 100 人的总数减去第 2 人的总数，0.0001秒，直接报出答案！
差分（画大饼 
）： 校长让你给第 10 到 50 个人发糖。你懒得一个人一个人发，你直接在第 10 个人背后贴个条子写 +2，在第 51 个人背后贴个条子写 -2。等最后放学时，大家从头往后走，前面人的糖果效果往后累加，到第 51 个人自动把多发的糖扣掉。发糖操作瞬间变成只要对两个人动手，快到飞起！
双指针： 校长让你找一段连续的小朋友，要求他们的苹果总数刚好等于 10。你伸出左右两只手（左右指针）掐住一段队伍。如果苹果不够，右手往后挪（扩张边界）；如果苹果多了，右手别动，左手往后缩（收缩边界）。两只手都只往前走，绝不回头。一趟走完，所有满足条件的队伍全被你揪出来了！
2. 线性区间算法的优缺点喵
这三驾马车合称线性表的“降维打击”神器，它们也有自己的脾气：
优点： 它们的运行速度极快！能把最容易写超时的双重循环 O(n^2) 强行削成 O(n) 线性复杂度。写起来也特别简单直观。你“只要”多开一两个一维数组，或者多设两个 L 和 R 变量，就能直接在考场上拿下满分。
缺点： 前缀和与差分都需要额外开辟跟原数组一样大的空间，属于典型的空间换时间。另外，双指针滑动窗口有一个硬性大前提——数据必须具有单调性（例如区间和不能有负数干扰），一旦没有单调性，双指针就会当场失效喵。
3. 那它们 C++ 代码长什么样？怎么运行
这三个算法的核心骨架代码非常纯粹，记住它们的黄金法则，上场直接套用：
A. 前缀和骨架（怎么运行：预处理求和， O(1) 查表）
long long a[100010], sum[100010];
// 运行逻辑：
// 1. 进门先记账：严格从 1 开始读入，顺便把前面的总和累加到 sum[i] 里
for (int i = 1; i <= n; i++) {
cin >> a[i];
sum[i] = sum[i - 1] + a[i];
}
// 2. 出门直接查：不管查询多少次区间 [L, R] 的和，直接用后减前，秒杀！
while (m--) {
int L, R;
cin >> L >> R;
cout << sum[R] - sum[L - 1] << "\n";
}
B. 差分骨架（怎么运行：两头标记，最后一次性前缀和还原）
long long diff[100010];
// 运行逻辑：
// 1. 修改极快：给 [L, R] 区间全部加上 k，不用循环，直接改头尾两个点
while (m--) {
int L, R; long long k;
cin >> L >> R >> k;
diff[L] += k;
diff[R + 1] -= k; // 别忘了在 R + 1 的位置把效果消掉
}
// 2. 最后一并算账：用前缀和把差分数组还原回最终的答案
long long current_val = 0;
for (int i = 1; i <= n; i++) {
current_val += diff[i]; // 累加差分效果
cout << current_val << (i == n ? "" : " ");
}
C. 双指针滑动窗口骨架（怎么运行：右指针疯狂冲，状态不对左指针疯狂缩）
long long a[100010];
// 运行逻辑：
long long sum = 0; int ans = 0;
// le 是左手，ri 是右手，两只手配合在队伍里滑动
for (int le = 1, ri = 1; ri <= n; ri++) {
sum += a[ri]; // 右手往右走，把新同学的苹果加进来
// 如果苹果总数超过了目标 m，右手停下，左手疯狂往右缩，直到不超为止
while (sum > m && le <= ri) {
sum -= a[le]; // 减去左手丢掉的同学的苹果
le++; // 左手往右移
}
// 此时窗口正好符合条件，记账！
if (sum == m) {
ans++;
}
}
cout << ans << "\n";