前缀和

1 B3612 【深进1.例1】求区间和 - 洛谷

1 代码

#include <bits/stdc++.h>
using namespace std;
int n, m, l, r, a[100010];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 2; i <= n; i++)
        a[i] = a[i - 1] + a[i];
    cin >> m;
    for (int i = 0; i < m; i++)
        cin >> l >> r,cout << a[r] - a[l - 1] << '\n';
}

2 题目描述

给定 $n$ 个正整数组成的数列 $a_{1}, a_{2}, \dots, a_{n}$ 和 $m$ 个区间 $[l_{i}, r_{i}]$ ，分别求这 $m$ 个区间的区间和。

3 输入格式

\begin{aligned} n \\ a_{1} a_{2} \dots a_{n} \\ m \\ l_{1} r_{1} \\ l_{2} r_{2} \\ ⋮ \\ l_{m} r_{m} ​ \end{aligned}

满足 $1 \leq l_{i} \leq r_{i} \leq n$ , $1 \leq n, m \leq 10^{5}$ ， $1 \leq a_{i} \leq 10^{4}$ 。

4 输出格式

\begin{aligned} r e s_{1} \\ r e s_{2} \\ ⋮ \\ r e s_{m} ​ \end{aligned}

共 $m$ 行。

第 $i$ 行为第 $i$ 组答案的询问。

5 样例 #1

5.1 样例输入 #1

5.2 样例输出 #1

10
5