前缀和(一维)

一、算法描述

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

什么是前缀和?

  • 前缀和是某一个序列的前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\)

输入样例:

5 3
2 1 3 6 4
1 2
1 3
2 4 

输出样例:

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;
}

热门相关:宠物小精灵之庭树   我是仙凡   重生成偏执霍少的小仙女   一等狂妃:邪王,请接招!   重生成偏执霍少的小仙女