function to make prefix sums array
void MakePreSum ( int arr [ ] , int presum [ ] , int n ) { presum [ 0 ] = arr [ 0 ] ; for ( int i = 1 ; i < n ; i ++ ) presum [ i ] = presum [ i - 1 ] + arr [ i ] ; }