Content deleted Content added
ToadetteEdit (talk | contribs) Declining submission: nn - Submission is about a topic not yet shown to meet general notability guidelines (be more specific if possible) (AFCH) |
Added a bit more information and another source |
||
Line 7:
<!-- Important, do not remove anything above this line before article has been created. -->
An array that is constructed using a sequence of numbers <math>A=\{x_{0},x_{1},...,x_{n}\}</math> and the differences between each element forming a new array <math>D(A)=y_{0},y_{1},...,y_{n}</math> in which <math>y_{i}=x_{i}-x_{i-1}</math>. The difference array of <math>A</math> can be denoted as <math>D(A)</math>. The main goal of a difference array is to show the amount of change between consecutive elements in an array.<ref name=":2">{{Cite book |last=Laaksonen |first=Antti |url=https://www.google.com/books/edition/Guide_to_Competitive_Programming/3JbiDwAAQBAJ?hl=en&gbpv=0 |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 13:
y{1}=x_{1}-x_{0} \\
\vdots \\
y_{n}=x_{n}-x_{n-1
\end{array}</math>
Line 23:
== Range Queries ==
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> 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" />
To obtain the final array a prefix sum can be performed on <math>D(A)</math>, then when the prefix sum of <math>D(A)</math> is added to <math>A</math> all the queries that were to being applied to <math>A</math> will be performed through a single iteration.<ref name=":1" />
Line 40:
\end{array}</math>
Thus the middle x cancels out showing that <math>x</math> has no effect on the differences of the middle values.
== References ==
| |||