14-Prefix-Sum-Query.md

Prefix Sum Query

Problem Link

(Variant: prefix sum based query)

---

Pattern

• Prefix Sum

---

Approach

Precompute prefix sum; queries answered using prefix[right] - prefix[left-1].

---

Time Complexity

O(n) preprocessing

Space Complexity

O(n)

---

Java Solution

class PrefixSumQuery {
    private int[] prefix;
    public PrefixSumQuery(int[] nums) {
        prefix = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            prefix[i+1] = prefix[i] + nums[i];
        }
    }
    public int query(int left, int right) {
        return prefix[right+1] - prefix[left];
    }
}