算法刷题笔记 前缀和（C++实现）

文章目录

• • 题目描述
  • 基本思路
  • 实现代码

题目描述

• 输入一个长度为n的整数序列。
• 接下来再输入m个询问，每个询问输入一对l,r。
• 对于每个询问，输出原序列中从第l个数到第r个数的和。

输入格式

• 第一行包含两个整数n和m。
• 第二行包含n个整数，表示整数数列。
• 接下来m行，每行包含两个整数l和 r，表示一个询问的区间范围。

输出格式

• 共m行，每行输出一个询问的结果。

数据范围

• 1 ≤ l ≤ r ≤ n
• 1 ≤ n,m ≤ 100000
• −1000 ≤ 数列中元素的值 ≤ 1000

基本思路

本题有两种思路：

• 第一种：首先存储用户输入的数组，然后每次根据用户输入的区间，将指定区间内所有的数值相加。但是，这种思路需要每一次处理都要进行多次加法运算，有些浪费时间。
• 第二种：直接使用一个数组存储到目前位置为止的数组前缀和。例如，对于数组 1 2 3，对应的前缀和数组为 1 3 6（因为 3 = 1 + 2，6 = 1 + 2 + 3），这样，计算某个区间内元素的累加值，只需要将前缀和数组中的两个元素相减即可。具体来说，当区间的右端点是right，左端点是left时，只需要计算数组中下标为right元素减去下标为left-1的元素的值即可。这种思路明显更加节约时间。

实现代码

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

int main(void)
{
    int n, m;
    scanf("%d %d", &n, &m);
    vector<int> sum;
    sum.push_back(0);
    int x;
    for(int i(1); i <= n; ++i) 
    {
        scanf("%d", &x);
        sum.push_back(sum[i - 1] + x);
    }
    
    int pos1, pos2;
    for(int i(0); i < m; ++i)
    {
        scanf("%d %d", &pos1, &pos2);
        printf("%d\n", sum[pos2] - sum[pos1 - 1]);
    }
    return 0;
}