Content deleted Content added
Citation bot (talk | contribs) Removed parameters. | Use this bot. Report bugs. | Suggested by Eastmain | #UCB_webform 458/1621 |
Citation bot (talk | contribs) Alter: url, title, template type. URLs might have been anonymized. Add: isbn, chapter, authors 1-1. Removed URL that duplicated identifier. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | #UCB_CommandLine |
||
| (11 intermediate revisions by 5 users not shown) | |||
Line 1:
{{AFC submission|d|nn|u=Heyyo53|ns=118|decliner=CoconutOctopus|declinets=20250610091154|reason2=essay|ts=20250523233053}} <!-- Do not remove this line! -->
{{Short description|Algorithm}}▼
{{AFC submission|d|nn|u=Heyyo53|ns=118|decliner=ToadetteEdit|declinets=20250521084736|small=yes|ts=20250520231757}} <!-- Do not remove this line! -->
▲{{Short description|Computer Science Algorithm}}
{{Draft topics|stem}}
{{AfC topic|stem}}
<!-- Important, do not remove anything above this line before article has been created. -->
An array that
<math>\begin{array}{l}
Line 12 ⟶ 15:
y{1}=x_{1}-x_{0} \\
\vdots \\
y_{n}=x_{n}-x_{n-1
\end{array}</math>
== Properties ==
=== Inverse Function ===
A difference array can be undone using a prefix sum array. Here the prefix sum array is denoted as <math>P(c, A)</math> where <math>c</math> is an arbituary constant prepending the prefix sum array. Given that <math>c</math> is <math>A_0</math> by plugging into the prefix sum function <math>P(A_0, D(A))=A</math><ref name=":0" />
=== Uniqueness of Difference Arrays ===
<math>A</math> only has a single difference array <math>D(A)</math>. If no additional inputs are given <math>D(A)</math> uses the elements of <math>A</math> to form the difference array. The non-communativity of subtraction only allows for single way to represent a given difference array.<ref name=":0" />
== Usage ==
=== Range Queries ===
[[Range Queries|Range queries]] are an array modifying operation that add a value to a defined range of values
A difference array can be used to update an array that is being modified using range queries in constant time.<ref name=":1">{{Cite web |last=Katiyar |first=Ishank |date=2021-07-30 |title=Understanding Difference Array: The Underrated Constant Time Range Update Algorithm (Part 1) |url=https://medium.com/@ishankkatiyar162/understanding-difference-array-the-underrated-constant-time-range-update-algorithm-part-1-e432ada7f1f5 |access-date=2025-05-20 |website=Medium}}</ref> Here a query <math>(l, r, x)</math> with <math>l, r</math> as the left and right indices of the array to edit and <math>x</math> as the value to add to the elements within <math>[l,r]</math>.<ref>{{Cite web |last=Nadaf |first=Aman |date=2023-02-28 |title=Difference Array Technique |url=https://teckbakers.hashnode.dev/difference-array-technique |access-date=2025-05-20 |website=TeckBakers}}</ref> 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 <math>[l,r]</math> the elements of <math>D(A)</math> will remain unchanged except for <math>D(A)[l], D(A)[r]</math> which will be <math>x</math> more than before the query. This allows for a range query to be expressed by <math>D(A)[l]+1</math> and <math> D(A)[r+1]-1</math>.▼
<math>(l, r, x)</math>
* <math>l, r</math> Left and right indices of the range of elements to edit (inclusive).
* <math>x</math> Value to add to the elements within <math>[l,r]</math>.
▲
<math>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}</math>
By performing a prefix sum on <math>D(A)</math>, once added to <math>A</math> 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 <math>A</math> to be performed within a single iteration.<ref name=":1" />
==== Proof ====
The relative differences of the values that lie within the range <math>(l,r)</math> will remain unchanged after a range query is performed. However the elements <math>l - 1</math> and <math>r + 1</math> will have their relative differences change. Since each element within <math>[l,r]</math> is increasing by <math>x</math> element <math>l</math> will be <math>x</math> greater than the previous entry, similarly element <math>r</math> will be x less than the next entry in the array.
<math>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}]</math>
<math>D(A) = [ a_{1}, (a_{2}-a_{1})+x, (a_{3}-a_{2})+x, (a_{4}-a_{3})+x , a_{5}-a_{4} ]</math>
<math>\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}</math>
Thus the middle x cancels out showing that <math>x</math> 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.<ref>{{Cite book |last1=Zhou |first1=Zhiping |last2=Hui |first2=Maomao |chapter=Steganalysis for Markov Feature of Difference Array in DCT Domain |date=August 2009 |title=2009 Sixth International Conference on Fuzzy Systems and Knowledge Discovery |volume=7 |pages=581–584 |doi=10.1109/FSKD.2009.230 |isbn=978-0-7695-3735-1 }}</ref>
== References ==
| |||