题解 | 【模板】静态区间和（前缀和）

#include <iostream>
#include <vector>
using namespace std;

// 构建前缀和并处理查询的模板
int main() {
    int n, q;  // n：数组长度，q：查询次数
    cin >> n >> q;

    // 1. 读入原始数组（0-based）
    vector<long long> nums(n);  // 用long long避免大数溢出
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }

    // 2. 构建前缀和数组（prefix[0] = 0，prefix[i] = sum(nums[0..i-1])）
    vector<long long> prefix(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        prefix[i] = prefix[i - 1] + nums[i - 1];  // 累加前i-1个元素
    }

    // 3. 处理每个查询（查询[l, r]为1-based）
    while (q--) {
        int l, r;
        cin >> l >> r;
        // 区间和 = prefix[r] - prefix[l-1]
        cout << prefix[r] - prefix[l - 1] << endl;
    }

    return 0;
}

经典：

✅ 一维前缀和模板（Prefix Sum - 1D）

💡 适用场景：快速求任意区间 [l, r] 的和

🔹 模板代码：

// 输入：长度为 n 的数组 a[0..n-1]
vector<int> a(n); 
for (int i = 0; i < n; ++i) cin >> a[i];

// 构建前缀和数组 s[0..n]
// s[i] 表示前 i 个数的和（不包含第 i 个）
vector<long long> s(n + 1, 0);
for (int i = 1; i <= n; ++i) {
    s[i] = s[i - 1] + a[i - 1];
}

// 查询区间 [l, r]（下标从 0 开始）
int l, r; // 输入：0 <= l <= r < n
long long sum = s[r + 1] - s[l]; // 区间和

✅ 二维前缀和模板（2D Prefix Sum）

💡 适用场景：求一个二维矩形区域内所有元素的和

🔹 模板代码：

// 输入：矩阵 a[n][m]
vector<vector<int>> a(n, vector<int>(m));
for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j)
        cin >> a[i][j];

// 构建二维前缀和 s[n+1][m+1]
vector<vector<long long>> s(n + 1, vector<long long>(m + 1, 0));

// 注意：s[i][j] 表示从 a[0][0] 到 a[i-1][j-1] 的区域和
for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
        s[i][j] = s[i - 1][j] + s[i][j - 1]
                  - s[i - 1][j - 1] + a[i - 1][j - 1];
    }
}

🔹 查询某一子矩阵 [x1, y1] 到 [x2, y2]（0-based，包含端点）：

// 因为前缀和数组是从 1 开始，所以 +1
long long sum = s[x2 + 1][y2 + 1]
              - s[x1][y2 + 1]
              - s[x2 + 1][y1]
              + s[x1][y1];