【模版】前缀和

问题引入：

【洛谷P8218】

## 题目描述

给定 $n$ 个正整数组成的数列 $a_1, a_2, \cdots, a_n$ 和 $m$ 个区间 $[l_i,r_i]$，分别求这 $m$ 个区间的区间和。

对于所有测试数据，$n,m\le10^5,a_i\le 10^4$

最朴素的想法，就是对于每次询问，我们都用for循环进行 $[l_i,r_i]$区间的求和，不难看出时间复杂度为O（n*m）。

而如果我们利用前缀和，便可以把时间复杂度优化成O（m+n）。

所以前缀和是一种预处理，用于降低查询时的时间复杂度。

（一维）前缀和的定义：

设si为数列a从第一个数到第i个数的和，当i>=1时，显然有s[i]=s[i-1]+a[i]，这里s[i]数组记录的数值称为前缀和。

若要求出$[l_i,r_i]$区间的和，只需要求s[r]-s[l-1]，单次时间复杂度为O（1）

本题AC代码如下：

#include<iostream>
using namespace std;
#define MAXN 100010;
int n,m;
int a[MAXN],s[MAXN];

int main() {
    cin >> n;
    for (int i=1;i<=n;i++) {
        cin >> a[i];   //若要使用前缀和，数组最好从下标1开始
        s[i]=s[i-1]+a[i];
    }
    cin >> m;
    for (int i=1,l,r;i<=m;i++) {
        cin >> l >> r;
        cout << s[r]-s[l-1];
    }
    return 0
}

二维前缀和待补，累了