Two equal sum segment range queries | C ++ implementation of the approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void prefixSum ( int * p_arr , int * arr , int n ) { p_arr [ 0 ] = arr [ 0 ] ; for ( int i = 1 ; i < n ; i ++ ) p_arr [ i ] = arr [ i ] + p_arr [ i - 1 ] ; } void hashPrefixSum ( int * p_arr , int n , unordered_set < int > & q ) { for ( int i = 0 ; i < n ; i ++ ) q . insert ( p_arr [ i ] ) ; } void canDivide ( int * p_arr , int n , unordered_set < int > & q , int l , int r ) { int sum ; if ( l == 0 ) sum = p_arr [ r ] ; else sum = p_arr [ r ] - p_arr [ l - 1 ] ; if ( sum % 2 == 1 ) { cout << " No " << endl ; return ; } int beg = 0 ; if ( l != 0 ) beg = p_arr [ l - 1 ] ; if ( q . find ( beg + sum / 2 ) != q . end ( ) ) cout << " Yes " << endl ; else cout << " No " << endl ; } int main ( ) { int arr [ ] = { 1 , 1 , 2 , 3 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int p_arr [ n ] ; prefixSum ( p_arr , arr , n ) ; unordered_set < int > q ; hashPrefixSum ( p_arr , n , q ) ; canDivide ( p_arr , n , q , 0 , 1 ) ; canDivide ( p_arr , n , q , 1 , 3 ) ; canDivide ( p_arr , n , q , 1 , 2 ) ; return 0 ; }