Fills pre [ ]
< ? php function precompute ( & $ arr , $ n , & $ pre ) { $ pre [ $ n - 1 ] = $ arr [ $ n - 1 ] * pow ( 2 , 0 ) ; for ( $ i = $ n - 2 ; $ i >= 0 ; $ i -- ) $ pre [ $ i ] = $ pre [ $ i + 1 ] + $ arr [ $ i ] * ( 1 << ( $ n - 1 - $ i ) ) ; }