Submatrix Sum Queries | Function to preprcess input mat [ M ] [ N ] . This function mainly fills aux [ M ] [ N ] such that aux [ i ] [ j ] stores sum of elements from ( 0 , 0 ) to ( i , j ) ; Copy first row of mat [ ] [ ] to aux [ ] [ ] ; Do column wise sum ; Do row wise sum ; A O ( 1 ) time function to compute sum of submatrix between ( tli , tlj ) and ( rbi , rbj ) using aux [ ] [ ] which is built by the preprocess function ; result is now sum of elements between ( 0 , 0 ) and ( rbi , rbj ) ; Remove elements between ( 0 , 0 ) and ( tli - 1 , rbj ) ; Remove elements between ( 0 , 0 ) and ( rbi , tlj - 1 ) ; Add aux [ tli - 1 ] [ tlj - 1 ] as elements between ( 0 , 0 ) and ( tli - 1 , tlj - 1 ) are subtracted twice ; Driver Code
< ? php function preProcess ( & $ mat , & $ aux ) { $ M = 4 ; $ N = 5 ; for ( $ i = 0 ; $ i < $ N ; $ i ++ ) $ aux [ 0 ] [ $ i ] = $ mat [ 0 ] [ $ i ] ; for ( $ i = 1 ; $ i < $ M ; $ i ++ ) for ( $ j = 0 ; $ j < $ N ; $ j ++ ) $ aux [ $ i ] [ $ j ] = $ mat [ $ i ] [ $ j ] + $ aux [ $ i - 1 ] [ $ j ] ; for ( $ i = 0 ; $ i < $ M ; $ i ++ ) for ( $ j = 1 ; $ j < $ N ; $ j ++ ) $ aux [ $ i ] [ $ j ] += $ aux [ $ i ] [ $ j - 1 ] ; } function sumQuery ( & $ aux , $ tli , $ tlj , $ rbi , $ rbj ) { $ res = $ aux [ $ rbi ] [ $ rbj ] ; if ( $ tli > 0 ) $ res = $ res - $ aux [ $ tli - 1 ] [ $ rbj ] ; if ( $ tlj > 0 ) $ res = $ res - $ aux [ $ rbi ] [ $ tlj - 1 ] ; if ( $ tli > 0 && $ tlj > 0 ) $ res = $ res + $ aux [ $ tli - 1 ] [ $ tlj - 1 ] ; return $ res ; } $ mat = array ( array ( 1 , 2 , 3 , 4 , 6 ) , array ( 5 , 3 , 8 , 1 , 2 ) , array ( 4 , 6 , 7 , 5 , 5 ) , array ( 2 , 4 , 8 , 9 , 4 ) ) ; preProcess ( $ mat , $ aux ) ; $ tli = 2 ; $ tlj = 2 ; $ rbi = 3 ; $ rbj = 4 ; echo ( " Query1 : ▁ " ) ; echo ( sumQuery ( $ aux , $ tli , $ tlj , $ rbi , $ rbj ) ) ; $ tli = 0 ; $ tlj = 0 ; $ rbi = 1 ; $ rbj = 1 ; echo ( " Query2 : " echo ( sumQuery ( $ aux , $ tli , $ tlj , $ rbi , $ rbj ) ) ; $ tli = 1 ; $ tlj = 2 ; $ rbi = 3 ; $ rbj = 3 ; echo ( " Query3 : " echo ( sumQuery ( $ aux , $ tli , $ tlj , $ rbi , $ rbj ) ) ; ? >