Fills pre [ ]
void precompute ( int arr [ ] , int n , int pre [ ] ) { memset ( pre , 0 , n * sizeof ( int ) ) ; pre [ n - 1 ] = arr [ n - 1 ] * pow ( 2 , 0 ) ; for ( int i = n - 2 ; i >= 0 ; i -- ) pre [ i ] = pre [ i + 1 ] + arr [ i ] * ( 1 << ( n - 1 - i ) ) ; }