03-Range-Sum-Query.md

Range Sum Query

Problem Link

https://leetcode.com/problems/range-sum-query-immutable/

---

Pattern

• Prefix Sum

---

Approach

Precompute prefix sum array; query answer = prefix[right+1] - prefix[left].

---

Time Complexity

O(n) preprocessing, O(1) per query

Space Complexity

O(n)

---

Java Solution

class NumArray {
    private int[] prefix;
    public NumArray(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 sumRange(int left, int right) {
        return prefix[right+1] - prefix[left];
    }
}