Why two endpoint changes suffice
Suppose are numbers with . An update adds to every with , where . If all updates are known before the final array is needed, changing each entry of each interval separately can repeat much work. A difference array records where an effect starts and where it stops.
This lesson connects the earlier Fenwick and segment-tree lessons. Assume that arithmetic and array access take constant time, and that the numeric representation handles the sums exactly without overflow.
The invariant
Definition 4.1.1
(Difference array with a sentinel)
Use indices . Set , for , and choose the extra sentinel . For every actual position , the original value telescopes:
The sentinel is not part of the reconstructed array. To add on , change only
This also handles : the second change goes to , outside every actual prefix. The sentinel was initialized to zero as bookkeeping; it need not equal a difference involving an imagined .
Proposition 4.1.2
(Range addition by two endpoint changes)
Let be the difference array above and let be an update with . Replace by and by . Then every prefix sum with changes by when and by otherwise. Hence, after any finite sequence of such updates, the prefix sums of equal the array obtained by applying the updates directly.
Proof
(Prefix sums see the change only between l and r)
At a position , the change in the prefix sum is
This verifies one update at every position. Repeating the argument or adding the increments proves the invariant after any finite sequence of updates, including overlapping intervals and negative increments.
Proof X-ray
Where the argument uses each endpoint
The one non-obvious move is to write the interval as the difference of two step functions: switches the effect on for every later prefix, and switches it off again. Because is included, the canceling step begins at the first position after the interval, namely , not at .
The hypothesis guarantees that the canceling step comes after the starting step, so the difference is a genuine indicator of . When the canceling step is never seen by an actual prefix, which is why the sentinel exists. Linearity does the rest: each update contributes independently, so overlapping or negative updates need no case analysis. The values of never enter the argument.
After processing all updates, make one left-to-right prefix pass through to output the final . Initializing differences and reconstructing cost , and updates cost , so the total time is and the additional array uses space. This is an offline bound: producing all current values after each update would require additional output work.
A trace
Worked example 4.1.3
(Two overlapping updates on five entries)
Start with , so . Apply on , then on . The endpoint changes produce
The first five prefix sums are . Directly applying the two updates to gives the same result. The sixth entry is a sentinel, not a sixth output value.
Worked example 4.1.4
(An update that ends at the last position)
With the same , add on . Then , so the second change goes to the sentinel: and , giving . The first five prefix sums are , which is with its last entry increased by . The sentinel is never part of an output prefix.
Worked example 4.1.5
(A single interior position)
Take , so . Add on . The changes are and , giving . The prefix sums are , so only changed, from to . A zero entry such as the original records "no change from the previous value", not "the value is zero".
Common mistake
(Reading a difference entry as the array value)
After the first update of the trace the difference array is , but the array is . The entry says only that is three less than ; it is not . Always take a prefix sum of before reading a value.
Common mistake
(Allocating only n difference slots)
An update with writes to . If the array has just slots, this write is out of range in a language that checks bounds, and silently corrupts neighboring memory in one that does not. Allocate slots even though only the first prefix sums are output.
Counterexample mode
Stopping at r instead of r+1
Claim: to add on , add at and subtract it at . Take , so , and add on . The claimed rule gives , whose first four prefix sums are . But the update must give , so position is missed. On a one-element interval such as the two changes even land on the same entry and cancel, so nothing changes at all. Because is included, the canceling change belongs at .
Online point values
If range additions and individual point queries are interleaved, store in the Fenwick tree from the earlier lesson. Each range addition becomes two point additions; querying is the Fenwick prefix sum . A tree including the sentinel has positions. With the earlier tree's assumptions and constant-time arithmetic, each update or point query takes time. A one-indexed query never asks for the sentinel as an actual array position.
This single tree supplies range additions and point values. It does not automatically give a range sum of current in one prefix query; that is a different operation requiring further structure or computation. Choose this method for its operation contract, not solely because it uses a familiar tree.
Exercises with solutions
Quick check
(Last position. For an update on , which difference entries change?)
Solution · Answer
gains and loses ; the only actual prefix affected is at .
Quick check
(Cancellation. What happens after adding and then on the same interval?)
Solution · Answer
Both endpoint changes cancel, so every reconstructed value returns to its original value.
Quick check
(Trace check. After the first update in the trace, what is ?)
Solution · Answer
The first four updated differences sum to ; equivalently .
Quick check
(Operation scope. Does one Fenwick prefix query on give ?)
Solution · Answer
Not in general: it gives one current point value. A singleton or accidental numerical equality may coincide, but arbitrary range sums require an additional derivation or structure.