Two Dimensional Difference Array

Last Updated : 23 Jun, 2022

Given a matrix of dimensions N * M and a 2D array Queries[][] with each query of the form {k, r1, c1, r2, c2}, the task is to add k to all the cells present in the submatrix (r1, c1) to (r2, c2)

Examples:

Input: A[][] = {{1, 2, 3}, {1, 1, 0}, {4, -2, 2}}, Queries[][] = {{2, 0, 0, 1, 1}, {-1, 1, 0, 2, 2}}
Output:
3 4 3
2 2 -1
3 -3 1
Explanation:
Query 1: Matrix modifies to {{3, 4, 3}, {3, 3, 0}, {4, -2, 2}
Query 2: Matrix modifies to {{3, 4, 3}, {2, 2, -1}, {3, -3, 1}

Input: A[][] = {{1, 2, 3}, { 4, 5, 6}, {7, 8, 9}}, Queries[][] = {{1, 1, 1, 2, 2}, {2, 0, 1, 0, 2}}
Output:
1 4 5
4 6 7
7 9 10

Approach: The idea is based on Difference Array | Range update query in O(1). Follow the steps below to solve the problem:

Initialize a 2D difference array D[][], such that D[i][j] stores A[i][j] – A[i][j – 1] (for 0 ? i ? N and 0 < j < M) or D[i][j] = A[i][j] otherwise.
Traverse each row and compute and store the difference between adjacent elements.
To update the submatrix (r1, c1) to (r2, c2), traverse from r1 to r2 (assuming r1 < r2 and c1 < c2) and update D[i][c1] = D[i][c1] + k and D[i][c2 + 1] = D[i][c2 + 1] – k.
Finally, print the modified array as D[i][j] + A[i][j-1] for j > 0 or D[i][j] for j = 0.

Below is the implementation of the above approach:

C++

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
#define N 3
#define M 3
 
// Function to initialize the difference array
void intializeDiff(int D[N][M + 1],
                   int A[N][M])
{
    for (int i = 0; i < N; i++) {
        D[i][0] = A[i][0];
        D[i][M] = 0;
    }
    for (int i = 0; i < N; i++) {
        for (int j = 1; j < M; j++)
            D[i][j] = A[i][j] - A[i][j - 1];
    }
}
 
// Function to add k to the specified
// submatrix (r1, c1) to (r2, c2)
void update(int D[N][M + 1], int k,
            int r1, int c1, int r2,
            int c2)
{
    for (int i = r1; i <= r2; i++) {
        D[i][c1] += k;
        D[i][c2 + 1] -= k;
    }
}
 
// Function to print the modified array
void printArray(int A[N][M], int D[N][M + 1])
{
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (j == 0)
                A[i][j] = D[i][j];
            else
                A[i][j] = D[i][j] + A[i][j - 1];
            cout << A[i][j] << " ";
        }
        cout << endl;
    }
}
 
// Function to perform the given queries
void performQueries(int A[N][M],
                    vector<vector<int> > Queries)
{
    // Difference array
    int D[N][M + 1];
 
    // Function to initialize
    // the difference array
    intializeDiff(D, A);
 
    // Count of queries
    int Q = Queries.size();
 
    // Perform Queries
    for (int i = 0; i < Q; i++) {
        update(D, Queries[i][0],
               Queries[i][1], Queries[i][2],
               Queries[i][3], Queries[i][4]);
    }
 
    printArray(A, D);
}
 
// Driver Code
int main()
{
 
    // Given Matrix
    int A[N][M] = { { 1, 2, 3 },
                    { 1, 1, 0 },
                    { 4, -2, 2 } };
 
    // Given Queries
    vector<vector<int> > Queries
        = { { 2, 0, 0, 1, 1 },
            { -1, 1, 0, 2, 2 } };
 
    performQueries(A, Queries);
 
    return 0;
}

Java

// Java program to implement 
// the above approach 
import java.util.*;
 
class GFG{
     
static int N = 3; 
static int M = 3;
  
// Function to initialize the difference array 
static void intializeDiff(int D[][], int A[][]) 
{ 
    for(int i = 0; i < N; i++)
    {
        D[i][0] = A[i][0]; 
        D[i][M] = 0; 
    } 
    for(int i = 0; i < N; i++)
    {
        for(int j = 1; j < M; j++) 
            D[i][j] = A[i][j] - A[i][j - 1]; 
    } 
} 
    
// Function to add k to the specified 
// submatrix (r1, c1) to (r2, c2) 
static void update(int D[][], int k, 
                   int r1, int c1, 
                   int r2, int c2) 
{ 
    for(int i = r1; i <= r2; i++) 
    {
        D[i][c1] += k; 
        D[i][c2 + 1] -= k; 
    } 
} 
    
// Function to print the modified array 
static void printArray(int A[][], int D[][]) 
{ 
    for(int i = 0; i < N; i++)
    { 
        for(int j = 0; j < M; j++) 
        {
            if (j == 0) 
                A[i][j] = D[i][j]; 
            else
                A[i][j] = D[i][j] + A[i][j - 1]; 
                  
            System.out.print(A[i][j] + " "); 
        } 
        System.out.println(); 
    } 
} 
    
// Function to perform the given queries 
static void performQueries(int A[][],
                           Vector<Vector<Integer>> Queries) 
{ 
     
    // Difference array 
    int D[][] = new int[N][M + 1]; 
    
    // Function to initialize 
    // the difference array 
    intializeDiff(D, A); 
    
    // Count of queries 
    int Q = Queries.size(); 
    
    // Perform Queries 
    for(int i = 0; i < Q; i++)
    {
        update(D, Queries.get(i).get(0), 
                  Queries.get(i).get(1),
                  Queries.get(i).get(2), 
                  Queries.get(i).get(3),
                  Queries.get(i).get(4)); 
    } 
    printArray(A, D); 
} 
 
// Driver Code
public static void main(String[] args)
{
     
    // Given Matrix 
    int A[][] = { { 1, 2, 3 }, 
                  { 1, 1, 0 }, 
                  { 4, -2, 2 } }; 
      
    // Given Queries 
    Vector<Vector<Integer>> Queries = new Vector<Vector<Integer>>();
    Vector<Integer> list1 = new Vector<Integer>();
    list1.add(2);
    list1.add(0);
    list1.add(0);
    list1.add(1);
    list1.add(1);
     
    Vector<Integer> list2 = new Vector<Integer>();
    list2.add(-1);
    list2.add(1);
    list2.add(0);
    list2.add(2);
    list2.add(2);
     
    Queries.add(list1);
    Queries.add(list2);
      
    performQueries(A, Queries);
}
}
 
// This code is contributed by divyeshrabadiya07

Python3

# Python3 Program to implement
# the above approach 
N = 3
M = 3
  
# Function to initialize the difference array
def intializeDiff(D, A): 
    for i in range(N):        
        D[i][0] = A[i][0];
        D[i][M] = 0;   
    for i in range(N):
        for j in range(1, M):
            D[i][j] = A[i][j] - A[i][j - 1];
      
# Function to add k to the specified
# submatrix (r1, c1) to (r2, c2)
def update(D, k, r1, c1, r2, c2):
    for i in range(r1, r2 + 1):
        D[i][c1] += k;
        D[i][c2 + 1] -= k;
 
# Function to print the modified array
def printArray(A, D):   
    for i in range(N):
        for j in range(M):   
            if (j == 0):
                A[i][j] = D[i][j];
            else:
                A[i][j] = D[i][j] + A[i][j - 1];                
            print(A[i][j], end = ' ')
        print()
         
# Function to perform the given queries
def performQueries(A, Queries):
 
    # Difference array
    D = [[0 for j in range(M + 1)] for i in range(N)]
  
    # Function to initialize
    # the difference array
    intializeDiff(D, A);
  
    # Count of queries
    Q = len(Queries)
  
    # Perform Queries
    for i in range(Q):    
        update(D, Queries[i][0],
               Queries[i][1], Queries[i][2],
               Queries[i][3], Queries[i][4]);
      
    printArray(A, D);
  
# Driver Code
if __name__=='__main__':
  
    # Given Matrix
    A = [ [ 1, 2, 3 ],
                    [ 1, 1, 0 ],
                    [ 4, -2, 2 ] ];
  
    # Given Queries
    Queries = [ [ 2, 0, 0, 1, 1 ],[ -1, 1, 0, 2, 2 ] ];
  
    performQueries(A, Queries);
 
  # This code is contributed by Pratham76

C#

// C# program to implement 
// the above approach 
using System;
using System.Collections.Generic;
 
class GFG{
     
static int N = 3; 
static int M = 3;
 
// Function to initialize the difference array 
static void intializeDiff(int[,] D, int[,] A) 
{ 
    for(int i = 0; i < N; i++)
    {
        D[i, 0] = A[i, 0]; 
        D[i, M] = 0; 
    } 
    for(int i = 0; i < N; i++)
    {
        for(int j = 1; j < M; j++) 
            D[i, j] = A[i, j] - A[i, j - 1]; 
    } 
} 
   
// Function to add k to the specified 
// submatrix (r1, c1) to (r2, c2) 
static void update(int[,] D, int k, 
                   int r1, int c1, 
                   int r2, int c2) 
{ 
    for(int i = r1; i <= r2; i++) 
    {
        D[i, c1] += k; 
        D[i, c2 + 1] -= k; 
    } 
} 
   
// Function to print the modified array 
static void printArray(int[,] A, int[,] D) 
{ 
    for(int i = 0; i < N; i++)
    { 
        for(int j = 0; j < M; j++) 
        {
            if (j == 0) 
                A[i, j] = D[i, j]; 
            else
                A[i, j] = D[i, j] + A[i, j - 1]; 
                 
            Console.Write(A[i, j] + " "); 
        } 
        Console.WriteLine(); 
    } 
} 
   
// Function to perform the given queries 
static void performQueries(int[,] A, 
                 List<List<int>> Queries) 
{ 
     
    // Difference array 
    int[,] D = new int[N, M + 1]; 
   
    // Function to initialize 
    // the difference array 
    intializeDiff(D, A); 
   
    // Count of queries 
    int Q = Queries.Count; 
   
    // Perform Queries 
    for(int i = 0; i < Q; i++)
    {
        update(D, Queries[i][0], 
                  Queries[i][1], Queries[i][2], 
                  Queries[i][3], Queries[i][4]); 
    } 
    printArray(A, D); 
} 
 
// Driver Code
static void Main() 
{
     
    // Given Matrix 
    int[,] A = { { 1, 2, 3 }, 
                 { 1, 1, 0 }, 
                 { 4, -2, 2 } }; 
     
    // Given Queries 
    List<List<int>> Queries = new List<List<int>>();
    Queries.Add(new List<int>{ 2, 0, 0, 1, 1 });
    Queries.Add(new List<int>{ -1, 1, 0, 2, 2 });
     
    performQueries(A, Queries); 
}
}
 
// This code is contributed by divyesh072019

Javascript

<script>
 
 
// JavaScript Program to implement
// the above approach
var N = 3;
var M = 3;
 
// Function to initialize the difference array
function intializeDiff(D,
                    A)
{
    for (var i = 0; i < N; i++) {
        D[i][0] = A[i][0];
        D[i][M] = 0;
    }
    for (var i = 0; i < N; i++) {
        for (var j = 1; j < M; j++)
            D[i][j] = A[i][j] - A[i][j - 1];
    }
}
 
// Function to add k to the specified
// submatrix (r1, c1) to (r2, c2)
function update( D,  k, r1, c1, r2, c2)
{
    for (var i = r1; i <= r2; i++) {
        D[i][c1] += k;
        D[i][c2 + 1] -= k;
    }
}
 
// Function to print the modified array
function printArray(A, D)
{
  var str = "";
    for (var i = 0; i < N; i++) {
        for (var j = 0; j < M; j++) {
            if (j == 0)
                A[i][j] = D[i][j];
            else
                A[i][j] = D[i][j] + A[i][j - 1];
                 
            str += A[i][j] + " ";
             
        }
        console.log(str );
        str="";
    }
}
 
// Function to perform the given queries
function performQueries( A,
                     Queries)
{
    // Difference array
    var D = new Array(N);
    for (var i =0 ; i< N;i++)
      D[i] = new Array(M + 1);
 
    // Function to initialize
    // the difference array
    intializeDiff(D, A);
 
    // Count of queries
    var Q = Queries.length;
 
    // Perform Queries
    for (var i = 0; i < Q; i++) {
        update(D, Queries[i][0],
               Queries[i][1], Queries[i][2],
               Queries[i][3], Queries[i][4]);
    }
 
    printArray(A, D);
}
 
// Driver Code
 
// Given Matrix
var A = [[ 1, 2, 3 ],
                [ 1, 1, 0 ],
                [ 4, -2, 2 ]];
 
// Given Queries
var Queries
    = [[ 2, 0, 0, 1, 1 ],
        [ -1, 1, 0, 2, 2 ]];
 
performQueries(A, Queries);
 
// This code is contributed by ukasp.    
 
</script>