Difference Array

array
range-queries

#1

Can someone explain Difference Array concept? I know it’s implementation but i’m not able to figure out why it works?


#2

You mean +1 -1 and then prefix sum right ?
Then just do +1 somewhere and do the prefix sum and observe the array…
Again take a new array do +1 -1 and again prefix sum… and keep on observing it…

Prefix sum is such that the effect of ith element will be on all the elements from ith to the last element of that array…
+1 at position i will cause a +1 at all positions after i (including i) and hence it works…
Basically you are updating all the entries from L to size by +1 and you are updating all the entries from R to size by -1…
And hence effect on R to size nullifies…


#3

I’m talking about this question: https://www.spoj.com/problems/UPDATEIT/
though it is a question of bit-masking ,still it can be done through difference array ( in comments you can see) .
Here is what I found on geeks4geeks : https://www.geeksforgeeks.org/difference-array-range-update-query-o1/


#4

yes replace +1 -1 with +val and -val in above answer…
I understood your question correctly…
feel free to ask more queries