Draft:Difference Array

An array that is constructed using a sequence of numbers $A=\{x_{0},x_{1},...,x_{n}\}$ and the differences between each element forming a new array $D(A)=y_{0},y_{1},...,y_{n}$ in which $y_{i}=x_{i}-x_{i-1}$. The difference array of $A$ can be denoted as $D(A)$

${\begin{array}{l}y_{0}=x_{0}\\y{1}=x_{1}-x_{0}\\\vdots \\y_{n}=x_{n}-x_{n-1}-...-x_{1}-x_{0}\\\end{array}}$

Inverse Function

A difference array can be undone using a prefix sum array. Here the prefix sum array is denoted as $P(c,A)$ where $c$ is an arbituary constant prepending the prefix sum array. Given that $c$ is $A_{0}$ by plugging into the prefix sum function $P(A_{0},D(A))=A$

Uniqueness of Difference Arrays

$A$ only has a single difference array $D(A)$. If no additional inputs are given $D(A)$ uses the elements of $A$ to form the difference array. The non-communativity of subtraction only allows for single way to represent a given difference array.

Range Queries

A difference array can be used to update an array that is being modified using range queries in constant time. Here a query $(l,r,x)$ with $l,r$ as the left and right indices of the array to edit and $x$ as the value to add to the elements within $[l,r]$. Difference arrays exhibit a unique property where when modified with a range query only the bounds of said query are modify. So given the range $[l,r]$ the elements of $D(A)$ will remain unchanged except for $D(A)[l],D(A)[r]$ which will be $x$ more than before the query. This allows for a range query to be expressed by $D(A)[l]+1$ and $D(A)[r+1]-1$.

To obtain the final array a prefix sum can be performed on $D(A)$, then when the prefix sum of $D(A)$ is added to $A$ all the queries that were to being applied to $A$ will be performed through a single iteration.

Proof

The relative differences of the values that lie within the range $(l,r)$ will remain unchanged after a range query is performed. However the elements $l-1$ and $r+1$ will have their relative differences change. Since each element within $[l,r]$ is increasing by $x$ element $l$ will be $x$ greater than the previous entry, similarly element $r$ will be x less than the next entry in the array.

$A=[a_{1},a_{2},a_{3},a_{4},a_{5}]\underbrace {\to } _{(2,4,x)}[a_{1},a_{2}+x,a_{3}+x,a_{4}+x,a_{5}]$

$D(A)=[a_{1},(a_{2}-a_{1})+x,(a_{3}-a_{2})+x,(a_{4}-a_{3})+x,a_{5}-a_{4}]$

${\begin{array}{l}D(A)[2]&=(a_{2}-a_{1})+x\\D(A)[3]&=(a_{3}-a_{2})+x=(a_{3}-((a_{2}-a_{1})+x)+x\\&=a_{3}-(a_{2}-a_{1})-x+x=a_{3}-a_{2}+a_{1}\end{array}}$

Thus the middle x cancels out showing that $x$ has no effect on the differences of the middle values.