Efficient Range Addition in Arrays Using Difference Array (C++)

---

Problem Statement:
You are given an array:

arr = {10, 20, 30, 40, 50};

And the following queries:

1. Add 5 to every element in the interval [1, 3]

2. Add 10 to every element in the interval [2, 4]

What should the final array look like after all these updates? And how can we do it efficiently?

---

Naive Approach (Brute Force)

For each query, we loop from the index l to r and add the value:

for (int i = l; i <= r; i++) {
    arr[i] += val;
}

But if the number of queries is large (like 100,000), this becomes very slow: O(N * Q) time.

---

Optimized Approach: Difference Array

We use a trick called a difference array to make range updates super efficient — in just O(1) per query!

How it Works

Instead of updating every index from l to r, we update only two places:

diff[l] += val;
diff[r + 1] -= val;

Then, at the end, we do a prefix sum to get the final updated array.

---

Step-by-Step in C++

Step 1: Initialize Difference Array

First, build a diff array from the original arr:

vector<int> diff(n + 1, 0); // One extra space to handle r+1 safely

diff[0] = arr[0];
for (int i = 1; i < n; i++) {
    diff[i] = arr[i] - arr[i - 1];
}

Step 2: Apply Queries

For each query (l, r, val):

diff[l] += val;
diff[r + 1] -= val;

Step 3: Rebuild Final Array

Now, apply prefix sum to get the updated array:

vector<int> result(n);
result[0] = diff[0];

for (int i = 1; i < n; i++) {
    result[i] = result[i - 1] + diff[i];
}

---

Cpp Code for the Optimised Approach TC: O(N)

#include <iostream>
#include <vector>
using namespace std;

vector<int> applyQueries(vector<int>& arr, vector<tuple<int, int, int>>& queries) {
    int n = arr.size();
    vector<int> diff(n + 1, 0);

    // Step 1: Build initial difference array
    diff[0] = arr[0];
    for (int i = 1; i < n; i++) {
        diff[i] = arr[i] - arr[i - 1];
    }

    // Step 2: Apply queries
    for (auto& q : queries) {
        int l, r, val;
        tie(l, r, val) = q;
        diff[l] += val;
        if (r + 1 < n) diff[r + 1] -= val;
    }

    // Step 3: Compute final array using prefix sum
    vector<int> result(n);
    result[0] = diff[0];
    for (int i = 1; i < n; i++) {
        result[i] = result[i - 1] + diff[i];
    }

    return result;
}

int main() {
    vector<int> arr = {10, 20, 30, 40, 50};
    vector<tuple<int, int, int>> queries = {
        {1, 3, 5},
        {2, 4, 10}
    };

    vector<int> updated = applyQueries(arr, queries);

    cout << "Updated Array: ";
    for (int val : updated) {
        cout << val << " ";
    }

    return 0;
}

---

Output

Updated Array: 10 25 45 55 60

---