Two equal sum segment range queries | Function to find the required prefix Sum ; Function to hash all the values of prefix Sum array in an unordered map ; Function to check if a range can be divided into two equal parts ; To store the value of Sum of entire range ; If value of Sum is odd ; To store p_arr [ l - 1 ] ; If the value exists in the map ; Driver code ; prefix - Sum array ; Map to store the values of prefix - Sum ; Perform queries
def prefixSum ( p_arr , arr , n ) : NEW_LINE INDENT p_arr [ 0 ] = arr [ 0 ] NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT p_arr [ i ] = arr [ i ] + p_arr [ i - 1 ] NEW_LINE DEDENT DEDENT def hashPrefixSum ( p_arr , n , q ) : NEW_LINE INDENT for i in range ( n ) : NEW_LINE INDENT q [ p_arr [ i ] ] = 1 NEW_LINE DEDENT DEDENT def canDivide ( p_arr , n , q , l , r ) : NEW_LINE INDENT Sum = 0 NEW_LINE if ( l == 0 ) : NEW_LINE INDENT Sum = p_arr [ r ] NEW_LINE DEDENT else : NEW_LINE INDENT Sum = p_arr [ r ] - p_arr [ l - 1 ] NEW_LINE DEDENT if ( Sum % 2 == 1 ) : NEW_LINE INDENT print ( " No " ) NEW_LINE return NEW_LINE DEDENT beg = 0 NEW_LINE if ( l != 0 ) : NEW_LINE INDENT beg = p_arr [ l - 1 ] NEW_LINE DEDENT if ( beg + Sum // 2 in q . keys ( ) ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT DEDENT arr = [ 1 , 1 , 2 , 3 ] NEW_LINE n = len ( arr ) NEW_LINE p_arr = [ 0 for i in range ( n ) ] NEW_LINE prefixSum ( p_arr , arr , n ) NEW_LINE q = dict ( ) NEW_LINE hashPrefixSum ( p_arr , n , q ) NEW_LINE canDivide ( p_arr , n , q , 0 , 1 ) NEW_LINE canDivide ( p_arr , n , q , 1 , 3 ) NEW_LINE canDivide ( p_arr , n , q , 1 , 2 ) NEW_LINE