前缀和入门（Introduction to Prefix Sums）

核心内容：在固定的一维数组上以常数时间计算区间和查询
编程语言：C++

1. 参考资料（Resources）

参考资料来源	章节/主题	内容说明
IUSACO	11 - 前缀和（Prefix Sums）	本模块内容基于此资料
CPH（《Competitive Programming 3》）	9.1 - 和查询（Sum Queries）	内容较为简洁
PAPS	11.2.1 - 前缀预处理（Prefix Precomputation）	内容同样较为简洁

2. 一维前缀和（1D Prefix Sums）

假设我们有一个1-索引的整数数组arr，长度为N。我们需要计算Q组不同(a,b)对（满足1≤a≤b≤N）对应的区间和：

arr[a] + arr[a+1] + … + arr[b]

示例数组

索引`i`	1	2	3	4	5	6
`arr[i]`	1	6	4	2	5	3

暴力解法的局限

对于每个查询，遍历从a到b的所有元素求和。总时间复杂度为O(NQ)。当N、Q ≤ 10^5时，NQ可达10^10，远超时间限制，无法通过测试。

前缀和数组的定义与构建

定义前缀和数组prefix，因数组为1-索引，设prefix[0] = 0。对于1 ≤ k ≤ N，前缀和数组的定义为：

prefix[k] = sum（从i=1到k）arr[i]

即前缀和数组的第k个元素存储原始数组从索引1到k的所有元素之和。

通过以下递推公式，可在O(N)时间内构建前缀和数组：

prefix[k] = prefix[k-1] + arr[k]

示例前缀和数组

索引`i`	0	1	2	3	4	5	6
`prefix[i]`	0	1	7	11	13	18	21

区间和查询公式

查询1-索引数组中[L, R]（包含边界）的区间和时，可使用公式：

sum（从i=L到R）arr[i] = prefix[R] - prefix[L-1]

该公式的原理是：prefix[R]是从1到R的总和，prefix[L-1]是从1到L-1的总和，两者相减即得到L到R的区间和。

示例查询

查询a=2到b=5的区间和：

原始数组计算：6 + 4 + 2 + 5 = 17
前缀和计算：prefix[5] - prefix[1] = 18 - 1 = 17

时间复杂度优化

预处理前缀和数组：O(N)
单次查询：O(1)
总时间复杂度：O(N+Q)，可满足时间限制。

前缀和也被称为“部分和（partial sums）”。

3. 解决方案 - 静态区间和（Solution - Static Range Sum）

在C++中，可使用std::partial_sum函数构建前缀和数组，但并不会显著简化代码。

#include <bits/stdc++.h>
using namespace std;

#define sz(x) (int)size(x)

using ll = long long;
using vl = vector<ll>;

// 计算前缀和数组
vl psum(const vl &a) {
    vl psum(sz(a) + 1);
    for (int i = 0; i < sz(a); i++) {
        psum[i + 1] = psum[i] + a[i];
    }
    return psum;
}

// 计算区间[L, R]的和（0-索引数组，L和R从0开始，包含边界）
ll range_sum(const vl &prefix, int L, int R) {
    return prefix[R + 1] - prefix[L];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;
    vl a(N);
    for (int i = 0; i < N; i++) {
        cin >> a[i];
    }

    vl prefix = psum(a);

    while (Q--) {
        int L, R;
        cin >> L >> R;
        // 若题目输入为1-索引，需转换为0-索引：L--, R--
        cout << range_sum(prefix, L, R) << '\n';
    }

    return 0;
}

4. 练习题（Problems）

状态（Status）	来源（Source）	题目名称（Problem Name）	难度（Difficulty）	标签（Tags）
-	白银级（Silver）	品种计数（Breed Counting）	极简单（Very Easy）	显示标签（Show Tags）：前缀和（Prefix Sums）
-	白银级（Silver）	和为7的子序列（Subsequences Summing to Sevens）	简单（Easy）	显示标签（Show Tags）：前缀和（Prefix Sums）
-	白银级（Silver）	蹄子、纸张、剪刀（Hoof Paper Scissors）	简单（Easy）	显示标签（Show Tags）：前缀和（Prefix Sums）
-	CSES	子数组和 II（Subarray Sums II）	简单（Easy）	显示标签（Show Tags）：前缀和（Prefix Sums）
-	CSES	子数组可整除性（Subarray Divisibility）	简单（Easy）	显示标签（Show Tags）：前缀和（Prefix Sums）
-	白银级（Silver）	奶牛为什么过马路 II（Why Did the Cow Cross the Road II）	简单（Easy）	显示标签（Show Tags）：前缀和（Prefix Sums）
-	SPOJ	干草捆堆叠（Haybale Stacking）	中等（Normal）	显示标签（Show Tags）：前缀和（Prefix Sums）
-	CF（Codeforces）	好子数组（Good Subarrays）	中等（Normal）	显示标签（Show Tags）：数学（Math）、前缀和（Prefix Sums）
-	AC（AtCoder）	黑板上的最大公约数（GCD on Blackboard）	中等（Normal）	显示标签（Show Tags）：前缀和（Prefix Sums）
-	CF（Codeforces）	奔跑里程（Running Miles）	中等（Normal）	显示标签（Show Tags）：前缀和（Prefix Sums）
-	CF（Codeforces）	不可约回文串（Irreducible Anagrams）	中等（Normal）	显示标签（Show Tags）：前缀和（Prefix Sums）
-	AC（AtCoder）	2019的倍数（Multiple of 2019）	困难（Hard）	显示标签（Show Tags）：前缀和（Prefix Sums）

5. 小测验（Quiz）

计算长度为n的数组的前缀和数组，最优时间复杂度是多少？

1. O(n)

2. O(n²)

3. O(1)

4. O(n log n)

答案解析：构建前缀和数组需遍历数组一次，每个元素的计算仅需O(1)时间，因此最优时间复杂度为O(n)，对应选项1。