Prefix and (one dimension)

Preface

   Space complexity has a very important influence on the running time of code 
   effect , In the code, prefix and are properly used for maintenance 
   It can save time and complexity .

One 、 What is the prefix and ？

The prefix and , Popular said ： For an array with some numbers , The prefix is the prefix of the array k Value of item addition , Therefore, the corresponding prefix sum is before the array k Sum of items . For an array , ask [L,R] And （ From L Items to R The sum of the values of the items ）, You can use prefix and to solve .

Two 、 One dimensional prefix and explanation

The one-dimensional prefix sum is probably ： There is a N An array of numbers arr[ ], On the q Times of inquiry [L,R] And .

Illustrate with examples

Array arr[ ] By 1,3,7,5,2 Form in order , On the 3 The second inquiry is
[2,4],[0,3],[3,4] And .
General solution ：
For the first time : Interval and [2,4]=7+2+5=14;
The second time : Interval and [0,3]=1+3+7+5=16;
For the third time : Interval and [3,4]=5+2=7;
It would be too much trouble to add the array one by one before each query , At this point we can introduce prefixes and arrays :

sum[i]=sum[i-1]+arr[i]     i>0
sum[0]=arr[0]              i=0

Explain it. sum[i]==arr[0]+arr[i]+…+arr[i], namely sum[i] Namely arr Array from 0 Items to i Sum of items .

arr  1   3    7    5   2
sum  1   4   11   16  18

from sum It is much easier to solve the problem by array
For the first time : Interval and [2,4]=sum[4]-sum[1]=18-4=14=7+5+2
reason ： take arr The array is divided into two pieces , One piece is made of 0 Item and the first item form the non required part ,
The other is from the 2 Items to 4 The required part of the item , The two together make up the whole sum[4],
From the first 0 The non desired part of the term and the first term can be regarded as sum[1],
Required part = whole sum[4]- Not required sum[1]

Not required	Required
1 3	7 5 2

Expand the scope , Open your eyes ,
Set interval and [L,R] use sum[L,R] Express
According to the first solving process , We can launch

sum[L,R]=sum[R]-sum[L-1]   L>0
sum[L.R]=sum[R]            L=0

The code is as follows （ Example ）：

#include<iostream>
using namespace std;
const int n=5;
int sum[n];
int get_sum(int L,int R)
{
    
	if(L!=0)
		return sum[R]-sum[L-1];
	else
		return sum[R];
}
int main()
{
    
	int arr[n]={
    1,3,7,5,2};
	sum[0]=arr[0];
	for(int i=1;i<n;i++)
		sum[i]=sum[i-1]+arr[i];
	cout<<get_sum(2,4)<<endl;
	cout<<get_sum(0,3)<<endl;
	cout<<get_sum(3,4)<<endl;
	return 0;
}

Code presents , Help to understand

---

summary

This chapter is about one-dimensional prefixes and simplifications , I passed through b Station learning , It's my own notes , I hope you can also learn .