Two Dimensional Difference Array | C ++ Program to implement the above approach ; Function to initialize the difference array ; Function to add k to the specified submatrix ( r1 , c1 ) to ( r2 , c2 ) ; Function to print the modified array ; Function to perform the given queries ; Difference array ; Function to initialize the difference array ; Count of queries ; Perform Queries ; Driver Code ; Given Matrix ; Given Queries
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define N  3 NEW_LINE #define M  3 NEW_LINE 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 ] ; } } 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 ; } } 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 ; } } void performQueries ( int A [ N ] [ M ] , vector < vector < int > > Queries ) { int D [ N ] [ M + 1 ] ; intializeDiff ( D , A ) ; int Q = Queries . size ( ) ; 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 ) ; } int main ( ) { int A [ N ] [ M ] = { { 1 , 2 , 3 } , { 1 , 1 , 0 } , { 4 , -2 , 2 } } ; vector < vector < int > > Queries = { { 2 , 0 , 0 , 1 , 1 } , { -1 , 1 , 0 , 2 , 2 } } ; performQueries ( A , Queries ) ; return 0 ; }