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.