前缀和 | Some Notes

开始

前缀和是一种优化算法，用于求区间和。若数据范围特别大，写 for 循环很可能会爆时间复杂度，就可以用上前缀和了。前缀和有一维前缀和和二维前缀和，我暂时还没有学二位前缀和，故在此不多赘述。

使用

一维前缀和需要把一个数组比如数组 $a [1]$ 到 $a [n]$ （ $n$ 为 $a$ 数组长度）储存到另一个数组中比如数组 $b$ 。那么：

b [i] (i \leq n) = j = 1 \sum i a [j]

我们发现：

b [1] = a [1] b [2] = a [1] + a [2] b [3] = a [1] + a [2] + a [3] ... b [i - 1] = a [1] + a [2] + ... + a [i - 1] b [i] = a [1] + a [2] + ... + a [i - 1] + a [i] ∴ b [i] = b [i - 1] + a [i]

这正好是一个递推的过程， $b [1] = a [1], b [2] = b [1] + a [2] ...$

同时，若 $l$ 为左边界， $r$ 为又边界， $b [r] - b [l - 1] = a [r]$ 到 $a [l]$ 的区间和。

例题

前缀和模板

题目描述

给出一个数字 $n$ 表示有个数字，
给出 $n$ 个整数 $a_{1}, a_{2}, \dots, a_{n}$ 。

给出一个数字 $m$ 。有 $m$ 个询问：
每次询问给出两个整数 $s, e$ ，请求出 $a_{s} + a_{s + 1} + \dots + a_{e}$

输出格式

$m$ 个整数，每一个换一行。

样例

输入

输出

3
5
15

提示

$n \leq 1 0^{5}$ , $a_{i} \leq 1 0^{4}$ 。

这道题目应该这样写

#include <cstdio>
using namespace std;

int a[100001], b[100001];
int n, m;
int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++)
    {
        scanf("%d", &a[i]);
    }
    
    b[1] = a[1];
    for(int i = 1; i <= n; i ++)
    {
        b[i + 1] += b[i] + a[i + 1];
    }
    
    scanf("%d", &m);
    for(int i = 1; i <= m; i ++)
    {
        int s, e;
        scanf("%d %d", &s, &e);
        printf("%d\n", b[e] - b[s - 1]);
    }
    
    return 0;
}