洛谷题单指南-前缀和差分与离散化-P8218 【深进1.例1】求区间和

原题链接：https://www.luogu.com.cn/problem/P8218

题意解读：对于数组a[N]，给定m个区间l~r，求每个区间所有元素之和。

解题思路：

先思考暴力做法：

对于每一个区间[l, r]，累加a[l] ~ a[r]所有元素，时间复杂度最坏为10^5 * 10^4，不可行。

一维前缀和：

设s[N]是a[N]的前缀和数组，即对于每一个s[i]，都表示s[i] = a[1] + .... + a[i]

递推式：s[i] = s[i - 1] + a[i]

对于区间[l, r]和，即a[l] + a[l + 1] + ... + a[r]

根据s的定义，有

s[r] = a[1] + ... + a[l - 1] + a[l] + ... + a[r]

s[l - 1] = a[1] + ... + a[l - 1]

因此s[r] - s[l - 1]即可得[l, r]的区间和

100分代码：

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

const int N = 100005;
int a[N], s[N];

int main()
{
    int n, m;
    cin >> n;
    for(int i = 1; i <= n; i++) 
    {
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }
    cin >> m;
    int l, r;
    for(int i = 1; i <= m; i++)
    {
        cin >> l >> r;
        cout << s[r] - s[l - 1] << endl;
    }
    return 0;
}