Difference Array | Range update query in O(1)

Given an array arr[] and a 2D array opr[][], where each row represents an operation in the form [l, r, v]. For each operation, add v to all elements from index l to r in arr. Return the updated array after applying all operations.

Examples : 

Input: arr[] = [2, 3, 5, 6, 7], opr[][] = [[2, 4, 2], [3, 4, -1]]
Output: [2, 3, 7, 7, 8]
Explanation: Operation [2, 4, 2]: Add 2 to elements at indices 2 to 4.
Updated array: [2, 3, 7, 8, 9]
Operation [3, 4, -1]: Subtract 1 from elements at indices 3 to 4.
Final array: [2, 3, 7, 7, 8]

Input: arr[] = [4, 5, 7, 9], opr[][] = [[1, 3, 1], [2, 3, -2]]
Ouput: [4, 6, 6, 8]
Explanation: After performing all the operations the final array look like [4, 6, 6, 8]

[Naive Approach] Using loops for each queries

For every operation (l, r, x), iterate from index l to r and add x to each element in that range. After all operations have been applied, traverse the array once to print the final result.

#include <iostream> #include <vector> using namespace std; // Function to apply a single operation:  // add x to elements from index l to r void update(vector<int> &arr, int l, int r, int x) {  for (int i = l; i <= r; i++) {  arr[i] += x;  } } // Function to apply all operations in order vector<int> diffArray(vector<int>& arr,  vector<vector<int>>& opr) {    // Apply each operation [l, r, v] to the array  // Here l , r are in 0 based indexing   for (auto &v : opr) {  update(arr, v[0], v[1], v[2]);  }  return arr; } int main() {    vector<int> arr = {2, 3, 5, 6, 7};  vector<vector<int>> opr = {  {2, 4, 2},   {3, 4, -1}   };  vector<int> res = diffArray(arr, opr);  for (int num : arr) {  cout << num << " ";  }  cout << endl;  return 0; } 

import java.util.ArrayList; import java.util.Arrays; class GfG {  // Function to apply a single operation:   // add x to elements from index l to r  static void update(int[] arr, int l, int r, int x) {  for (int i = l; i <= r; i++) {  arr[i] += x;  }  }  // Function to apply all operations in order  static ArrayList<Integer> diffArray(int[] arr, int[][] opr) {  for (int[] op : opr) {  update(arr, op[0], op[1], op[2]);  }  ArrayList<Integer> result = new ArrayList<>();  for (int num : arr) {  result.add(num);  }  return result;  }  public static void main(String[] args) {  int[] arr = {2, 3, 5, 6, 7};  int[][] opr = {  {2, 4, 2},  {3, 4, -1}  };  ArrayList<Integer> res = diffArray(arr, opr);  for (int num : res) {  System.out.print(num + " ");  }  System.out.println();  } } 

# Function to apply a single operation:  # add x to elements from index l to r def update(arr, l, r, x): for i in range(l, r + 1): arr[i] += x # Function to apply all operations in order def diffArray(arr, opr): # Apply each operation [l, r, v] to the array # Here l , r are in 0 based indexing  for v in opr: update(arr, v[0], v[1], v[2]) return arr if __name__ == "__main__": arr = [2, 3, 5, 6, 7] opr = [ [2, 4, 2], [3, 4, -1] ] res = diffArray(arr, opr) for num in arr: print(num, end=' ') print() 

using System; using System.Collections.Generic; class GfG {  // Function to apply a single operation:   // add x to elements from index l to r  static void update(int[] arr, int l, int r, int x) {  for (int i = l; i <= r; i++) {  arr[i] += x;  }  }  // Function to apply all operations and return List<int>  static List<int> diffArray(int[] arr, int[][] opr) {  foreach (int[] op in opr) {  update(arr, op[0], op[1], op[2]);  }  List<int> result = new List<int>(arr);  return result;  }  static void Main() {  int[] arr = {2, 3, 5, 6, 7};  int[][] opr = {  new int[] {2, 4, 2},  new int[] {3, 4, -1}  };  List<int> res = diffArray(arr, opr);  foreach (int num in res) {  Console.Write(num + " ");  }  Console.WriteLine();  } } 

// Function to apply a single operation:  // add x to elements from index l to r function update(arr, l, r, x) {  for (let i = l; i <= r; i++) {  arr[i] += x;  } } // Function to apply all operations in order function diffArray(arr, opr) {    // Apply each operation [l, r, v] to the array  // Here l , r are in 0 based indexing   for (let v of opr) {  update(arr, v[0], v[1], v[2]);  }    return arr; } // Driver Code let arr = [2, 3, 5, 6, 7]; let opr = [  [2, 4, 2],  [3, 4, -1] ]; let res = diffArray(arr, opr); console.log(arr.join(" ")); 

2 3 7 7 8 

Time Complexity: O(n × q), as each of the q operations may update up to n elements.
Auxiliary Space: O(1), since no extra space is used apart from a few variables.

[Better Approach] Using Difference Array

Instead of updating each element in the range for every operation, initialize a new array (same size as input) filled with zeros.

for each operation [l, r, v], do:

• diff[l] += v

• if (r + 1 < n) diff[r + 1] -= v

This marks the range updates in constant time.
Finally, compute the prefix sum of the diff[] array and add it to the original array to get the final result.

Why it works:

• Instead of updating every element between l and r for each operation (which can be slow), we just mark where the increase starts and where it ends.
• Imagine this like placing a +v flag at index l (start adding v), and a -v flag at index r + 1 (stop adding v after index r). You’re just saying: “Start adding v here, and stop adding v there.”
• After placing all these flags (from all operations), you take a prefix sum — going through the array from left to right and applying the net effect of all flags.
• This way, every element automatically receives all the right updates — without updating each one manually per operation.

#include <iostream> #include <vector> using namespace std; // Function to apply a single range update  // on the difference array void update(vector<int>& d, int l, int r, int x) {  // Adding v at index l   d[l] += x;  // Subtracting v at index r + 1 ensures the addition   // stops at index r when prefix sums are applied  d[r + 1] -= x; } // Function to initialize difference array, handle all  // queries, and apply prefix sum vector<int> diffArray(vector<int>& arr,   vector<vector<int>>& opr) {  int n = arr.size();  vector<int> d(n + 1, 0);  // Process each operation [l, r, v]  for (auto& query : opr) {  int l = query[0];  int r = query[1];  int v = query[2];  update(d, l, r, v);  }  // Apply prefix sum to get final result  for (int i = 0; i < n; i++) {  if (i > 0) d[i] += d[i - 1];  arr[i] += d[i];  }  return arr; } int main() {  vector<int> arr = {2, 3, 5, 6, 7};  vector<vector<int>> opr = {  {2, 4, 2},  {3, 4, -1}  };  vector<int> res = diffArray(arr, opr);  for (int i = 0; i < res.size(); i++) {  cout << res[i] << " ";  }  cout << endl;  return 0; } 

import java.util.ArrayList; import java.util.List; class GfG {  // Function to apply a single range update   // on the difference array  static void update(int[] d, int l, int r, int x) {  d[l] += x;  if (r + 1 < d.length) {  d[r + 1] -= x;  }  }  // Function to process operations   static ArrayList<Integer> diffArray(int[] arr, int[][] opr) {  int n = arr.length;  int[] d = new int[n + 1];  // Apply all operations to the difference array  for (int[] query : opr) {  int l = query[0];  int r = query[1];  int v = query[2];  update(d, l, r, v);  }  // Apply prefix sum and construct result  for (int i = 0; i < n; i++) {  if (i > 0) d[i] += d[i - 1];  arr[i] += d[i];  }  // Convert array to ArrayList and return  ArrayList<Integer> result = new ArrayList<>();  for (int num : arr) {  result.add(num);  }  return result;  }  public static void main(String[] args) {  int[] arr = {2, 3, 5, 6, 7};  int[][] opr = {  {2, 4, 2},  {3, 4, -1}  };  ArrayList<Integer> res = diffArray(arr, opr);  for (int num : res) {  System.out.print(num + " ");  }  System.out.println();  } } 

# Function to apply a single range update  # on the difference array def update(d, l, r, x): # Adding v at index l  d[l] += x # Subtracting v at index r + 1 ensures the addition  # stops at index r when prefix sums are applied if r + 1 < len(d): d[r + 1] -= x # Function to initialize difference array, handle  # all queries, and apply prefix sum def diffArray(arr, opr): n = len(arr) d = [0] * (n + 1) # Process each operation [l, r, v] for l, r, v in opr: update(d, l, r, v) # Apply prefix sum to get final result for i in range(n): if i > 0: d[i] += d[i - 1] arr[i] += d[i] return arr if __name__ == "__main__": arr = [2, 3, 5, 6, 7] opr = [ [2, 4, 2], [3, 4, -1] ] res = diffArray(arr, opr) for num in res: print(num, end=" ") print() 

using System; using System.Collections.Generic; class GfG {  // Function to apply a single range update   // on the difference array  static void update(int[] d, int l, int r, int x) {  d[l] += x;  if (r + 1 < d.Length) {  d[r + 1] -= x;  }  }  // Function to handle all queries  static List<int> diffArray(int[] arr, int[][] opr) {  int n = arr.Length;  int[] d = new int[n + 1];  // Apply all operations using difference array  foreach (var query in opr) {  int l = query[0];  int r = query[1];  int v = query[2];  update(d, l, r, v);  }  // Build the final array using prefix sum  for (int i = 0; i < n; i++) {  if (i > 0) d[i] += d[i - 1];  arr[i] += d[i];  }  // Convert array to List<int> and return  List<int> result = new List<int>();  foreach (int num in arr) {  result.Add(num);  }  return result;  }  static void Main() {  int[] arr = {2, 3, 5, 6, 7};  int[][] opr = new int[][] {  new int[] {2, 4, 2},  new int[] {3, 4, -1}  };  List<int> res = diffArray(arr, opr);  foreach (int num in res) {  Console.Write(num + " ");  }  Console.WriteLine();  } } 

// Function to apply a single range update on  // the difference array function update(d, l, r, x) {  // Adding v at index l   d[l] += x;  // Subtracting v at index r + 1 ensures the addition   // stops at index r when prefix sums are applied  if (r + 1 < d.length) {  d[r + 1] -= x;  } } // Function to initialize difference array, handle  // all queries, and apply prefix sum function diffArray(arr, opr) {  let n = arr.length;  let d = new Array(n + 1).fill(0);  // Process each operation [l, r, v]  for (let [l, r, v] of opr) {  update(d, l, r, v);  }  // Apply prefix sum to get final result  for (let i = 0; i < n; i++) {  if (i > 0) d[i] += d[i - 1];  arr[i] += d[i];  }  return arr; } // Driver code let arr = [2, 3, 5, 6, 7]; let opr = [  [2, 4, 2],  [3, 4, -1] ]; let res = diffArray(arr, opr); console.log(res.join(" ")); 

2 3 7 7 8 

Time Complexity: O(n + q), O(q) for updates and O(n) for prefix sum.
Auxiliary Space: O(n), for the difference array used to store range updates.

[Efficient Approach] In-Place Difference Array for Range Updates

The in-place difference array approach works by transforming the original array into a difference array, where each element represents the change from its previous element. This allows range updates to be applied in constant time by modifying just two positions — the start and end+1 of the range. Later, taking a prefix sum reconstructs the final updated array. This works because the prefix sum of a difference array always yields the original or updated values efficiently.

Step by step approach:

• Convert original array to difference form:
• Update each element from right to left as arr[i] = arr[i] - arr[i - 1] for i > 0. This transforms the array into its own difference array.
• Apply each operation [l, r, v]:
  • Do arr[l] += v to start adding v from index l.
  • Do arr[r + 1] -= v to stop adding v after index r (if r + 1 < n).
• Restore the final array by traversing the array from left to right, adding arr[i - 1] to arr[i] to compute the prefix sum and recover the final updated values.
• The modified array now holds the result after applying all range updates efficiently in-place.

#include <iostream> #include <vector> using namespace std; vector<int> diffArray(vector<int>& arr, vector<vector<int>>& opr) {  int n = arr.size();  // Convert arr to in-place difference array  for (int i = n - 1; i > 0; i--) {  arr[i] -= arr[i - 1];  }  // Apply each operation directly on the original array  // Each operation is of the form [l, r, v]  for (auto& q : opr) {  int l = q[0], r = q[1], v = q[2];  // Adding v at index l  arr[l] += v;  // Subtracting v at index r + 1 ensures the addition   // stops at index r when prefix sums are applied  if (r + 1 < n) arr[r + 1] -= v;  }  // Take prefix sum to get the final updated array  for (int i = 1; i < n; i++) {  arr[i] += arr[i - 1];  }  return arr; } int main() {  vector<int> arr = {2, 3, 5, 6, 7};  vector<vector<int>> opr = {  {2, 4, 2},  {3, 4, -1}  };  vector<int> res = diffArray(arr, opr);    for (int num : res) {  cout << num << " ";  }  cout << endl;  return 0; } 

import java.util.ArrayList; import java.util.List; class GfG {  public static ArrayList<Integer> diffArray(int[] arr, int[][] opr) {  int n = arr.length;  // Convert arr to in-place difference array  for (int i = n - 1; i > 0; i--) {  arr[i] -= arr[i - 1];  }  // Apply each operation [l, r, v]  for (int[] q : opr) {  int l = q[0], r = q[1], v = q[2];  arr[l] += v;  if (r + 1 < n) arr[r + 1] -= v;  }  // Take prefix sum to get final array  for (int i = 1; i < n; i++) {  arr[i] += arr[i - 1];  }  // Convert array to ArrayList  ArrayList<Integer> result = new ArrayList<>();  for (int num : arr) {  result.add(num);  }  return result;  }  public static void main(String[] args) {  int[] arr = {2, 3, 5, 6, 7};  int[][] opr = {  {2, 4, 2},  {3, 4, -1}  };  ArrayList<Integer> res = diffArray(arr, opr);  for (int num : res) {  System.out.print(num + " ");  }  System.out.println();  } } 

def diffArray(arr, opr): n = len(arr) # Convert arr to in-place difference array for i in range(n - 1, 0, -1): arr[i] -= arr[i - 1] # Apply each operation directly on the original array # Each operation is of the form [l, r, v] for l, r, v in opr: # Adding v at index l arr[l] += v # Subtracting v at index r + 1 ensures the addition  # stops at index r when prefix sums are applied if r + 1 < n: arr[r + 1] -= v # Take prefix sum to get the final updated array for i in range(1, n): arr[i] += arr[i - 1] return arr if __name__ == "__main__": arr = [2, 3, 5, 6, 7] opr = [ [2, 4, 2], [3, 4, -1] ] res = diffArray(arr, opr) print(*res) 

using System; using System.Collections.Generic; class GfG {  public static List<int> diffArray(int[] arr, int[][] opr) {  int n = arr.Length;  // Convert arr to in-place difference array  for (int i = n - 1; i > 0; i--) {  arr[i] -= arr[i - 1];  }  // Apply each operation [l, r, v]  foreach (var q in opr) {  int l = q[0], r = q[1], v = q[2];  arr[l] += v;  if (r + 1 < n) arr[r + 1] -= v;  }  // Take prefix sum to restore the final array  for (int i = 1; i < n; i++) {  arr[i] += arr[i - 1];  }  // Convert array to List<int>  List<int> result = new List<int>();  foreach (int num in arr) {  result.Add(num);  }  return result;  }  // Driver code  public static void Main() {  int[] arr = {2, 3, 5, 6, 7};  int[][] opr = {  new int[] {2, 4, 2},  new int[] {3, 4, -1}  };  List<int> res = diffArray(arr, opr);  foreach (int num in res) {  Console.Write(num + " ");  }  Console.WriteLine();  } } 

function diffArray(arr, opr) {  let n = arr.length;  // Convert arr to in-place difference array  for (let i = n - 1; i > 0; i--) {  arr[i] -= arr[i - 1];  }  // Apply each operation directly on the original array  // Each operation is of the form [l, r, v]  for (let [l, r, v] of opr) {  // Adding v at index l  arr[l] += v;  // Subtracting v at index r + 1 ensures the addition   // stops at index r when prefix sums are applied  if (r + 1 < n) {  arr[r + 1] -= v;  }  }  // Take prefix sum to get the final updated array  for (let i = 1; i < n; i++) {  arr[i] += arr[i - 1];  }  return arr; } // Driver code let arr = [2, 3, 5, 6, 7]; let opr = [  [2, 4, 2],  [3, 4, -1] ]; let res = diffArray(arr, opr); console.log(res.join(" ")); 

2 3 7 7 8 

Time Complexity: O(n + q), O(q) for updates and O(n) for prefix sum.
Auxiliary Space: O(1), since no extra space is used apart from a few variables.