Enter a length of n Integer sequence of .

Then enter m A query , Enter a pair for each query l, r.

For each query , Output from the original sequence l Number to r Sum of numbers .

Input format
The first line contains two integers n and m.

The second line contains n Integer , Represents an integer sequence .

next m that 's ok , Each line contains two integers l and r, Indicates the range of a query .

Output format
common m that 's ok , Output the result of one query per line .

Data range
1≤l≤r≤n,
1≤n,m≤100000,
−1000≤ The value of an element in a sequence ≤1000
sample input ：
5 3
2 1 3 6 4
1 2
1 3
2 4
sample output ：
3
6
10

This question is the purest prefix and question .
Let's use this question to talk about prefix and prefix .

first , Let's first understand what prefix and prefix are according to the figure below .

So we know , Prefix and are from location 1 To position i The sum of all the numbers in this interval .

Now that we understand what prefix and are all about , Let's see how we can input
Give the answer first , Then give the analysis .
for (int i = 1; i <= n; i ++ ){ cin >> a[i]; s[i] = s[i - 1] + a[i]; }
Let's use this picture to understand why we can get prefixes and prefixes by writing code like this

Until now , We have solved the problem of input and prefix sum , Here's how we use prefixes and .
We use prefixes and have a big advantage , That is, you can quickly get the interval sum of a certain interval

<> Advantages of prefixes and ： with (o1) Get the sum of some intervals according to the time complexity of

good , Let's first look at how to sum an interval
We use L and R Represent the left and right endpoints of the interval respectively ,
that

good , There are so many prefixes
Here's my code
#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],
s[i] = s[i - 1] + a[i]; while (m -- ){ int l, r; cin >> l >> r; cout << s[r] -
s[l - 1] << endl; } return 0; }

Technology
Daily Recommendation
views 5
views 3
views 3