[algogeeks] Re: Sum of sub array

[phoenixinter]

just read these array is O(n)
then precompute the partial-sum O(n)
sum from (i,j) takes O(1) time