算法技巧：前缀和一维与二维应用解析

前言

在算法设计与优化中，前缀和是一种简单却强大的技巧，能够将复杂问题转化为高效计算。无论是处理一维数组的区间求和，还是解决二维矩阵的子矩阵问题，前缀和都能通过预处理将时间复杂度从线性降低到常数级别，彻底改变问题的解决方式。 从经典的最大子段和问题到实际应用中的'激光炸弹'场景，前缀和不仅展现了数学的优雅，更体现了算法思维的灵活性。本文将深入探讨一维和二维前缀和的原理与应用，揭示其如何通过'预谋'式的预处理，在竞赛与工程中成为改变游戏规则的关键。

前缀和

前缀和与差分的核心思想是预处理，可以在暴力枚举的过程中，快速给出查询的结果，从而优化时间复杂度。 这是经典的用空间替换时间的做法。 前缀和： 快速求出数组中某一段区间和，时间复杂度为 O(1)。

1.1 一维前缀和

1.1.1 前缀和

算法原理：

1. 暴力模拟实现，从指定的下标进行循环，时间复杂度为 O(n * q) 会超时。
2. 前缀和： a. 先预处理出来一个前缀和数组。f[i] 表示：区间 [1, i] 中所有元素和。则 f[i] = f[i - 1] + a[i]。 b. 查询 [l, r] 区间和，则 f[r] - f[l - 1]。

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
int n, q;
LL a[N];
LL f[N]; // 前缀和数组

int main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    // 处理前缀和
    for (int i = 1; i <= n; i++) {
        f[i] = f[i - 1] + a[i];
    }
    // 处理 q 次询问
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << f[r] - f[l - 1] << endl;
    }
    return 0;
}