前缀和

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, \cdots, a_n\) 和 \(m\) 个区间 \([l_i,r_i]\)，分别求这 \(m\) 个区间的区间和。 ## 3 输入格式 \[ \boxed{ \begin{align} &n &\\ &a_{1} \ a_2 \cdots \ a_n \\ &m \\&l_1\ \ r_1 \\&l_2\ \ r_2\\ &\vdots \\&l_m\ r_m​ \end{align} } \]

满足 \(1\le l_i\le r_i\le n\) , \(1 \leq n,m\le 10^5\)，\(1 \leq a_i\le 10^4\)。 ## 4 输出格式 \[ \boxed{ \begin{align} &res_1 \\ &res_2 \\ &\vdots \\&res_m​ \end{align} } \] 共 \(m\) 行。

第 \(i\) 行为第 \(i\) 组答案的询问。

5 样例 #1

5.1 样例输入 #1

4
4 3 2 1
2
1 4
2 3

5.2 样例输出 #1

10
5