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)$. The main goal of a difference array is to show the amount of change between consecutive elements in an array.

${\begin{array}{l}y_{0}=x_{0}\\y{1}=x_{1}-x_{0}\\\vdots \\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

A difference array can be used to update an array that is being modified using range queries in constant time. Often in the context of range queries the difference array is initially set to an array of 0's. 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$.

$D(A)=[0,0,0,0,0]\underbrace {\to } _{(l,r,x)}{\begin{array}{l}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}]\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.

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.