Draft:Difference array

Computer Science Algorithm

Review waiting, please be patient. This may take 7 weeks or more, since drafts are reviewed in no specific order. There are 2,089 pending submissions waiting for review. If the submission is accepted, then this page will be moved into the article space. If the submission is declined, then the reason will be posted here. In the meantime, you can continue to improve this submission by editing normally. Where to get help If you need help editing or submitting your draft, please ask us a question at the AfC Help Desk or get live help from experienced editors. These venues are only for help with editing and the submission process, not to get reviews. If you need feedback on your draft, or if the review is taking a lot of time, you can try asking for help on the talk page of a relevant WikiProject. Some WikiProjects are more active than others so a speedy reply is not guaranteed. How to improve a draft Wikipedia:Contributing to Wikipedia – a basic overview on how to edit Wikipedia. Help:Wikitext – how to use the markup Help:Referencing for beginners – how to include references Wikipedia:Article development – how to develop your article Wikipedia:Writing better articles – how to improve your article Wikipedia:Verifiability – make sure your article includes reliable third-party sources You can also browse Wikipedia:Featured articles and Wikipedia:Good articles to find examples of Wikipedia's best writing on topics similar to your proposed article. Improving your odds of a speedy review To improve your odds of a faster review, tag your draft with relevant WikiProject tags using the button below. This will let reviewers know a new draft has been submitted in their area of interest. For instance, if you wrote about a female astronomer, you would want to add the Biography, Astronomy, and Women scientists tags. Add tags to your draft Editor resources Easy tools: Citation bot (help) | Advanced: Fix bare URLs Reviewer tools Instructions · What links here · Difference array (talk: + · bio) · (log) · Copyvios report · reFill · Citation Bot · (Search: Google, Wikipedia) · Submitted 3 months ago by Heyyo53 (talk: D · +) · Last edited 3 months ago by Heyyo53

An array that is constructed using a sequence of numbers ${\displaystyle A=\{x_{0},x_{1},...,x_{n}\}}$ and the differences between each element forming a new array ${\displaystyle D(A)=y_{0},y_{1},...,y_{n}}$ in which ${\displaystyle y_{i}=x_{i}-x_{i-1}}$. The difference array of ${\displaystyle A}$ can be denoted as ${\displaystyle D(A)}$^[1]

${\displaystyle {\begin{array}{l}y_{0}=x_{0}\\y{1}=x_{1}-x_{0}\\\vdots \\y_{n}=x_{n}-x_{n-1}-...-x_{1}-x_{0}\\\end{array}}}$

Inverse Function

A difference array can be undone using a prefix sum array. Here the prefix sum array is denoted as ${\displaystyle P(c,A)}$  where ${\displaystyle c}$  is an arbituary constant prepending the prefix sum array. Given that ${\displaystyle c}$  is ${\displaystyle A_{0}}$  by plugging into the prefix sum function ${\displaystyle P(A_{0},D(A))=A}$ ^[1]

Uniqueness of Difference Arrays

${\displaystyle A}$  only has a single difference array ${\displaystyle D(A)}$ . If no additional inputs are given ${\displaystyle D(A)}$  uses the elements of ${\displaystyle A}$  to form the difference array. The non-communativity of subtraction only allows for single way to represent a given difference array.^[1]

Range Queries

A difference array can be used to update an array that is being modified using range queries in constant time.^[2] Here a query ${\displaystyle (l,r,x)}$  with ${\displaystyle l,r}$  as the left and right indices of the array to edit and ${\displaystyle x}$  as the value to add to the elements within ${\displaystyle [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 ${\displaystyle [l,r]}$  the elements of ${\displaystyle D(A)}$  will remain unchanged except for ${\displaystyle D(A)[l],D(A)[r]}$  which will be ${\displaystyle x}$  more than before the query. This allows for a range query to be expressed by ${\displaystyle D(A)[l]+1}$  and ${\displaystyle D(A)[r+1]-1}$ .^[3]

To obtain the final array a prefix sum can be performed on ${\displaystyle D(A)}$ , then when the prefix sum of ${\displaystyle D(A)}$  is added to ${\displaystyle A}$  all the queries that were to being applied to ${\displaystyle A}$  will be performed through a single iteration.^[2]

Proof

The relative differences of the values that lie within the range ${\displaystyle (l,r)}$  will remain unchanged after a range query is performed. However the elements ${\displaystyle l-1}$  and ${\displaystyle r+1}$  will have their relative differences change. Since each element within ${\displaystyle [l,r]}$  is increasing by ${\displaystyle x}$  element ${\displaystyle l}$  will be ${\displaystyle x}$  greater than the previous entry, similarly element ${\displaystyle r}$  will be x less than the next entry in the array.

${\displaystyle 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}]}$ 

${\displaystyle D(A)=[a_{1},(a_{2}-a_{1})+x,(a_{3}-a_{2})+x,(a_{4}-a_{3})+x,a_{5}-a_{4}]}$ 

${\displaystyle {\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 ${\displaystyle x}$  has no effect on the differences of the middle values.

References

1. "Prefix sum array and difference array - PEGWiki". wcipeg.com. Retrieved 2025-05-20.
2. Katiyar, Ishank (2021-07-30). "Understanding Difference Array: The Underrated Constant Time Range Update Algorithm (Part 1)". Medium. Retrieved 2025-05-20.
3. Nadaf, Aman (2023-02-28). "Difference Array Technique". TeckBakers. Retrieved 2025-05-20.