信息学奥赛课堂笔记：前缀和算法

一、核心概念

• 前缀和数组：对于给定数组a，定义前缀和数组s，其中s[i]表示a的前i项之和（即s[i] = a[1] + a[2] + ... + a[i]）。
• 作用：快速计算数组a中任意区间[L, R]的总和（从第L项到第R项的和）。

二、核心公式

1. 前缀和计算： s[i] = s[i-1] + a[i]（初始值s[0] = 0，便于边界计算）。
2. 区间和计算： 区间[L, R]的总和 = s[R] - s[L-1]。 （原理：前R项和减去前L-1项和，剩余部分即为L到R的和）。

三、代码实现

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

// 变量说明：
// n：原数组长度；a：原数组；s：前缀和数组
// m：查询次数；l,r：查询的区间左右端点
int n, a[1000010], s[1000010], m, l, r;

int main() {
    // 输入数组长度和查询次数
    cin >> n >> m;
    
    // 读入原数组并计算前缀和
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        s[i] = s[i-1] + a[i];  // 应用前缀和公式
    }
    
    // 处理每次查询，输出区间和
    for (int i = 1; i <= m; i++) {
        cin >> l >> r;
        cout << s[r] - s[l-1] << endl;  // 应用区间和公式
    }
    
    return 0;
}

四、优势分析

• 时间效率：
  • 预处理（计算前缀和）：O(n)（只需遍历一次数组）。
  • 每次查询：O(1)（仅一次减法）。
• 对比普通方法（每次查询遍历区间求和，时间O(R-L+1)），前缀和在多次查询场景下效率极大提升。

五、练习

1. 若a = [3, 1, 4, 2]，则前缀和数组s为： s[0] = 0，s[1] = 3，s[2] = 4，s[3] = 8，s[4] = 10。
2. 计算区间[2, 3]的和： s[3] - s[1] = 8 - 3 = 5（验证：1 + 4 = 5）。