- 2020-07-16 17:20
*views 3*

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 .

answer ：

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 4

views 3

views 3

views 3

©2019-2020 Toolsou All rights reserved,

QQ Login interface implementation code implementation mysql Addition, deletion, modification and query of database JAVA Experiment 4 set and functional programming experiment about String How to create objects VHDL——4 choose 1 Data selector C language （ Guess numbers games ） Blue Bridge Cup MCU advanced module --NE555 I don't memorize eight part essays , You go to the interview ? Hill sorting of sorting algorithm ——c++ realization python What does built-in function mean _python What are the built-in functions