Queries to count sum of rows and columns of a Matrix present in given ranges | ''Python3 program for the above approach ; ''Function to preprocess the matrix to execute the queries ; '' Stores the sum of each row ; '' Stores the sum of each col ; '' Traverse the matrix and calculate  sum of each row and column ; '' Insert all row sums in sum_list ; '' Insert all column sums in sum_list ; '' Sort the array in ascending order ; '' Traverse the array queries[][] ; '' Search the leftmost index of L ; '' Search the rightmost index of R ; ''Function to search for the leftmost index of given number ; '' Initialize low, high and ans ; '' Stores mid ; '' If A[mid] >= num ; ''Function to search for the rightmost index of given number ; '' Initialise low, high and ans ; '' Stores mid ; '' If A[mid] <= num ; '' Update ans ; '' Update mid ; '' Update high ; ''Driver Code ; '' Given dimensions of matrix ; '' Given matrix ; '' Given number of queries ; '' Given queries ; '' Function call to count the  number row-sums and column-sums  present in the given ranges
from collections import deque NEW_LINE from bisect import bisect_left , bisect_right NEW_LINE def totalCount ( A , N , M , queries , Q ) : NEW_LINE INDENT row_sum = [ 0 ] * N NEW_LINE col_sum = [ 0 ] * M NEW_LINE for i in range ( N ) : NEW_LINE INDENT for j in range ( M ) : NEW_LINE INDENT row_sum [ i ] += A [ i ] [ j ] NEW_LINE col_sum [ j ] += A [ i ] [ j ] NEW_LINE DEDENT DEDENT sum_list = [ ] NEW_LINE for i in range ( N ) : NEW_LINE INDENT sum_list . append ( row_sum [ i ] ) NEW_LINE DEDENT for i in range ( M ) : NEW_LINE INDENT sum_list . append ( col_sum [ i ] ) NEW_LINE DEDENT sum_list = sorted ( sum_list ) NEW_LINE for i in range ( Q ) : NEW_LINE INDENT L = queries [ i ] [ 0 ] NEW_LINE R = queries [ i ] [ 1 ] NEW_LINE l = left_search ( sum_list , L ) NEW_LINE r = right_search ( sum_list , R ) NEW_LINE print ( r - l + 1 , end = " ▁ " ) NEW_LINE DEDENT DEDENT def left_search ( A , num ) : NEW_LINE INDENT low , high = 0 , len ( A ) - 1 NEW_LINE ans = 0 NEW_LINE while ( low <= high ) : NEW_LINE INDENT mid = low + ( high - low ) // 2 NEW_LINE if ( A [ mid ] >= num ) : NEW_LINE INDENT ans = mid NEW_LINE high = mid - 1 NEW_LINE DEDENT else : NEW_LINE INDENT low = mid + 1 NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT def right_search ( A , num ) : NEW_LINE INDENT low , high = 0 , len ( A ) - 1 NEW_LINE ans = high NEW_LINE while ( low <= high ) : NEW_LINE INDENT mid = low + ( high - low ) // 2 NEW_LINE if ( A [ mid ] <= num ) : NEW_LINE INDENT ans = mid NEW_LINE low = mid + 1 NEW_LINE DEDENT else : NEW_LINE INDENT high = mid - 1 NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N , M = 3 , 2 NEW_LINE A = [ [ 13 , 3 ] , [ 9 , 4 ] , [ 6 , 10 ] ] NEW_LINE Q = 2 NEW_LINE queries = [ [ 10 , 20 ] , [ 25 , 35 ] ] NEW_LINE totalCount ( A , N , M , queries , Q ) NEW_LINE DEDENT