Constant time range add operation on an array | Utility method to add value val , to range [ lo , hi ] ; Utility method to get actual array from operation array ; convert array into prefix sum array ; method to print final updated array ; Driver Code ; Range add Queries
< ? php function add ( & $ arr , $ N , $ lo , $ hi , $ val ) { $ arr [ $ lo ] += $ val ; if ( $ hi != $ N - 1 ) $ arr [ $ hi + 1 ] -= $ val ; } function updateArray ( & $ arr , $ N ) { for ( $ i = 1 ; $ i < $ N ; $ i ++ ) $ arr [ $ i ] += $ arr [ $ i - 1 ] ; } function printArr ( & $ arr , $ N ) { updateArray ( $ arr , $ N ) ; for ( $ i = 0 ; $ i < $ N ; $ i ++ ) echo $ arr [ $ i ] . " ▁ " ; echo " STRNEWLINE " ; } $ N = 6 ; $ arr = array_fill ( 0 , $ N , NULL ) ; add ( $ arr , $ N , 0 , 2 , 100 ) ; add ( $ arr , $ N , 1 , 5 , 100 ) ; add ( $ arr , $ N , 2 , 3 , 100 ) ; printArr ( $ arr , $ N ) ; ? >