Draft:Difference array: Difference between revisions

Revision as of 23:30, 23 May 2025

Latest revision as of 14:42, 16 July 2025

(3 intermediate revisions by 3 users not shown)

Line 1:

{{AFC submission|d|nn|u=Heyyo53|ns=118|decliner=ToadetteEditCoconutOctopus|declinets=2025052108473620250610091154|reason2=essay|ts=2025052023175720250523233053}} <!-- Do not remove this line! -->

{{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}}

{{AfC submission|||ts=20250523233053|u=Heyyo53|ns=118}}

{{AFC submission|d|nn|u=Heyyo53|ns=118|decliner=ToadetteEdit|declinets=20250521084736|ts=20250520231757}} <!-- Do not remove this line! -->

<!-- Important, do not remove anything above this line before article has been created. -->

An array that is constructed usingtakes a sequence of numbers <math>A=\{x_{0},x_{1},...,x_{n}\}</math> and stores the differences between each element formingin athe newarray. More generally an array <math>D(A)=y_{0},y_{1},...,y_{n}</math> in whichwhere <math>y_{i}=x_{i}-x_{i-1}</math>. The difference array of a sequence <math>A</math> can be denoted as <math>D(A)</math>. The main goal ofCommonly a difference array is use to showmake thea amountseries of changerange betweenqueries consecutivewith elementsconstant in[[time an array.complexity]]<ref name=":2">{{Cite book |last=Laaksonen |first=Antti |url=https://wwwbooks.google.com/books/edition/Guide_to_Competitive_Programming/3JbiDwAAQBAJ?hlid=en&gbpv=03JbiDwAAQBAJ |title=Guide to Competitive Programming: Learning and Improving Algorithms Through Contests |date=2020-05-08 |publisher=Springer Nature |isbn=978-3-030-39357-1 |publication-date=2020-05-08 |pages=137 |language=en}}</ref><ref name=":0">{{Cite web |title=Prefix sum array and difference array - PEGWiki |url=https://wcipeg.com/wiki/Prefix_sum_array_and_difference_array |access-date=2025-05-20 |website=wcipeg.com}}</ref>

<math>\begin{array}{l}

Line 29:

=== 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 |url-status=live |access-date=2025-05-20 |website=Medium}}</ref> Often in the context of range queries the difference array is initially set to an array of 0's. 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>. 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>.<ref>{{Cite web |last=Nadaf |first=Aman |date=2023-02-28 |title=Difference Array Technique |url=https://teckbakers.hashnode.dev/difference-array-technique |url-status=live |access-date=2025-05-20 |website=TeckBakers}}</ref><ref name=":2" />

<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>.

ADifference differencearrays array can beare used to update an arrayarrays that is beingare modified using [[Range Queries|range queries]] inwithin [[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 |url-status=live |access-date=2025-05-20 |website=Medium}}</ref> Often in the context of range queriesinitially the difference array ishas initiallyeach element set to an array of 0's. HereDifference aarrays querywhen <math>(l,modified r,using x)</math>a withrange <math>l,query r</math>only asrequire thechanges left and right indices ofto the arrayelements tothat editlie and <math>x</math> ason the valuebounds to add toof the elementsrange within <math>[l,r]</math>query. DifferenceSo arrays exhibit a unique property where when modified withgiven a range query only the bounds of said query are modify. So given the range <math>[(l, r], x)</math> the elements of <math>D(A)</math> will remain unchanged except for at index <math>D(A)[l], D(A)[r]</math> which will beand <math>xr + 1</math> more than before the query. This allows for athe entire range query to be expressed by modifying <math>D(A)[A_{l]}+1</math> and <math> D(A)[A_{r+1]}-1</math> rather than updating each element between.<ref>{{Cite web |last=Nadaf |first=Aman |date=2023-02-28 |title=Difference Array Technique |url=https://teckbakers.hashnode.dev/difference-array-technique |url-status=live |access-date=2025-05-20 |website=TeckBakers}}</ref><ref name=":2" />

<math>D(A)=[0,0,0,0,0] \underbrace{\to}_{(l,r,x)}

Line 55 ⟶ 62:

=== 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 journalbook |lastlast1=Zhou |firstfirst1=Zhiping |last2=Hui |first2=Maomao |date=August 2009 |titlechapter=Steganalysis for Markov Feature of Difference Array in DCT Domain |urldate=https://ieeexplore.ieee.org/document/5360076August 2009 |journaltitle=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 ==