算法基础课题解合集

什么是前缀和

前缀和 $S_i$ 是指数组前 $i$ 个元素的和，如下图。

前缀和公式很明显是 $S_i = S_{i - 1} + A_i$

前缀和的作用

如题目中所说，给定 $l$ 和 $r$，要求 $A_l$ 到 $A_r$ 的和。

其实这个问题的答案就是 $S_r - S_{l - 1}$。

那么，为什么呢？

首先我们先来看一下 $S_r$ 和 $S_{l - 1}$ 是什么

$S_r = A_1 + A_2 + A_3 + \dots + A_{r - 1} + A_{r}$

$S_{l - 1} = A_1 + A_2 + \dots + A_{l - 1}$

$S_r - S_{l - 1} = A_l + A_{l + 1} + A_{l + 2} + \dots + A_{r - 1} + A_{r}$

所以这是对的。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;

const int N = 100010;
int n, m;
int s[N], a[N];

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

好了，这篇题解到这里就结束啦！感谢观看！！！

$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\mathcal{writer\enspace by \enspace acwing}$ : $\mathfrak{天元之弈}$