Range Sum - Implementation

Here's the full solution:

class NumArray
    prefix := empty array

    function init(nums)
        n := length of nums
        prefix := array of size (n + 1)
        prefix[0] := 0
        for i from 0 to n - 1
            prefix[i + 1] := prefix[i] + nums[i]

    function sumRange(left, right)
        return prefix[right + 1] - prefix[left]

Initialization: $O(n)$ time, $O(n)$ space. Each query: $O(1)$ time.