Prefix Sum Array and Range Sum Queries

Problem

Given an array, answer multiple range-sum queries efficiently using a prefix sum array.

Input:  nums = [2, 4, 6, 8, 10], query = sum(1, 3)
Output: 18   (4 + 6 + 8)

Python Solution

def build_prefix_sum(nums):
    prefix = [0] * (len(nums) + 1)
    for i, num in enumerate(nums):
        prefix[i + 1] = prefix[i] + num
    return prefix

def range_sum(prefix, left, right):
    return prefix[right + 1] - prefix[left]

C++ Solution

vector<int> buildPrefixSum(vector<int>& nums) {
    vector<int> prefix(nums.size() + 1, 0);
    for (int i = 0; i < nums.size(); i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
    return prefix;
}

int rangeSum(vector<int>& prefix, int left, int right) {
    return prefix[right + 1] - prefix[left];
}

Java Solution

class Solution {
    public int[] buildPrefixSum(int[] nums) {
        int[] prefix = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        return prefix;
    }

    public int rangeSum(int[] prefix, int left, int right) {
        return prefix[right + 1] - prefix[left];
    }
}

Complexity

Time: O(n) to build the prefix array once, then O(1) per range-sum query. Space: O(n) for the prefix array itself.