Draft:Difference array

An array that takes a sequence of numbers $A=\{x_0,x_1,\mathrm{...},x_n\}$ and stores the differences between each element in the array. More generally an array $D(A)=y_0,y_1,\mathrm{...},y_n$ where $y_i=x_i-x_{i-1}$. The difference array of a sequence $A$ can be denoted as $D(A)$. Commonly a difference array is use to make a series of range queries with constant time complexity:

$\begin{array}{c}{y}_0=x_0\\ y1=x_1-x_0\\ ⋮\\ y_n=x_n-x_{n-1}\end{array}$

Properties

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.

Usage

Range Queries

Range queries are an array modifying operation that add a value to a defined range of values

$(l,r,x)$

• $l,r$ Left and right indices of the range of elements to edit (inclusive).
• $x$ Value to add to the elements within $[l,r]$.

Difference arrays are used to update arrays that are modified using range queries within constant time. initially the difference array has each element set to 0. Difference arrays when modified using a range query only require changes to the elements that lie on the bounds of the range query. So given a range query of $(l,r,x)$ the elements of $D(A)$ will remain unchanged except for at index $l$ and $r+1$ . This allows for the entire range query to be expressed by modifying $A_l+1$ and $A_{r+1}-1$ rather than updating each element between.

$D(A)=[0,0,0,0,0]\underset{(l,r,x)}{\underbrace{\to }}\begin{array}{c}D(A)[l]=1\\ D(A)[r+1]=-1\end{array}$

By performing a prefix sum on $D(A)$, once added to $A$ in where each matching index is added to the others, the resulting array will be as if each query was performed. This allows for any number of queries to $A$ to be performed within 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]\underset{(2,4,x)}{\underbrace{\to }}[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}{cc}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.

Steganalaysis

Methods of JPEG base steganography can be detected using difference arrays. It has been shown that Markov features that were extracting from zigzag intra-block and inter-block difference array improve steganography detection substantially. By calculating difference arrays along the horizontal and vertical directions of the JPEG's data array, then applying a Markov matrix to these difference arrays intra-block features are able to be constructed.