前缀和

前缀和实现

在处理数组区间求和时，可以使用前缀和技术来提高效率。本文将介绍如何使用C++实现前缀和。

代码实现

以下是一个实现前缀和的完整C++代码示例：

#include <bits/stdc++.h>

using namespace std;

#define N 100010

long long f[N];
int n, m, t, x, y;

int main() {
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &t);
        f[i] = f[i - 1] + t;
    }   

    while(m--) {
        scanf("%d %d", &x, &y);
        printf("%lld", f[y] - f[x - 1]);
    }
    return 0;
}

示例输入输出

以下是一些示例输入和对应的输出，帮助理解代码的工作原理。

示例 1

输入：

5 3
1 2 3 4 5
1 3
2 4
1 5

输出：

6
9
15

示例 2

输入：

6 2
1 1 1 1 1 1
1 6
3 5

输出：

6
3

示例 3

输入：

4 1
10 20 30 40
2 3

输出：

50

代码说明

输入处理：

• 使用 scanf 函数读取数组长度 n 和查询次数 m。
• 读取数组元素，并计算前缀和存储在数组 f 中。

前缀和实现：

• 通过累加前缀和数组 f，使 f[i] 表示前 i 个元素的和。
• 对于每个查询，计算并输出区间和 f[y] - f[x - 1]。

主函数逻辑：

• 读取输入数据并计算前缀和数组。
• 处理每个查询，输出对应的区间和。