Difference Arrays

Difference arrays encode where a sequence changes, making a whole interval addition require only two boundary edits. After all updates, a prefix sum reconstructs the final values. This is ideal for an offline batch of range additions when intermediate range answers are unnecessary. It complements prefix sums: prefixes accumulate values, while differences record the increments needed to recover them.

Prerequisites: Prefix Sums; arrays; signed arithmetic.

Build the idea

1. 1. Take differences of the initial array

   Define d[0]=a[0] and d[i]=a[i]−a[i−1] for i>0. Then a[i]=d[0]+…+d[i] by cancellation. For [1,2,3,4,5], differences are [1,1,1,1,1]. We allocate n+1 entries so index n is a valid stopping sentinel for updates ending at n−1.

2. 2. Add at the start and cancel after the end

   To add x to inclusive [l,r], increase d[l] by x and decrease d[r+1] by x. During reconstruction, the running prefix increases starting at l and stays increased until reaching r+1, where cancellation restores the previous level. There is no need to touch every element of the interval for each update.

3. 3. Combine overlapping updates

   Starting from [1,2,3,4,5], add 10 to [1,3] and −2 to [0,2]. Their effects superpose because addition is linear. The result is [−1,10,11,14,5]. At index 1 both updates apply; at index 3 only +10 applies; the last index remains unchanged. Boundary edits can be performed in any order because they add to the same differences.

4. 4. Reconstruct exactly once

   After processing all q updates, scan i=0..n−1 with current+=d[i], and print current. The sentinel d[n] is not an output element; it only records cancellation outside the final range. Initial differences are computed from the original consecutive input values using previous; do not overwrite an element before its old value has been used for the next difference.

5. 5. Understand the offline restriction

   A difference array does not immediately provide every updated a[i] as an independent stored value. Reconstruction costs O(n), so reconstructing after every update loses the batch advantage. If queries must be answered between updates, a Fenwick-based difference structure or lazy segment tree may be appropriate. This program supports additions, not arbitrary range assignment or multiplying an interval.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
int main(){
    int n,q;
    std::cin>>n>>q;
    std::vector<long long>difference(n+1,0);
    long long previous=0;
    for(int i=0;i<n;++i){
        long long x;
        std::cin>>x;
        difference[i]=x-previous;
        previous=x;
    }
    while(q--){
        int l,r;
        long long value;
        std::cin>>l>>r>>value;
        difference[l]+=value;
        difference[r+1]-=value; // n is allocated as a sentinel.
    }
    long long current=0;
    for(int i=0;i<n;++i){
        current+=difference[i];
        std::cout<<current<<(i+1==n?'\n':' ');
    }
    if(n==0){
        std::cout<<'\n';
    }
}

Complexity analysis

O(n+q) total time: O(n) initialization, O(1) per range addition, O(n) final reconstruction. O(n) memory including the extra sentinel. With n,q≤200000 and initial/update magnitudes≤10^9, accumulated values remain safely inside long long. This is not O(1) arbitrary interleaved range-query support.

Example input and output

Read n q (0..200000), n initial integers, then q updates l r x for inclusive zero-based valid ranges. Initial values and x have absolute value≤10^9. Print the final array; n=0 requires q=0.

Input

5 2
1 2 3 4 5
1 3 10
0 2 -2

Output

-1 10 11 14 5

The first three entries receive −2; positions 1..3 also receive +10. Position 4 receives neither.

Practical applications

Use for batch increments, event coverage counts and applying many interval contributions before reading all final values. Prefix sums solve static queries instead. Dynamic online operations require an additional data structure chosen for the exact update/query combination.

Check your understanding

Where does an inclusive [l,r] increment stop in the difference array?

Put it into practice

Begin with zeros and use updates to count how many intervals cover each index.