前缀和（一维）-Toy模板网

这篇具有很好参考价值的文章主要介绍了前缀和（一维）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、算法描述

本篇文章我们来介绍一个简单的算法，前缀和。

什么是前缀和？

前缀和是某一个序列的前n项的和，可以理解为数学上的数列的前n项和。
如果 \(a\) 和 \(s\) 分别是原数组和前缀和数组，那么应该有如下关系：

s[1] = a[1];、s[2] = a[1] + a[2];、s[3] = a[1] + a[2] + a[3];

如何得到前缀和？

显然如果按照上面的累加法得到前缀和数组时间复杂度较大，所以我们换一个思路。
\(s[i]\) 表示的是前 \(i\) 项的和，那么要求前 \(i + 1\) 项的和，即 \(s[i + 1]\) ，只需要在 \(s[i]\) 的基础上加上 \(a[i + 1]\) 即可得到 \(s[i + 1]\) 了。
所以可以得到递推关系式：s[i] = s[i - 1] + a[i];。

前缀和有什么作用？

当我们需要查询数组某段区间 \([l, r]\) 的和时，如果从 \(l\) 遍历到 \(r\) ，那么时间复杂度为 \(O(n)\) ，这个时候就可以用到前缀和的性质了。
\(s[r]\) 表示数组 \(a\) 的前 \(r\)项和，要求 \([l, r]\)区间内的和，只需要减去前 \(l - 1\) 项的和，即 \(s[l - 1]\) ，这样只需要 \(O(1)\)的时间复杂度就可以获取区间 \([l, r]\) 内的和。

二、题目描述

输入一个长度为 \(n\) 的整数序列。

接下来再输入 \(m\) 个询问，每个询问输入一对 \(l,r\)。

对于每个询问，输出原序列中从第 \(l\) 个数到第 \(r\) 个数的和。

输入格式

第一行包含两个整数 \(n\) 和 \(m\)。

第二行包含 \(n\) 个整数，表示整数数列。

接下来 \(m\) 行，每行包含两个整数 \(l\) 和 \(r\)，表示一个询问的区间范围。

输出格式

共 \(m\) 行，每行输出一个询问的结果。

数据范围

\(1≤l≤r≤n,\)
\(1≤n,m≤100000,\)
\(−1000≤数列中元素的值≤1000\)文章来源地址https://www.toymoban.com/news/detail-711114.html

输入样例：

输出样例：

3
6
10

三、题目来源

AcWing算法基础课-795.前缀和

四、源代码

#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
int a[N], s[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;
}

到了这里，关于前缀和（一维）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！