「算 1 加到 1 亿」——循环一个个加要 1 亿步，高斯公式一步出答案。今天学「同样的事做得更快」：数学公式、前缀和、滚动数组、预处理——四条路把 O(n)、O(n²) 的活压到 O(1)。
去 30 楼：爬楼梯要一级一级走 30 步，坐电梯「叮」一声直达——目的地一样，路径不同，快慢差百倍。算法也一样：答案只有一个，做法可以有很多种，选对路径就是优化。
路径一：数学公式。1+2+…+n 一个个加要 n 步；小时候的高斯把首尾配对：(1+n)、(2+n−1)……每对都是 n+1，一共 n/2 对 → n(n+1)/2，一步算完。n = 10^8 时：循环 1 亿步 ≈ 1 秒，公式 1 步 ≈ 0 秒。
路径二：前缀和——提前造一张「累计总和表」：pre[i] = a[1]+…+a[i]。建表花 n 步；之后任意区间 [l, r] 的和 = pre[r] − pre[l−1]，1 步出答案。查一次不赚，查 10000 次就把 10000 次 O(n) 变成了 10000 次 O(1)——「预处理换查询」。
路径三：空间优化。算斐波那契 f(n) = f(n−1) + f(n−2)，每一步只用前两个值——开 n 格数组是浪费，两个变量滚着算，空间 O(n) → O(1)（七级 C07 的滚动数组）。还有「复用数组」：用完的表接着用，别每件事都开新表；「别开比需要的更大的表」：n 最多 500 就别开 1000 的表。
四条路合起来就是「一般技巧」：减循环层数（O(n²) → O(n) → O(1)）、数学公式（求和、快速幂）、预处理换查询（前缀和、查表）、空间换时间（哈希表 O(1) 查 vs 顺序找 O(n)）。
// ── 手推：1+2+…+100 ── // 循环：s = 0; for i = 1..100: s += i → 100 步 // 公式：(1 + 100) x 100 / 2 = 5050 → 1 步 // 配对的由来（小时候的高斯）： // 1 + 100 = 101 // 2 + 99 = 101 // 3 + 98 = 101 // ... // 50 + 51 = 101 （一共 50 对） // 总和 = 101 x 50 = 5050 // 通用公式：1+2+…+n = n(n+1)/2 // 更一般：a1+a2+…+an（等差）= n(a1+an)/2 // ── 手推：1+2+…+10^8 ── // 循环：10^8 步 ≈ 1 秒（擦边，循环里再干点别的就超时） // 公式：10^8 x (10^8+1) / 2 = 5000050000000000 → 1 步 // 防溢出：10^8 x 10^8 = 10^16，超过 int 上限 2.1x10^9 → long long
// ── 手推：a = 3, 1, 4, 1, 5（5 个数，下标 1..5）── // 第 1 步：建「累计总和表」（n 步） // pre[1] = 3 // pre[2] = 3 + 1 = 4 // pre[3] = 3 + 1 + 4 = 8 // pre[4] = 3 + 1 + 4 + 1 = 9 // pre[5] = 3 + 1 + 4 + 1 + 5 = 14 // 第 2 步：答区间和（每次查询 1 步） // a[2..4] 的和 = pre[4] - pre[1] = 9 - 3 = 6 （1+4+1 ✓） // a[3..5] 的和 = pre[5] - pre[2] = 14 - 4 = 10 （4+1+5 ✓） // a[1..5] 的和 = pre[5] = 14 （整个数组） // 对比：查上面 3 个区间 // 循环逐个加：3 + 3 + 5 = 11 步 // 前缀和： 建表 5 步 + 3 次查询 x 1 步 = 8 步 // 查询越多越赚：查 10000 个区间，前缀和 = 5 + 10000 步， // 循环 = 10000 x 平均长度（几十步）= 几十万方
// ── 手推：斐波那契 f(n) = f(n-1) + f(n-2)，求 f(10) ── // 数组版（开 10 格）：f = 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 // 滚动版（只留 3 个变量，滚着算）： // 起步：a = 1, b = 1 （f1, f2） // i=3: c = a+b = 2 → a, b = b, c （1, 2） // i=4: c = a+b = 3 → （2, 3） // i=5: c = 5 → （3, 5） // i=6: c = 8 → （5, 8） // i=7: c = 13 → （8, 13） // i=8: c = 21 → （13, 21） // i=9: c = 34 → （21, 34） // i=10: c = 55 → 答案 f(10) = 55 // 每一步只用「前两个值」，更早的格子再也不会被用到 → 可以滚掉 // ── 空间账本（1 个 int = 4 B）── // n = 10^6：数组版 10^6 x 4 B = 4 MB；滚动版 3 个 int = 12 B // n = 10^8：数组版 400 MB → 爆（128 MB 限制）；滚动版还是 12 B // ── 另外两条空间纪律 ── // ① 复用数组：用完的表接着干下一件事，别每件事都开新表 // ② 别开比需要的更大的表：n 最多 500，就别开 g[1000][1000]
// ── 四条路速查 ── // ① 减循环层数：O(n^2) → O(n) → O(1) // 循环在「求和/求幂/计数」？→ 找数学公式 // 求和 n(a1+an)/2；幂用快速幂 O(log n)（C05） // ② 预处理换查询：建表一次 O(n)，之后每次查询 O(1) // 前缀和：区间和；查表：n 小时把答案全算好 // ③ 空间换时间：哈希表查询 O(1) vs 顺序找 O(n) // visited 数组：标「到过没」，免重复算（DFS/BFS 都在用） // ④ 省空间：滚动数组 O(n) → O(1)；数组别开大 // ── 决策树 ── // 代码有慢循环？ // ├─ 在反复答同类查询？→ 前缀和 / 查表（路 ②） // ├─ 在逐个查「在不在集合里」？→ 哈希（路 ③） // ├─ 在算和/幂？→ 数学公式（路 ①） // └─ 数组太大？→ 滚动 / 缩小（路 ④）
// 任务：算 1+2+…+n（n = 10^8），循环 / 公式 / 前缀和 三路对照 #include <iostream> using namespace std; int main() { long long n = 100000000LL; // n = 10^8 // ── 方法 1：循环一个个加（O(n) = 10^8 步 ≈ 1 秒）── long long s1 = 0; for (long long i = 1; i <= n; i++) s1 += i; cout << "循环：和 = " << s1 << "（10^8 步）" << endl; // ── 方法 2：等差求和公式（O(1) = 1 步）── long long s2 = n * (n + 1) / 2; cout << "公式：和 = " << s2 << "（1 步）" << endl; cout << "结果一致：" << (s1 == s2 ? "是" : "否") << endl; // 注意：n*(n+1) 到 10^16，超 int 上限（约 2.1x10^9）→ 必须 long long // ── 方法 3：前缀和（建表 O(n)，之后每个区间查询 O(1)）── // n = 10^8 的数组放不进内存，用 5 个数演示方法 int a[6]; a[1] = 3; a[2] = 1; a[3] = 4; a[4] = 1; a[5] = 5; int pre[6] = {0}; for (int i = 1; i <= 5; i++) pre[i] = pre[i - 1] + a[i]; cout << "前缀和表："; for (int i = 1; i <= 5; i++) cout << pre[i] << " "; cout << endl; // 区间 [2, 4] 的和 = pre[4] - pre[1] = 9 - 3 = 6（1 步） cout << "a[2..4] 的和 = " << pre[4] - pre[1] << "（1 步）" << endl; return 0; } // 运行结果： // 循环：和 = 5000050000000000（10^8 步） // 公式：和 = 5000050000000000（1 步） // 结果一致：是 // 前缀和表：3 4 8 9 14 // a[2..4] 的和 = 6（1 步）