Difference (one dimension)

---

Preface

Some time ago, I learned the one-dimensional prefix and , One dimensional prefixes and arrays can be integrated , Today, learn about one-dimensional difference , One dimensional difference can perform regional addition and subtraction operations on the array .

---

One 、 What is the difference ？

 Difference and prefix sum often correspond to each other in the algorithm , It's a strategy 
 Make b [i]=a[i] −a[i-1]  , That is, the difference between two adjacent numbers .

————————————————

Two 、 Difference is property

 The difference array can get the original array by prefix and （）

Two 、 One dimensional difference explanation

introduce

One by 5 An array of numbers arr[5]={1,3,7,5,2}
On the 3 operations
： stay [2,4] +5
stay [1,3] +2
stay [0,2] -3
Finally, ask 1 Time :arr[]={ }

arr[5]
1 3 7 5 2

If we operate step by step

arr[5]
1   3  7    5  2
1   3  12  10  7
1   5  14  12  7
-2  2  11  12  7

Step by step, you will finally get the knot arr[5]={-2,2,11,12,7}
But if the data is big , Such solution space complexity will completely exceed the time limit ,
So we introduce the difference .
Ask for the travel score group first d[i]= arr[i]− arr[i-1] // i>0
d[0]=arr[0]

 Difference is the difference between two adjacent numbers （ reason ）
 So when we talk about the n When items are changed , From n After item 
 All numbers will be affected accordingly  .
( You can imagine dominoes , The whole body moves at once )
  
  
 If to the second L Item , Right. R+1 Item with the opposite change ,
 So the space for change is just [L,R]（ Push your fingers down L Dominoes from L
 Later, the dominoes fell down one by one , In order to involve the R+1 Hold your fingers while playing cards 
 It didn't fall , So the only thing that has fallen or changed is [L,R]）

It's easy to understand .
We call this operation ： Differential marking

Carries out an The difference tag can get the difference array after all operations are changed , According to this difference array , You can restore it with the property of difference to get the original array after all operations are changed .

We will use the difference mark in the title ：
First of all arr【】 Array determines the differential array of d【】
Proceed again ± operation

 d【2】+5    d【5】-5   // Yes d【5】-5 Operation is optional , Across the border 

It affects the 2 Items to 5 term （ It can also be said that the whole array behind , So for d【5】 The operation of is optional ）
here

d    1  2  9   -2  -3    // Properties of difference -- Restore the original array 
arr  1  3  12  10   7

The rest is almost the same , I don't want to explain it anymore

Code operation

The code is as follows （ Example ）：

#include<iostream>
using namespace std;
int d[6]={
    0};  // Initialize the differential array d,d[6] Than 
               //arr[5] Big 1 prevent d[R+1]+-v Transboundary 
               // It can also be replaced by d[5]={0}
void add(int L,int R,int v)
{
    
	d[L]+=v;
	d[R+1]-=v;
}
int main()
{
    
	int arr[5]={
    1,3,7,5,2};
	add(2,4,5);
	add(1,3,2);
	add(0,2,-3);
	for(int i=1;i<5;i++)
		d[i]+=d[i-1];
	for(int i=0;i<5;i++)
	{
    
		arr[i]+=d[i];
		cout<< arr[i] <<" ";
	}
	return 0;
}

---

summary

One dimensional difference is also relatively simple , Just figure out the difference array and the difference tag , Think of dominoes to help understand .