Draft:Difference array: Difference between revisions

Revision as of 19:41, 22 May 2025

Revision as of 23:30, 23 May 2025

Line 27:

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

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" />

\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 ====