46. Range Sum Query - Immutable

🔗 LeetCode Problem: 303. Range Sum Query - Immutable
📊 Difficulty: Easy
🏷️ Topics: Array, Design, Prefix Sum

Problem Statement

Given an integer array nums, handle multiple queries of the following type:

Calculate the sum of the elements of nums between indices left and right inclusive where left <= right.

Implement the NumArray class:

NumArray(int[] nums) Initializes the object with the integer array nums.
int sumRange(int left, int right) Returns the sum of the elements of nums between indices left and right inclusive (i.e., nums[left] + nums[left + 1] + ... + nums[right]).

Example 1:

Input
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
Output
[null, 1, -1, -3]

Explanation
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return (-2) + 0 + 3 = 1
numArray.sumRange(2, 5); // return 3 + (-5) + 2 + (-1) = -1
numArray.sumRange(0, 5); // return (-2) + 0 + 3 + (-5) + 2 + (-1) = -3

Constraints: - 1 <= nums.length <= 10^4 - -10^5 <= nums[i] <= 10^5 - 0 <= left <= right < nums.length - At most 10^4 calls will be made to sumRange.

🎨 Visual Understanding

The Problem Visualized

nums = [-2, 0, 3, -5, 2, -1]
Index:  0   1  2   3  4   5

Query 1: sumRange(0, 2)
  nums[0] + nums[1] + nums[2]
  = -2 + 0 + 3 = 1

Query 2: sumRange(2, 5)
  nums[2] + nums[3] + nums[4] + nums[5]
  = 3 + (-5) + 2 + (-1) = -1

Query 3: sumRange(0, 5)
  nums[0] + nums[1] + nums[2] + nums[3] + nums[4] + nums[5]
  = -2 + 0 + 3 + (-5) + 2 + (-1) = -3

Key Observation: Multiple Queries = Need Preprocessing

Challenge:
- Multiple sumRange queries (up to 10^4)
- If we calculate sum each time: O(n) per query
- Total: O(q × n) where q = number of queries
- Can we do better?

Solution: PRECOMPUTE!
- Build prefix sum array during initialization
- Each query becomes O(1)
- Total: O(n) preprocessing + O(1) per query

What is Prefix Sum?

Prefix sum at index i = sum of all elements from 0 to i

nums     = [-2,  0,  3, -5,  2, -1]
Index:      0   1   2   3   4   5

prefixSum[0] = -2                           = -2
prefixSum[1] = -2 + 0                       = -2
prefixSum[2] = -2 + 0 + 3                   = 1
prefixSum[3] = -2 + 0 + 3 + (-5)            = -4
prefixSum[4] = -2 + 0 + 3 + (-5) + 2        = -2
prefixSum[5] = -2 + 0 + 3 + (-5) + 2 + (-1) = -3

prefixSum = [-2, -2, 1, -4, -2, -3]

Formula: prefixSum[i] = prefixSum[i-1] + nums[i]

The Magic Formula: Range Sum Using Prefix Sum

Sum of range [left, right] = prefixSum[right] - prefixSum[left - 1]

Visual proof:
nums     = [-2,  0,  3, -5,  2, -1]
Index:      0   1   2   3   4   5
prefixSum = [-2, -2, 1, -4, -2, -3]

Query: sumRange(2, 5) = sum of [3, -5, 2, -1]

prefixSum[5] = sum from 0 to 5 = -2 + 0 + 3 + (-5) + 2 + (-1) = -3
prefixSum[1] = sum from 0 to 1 = -2 + 0 = -2

prefixSum[5] - prefixSum[1] = -3 - (-2) = -1 ✓

This is: (sum 0 to 5) - (sum 0 to 1) = sum 2 to 5

Visual:
[-----sum 0 to 5-----]
[sum 0 to 1][sum 2 to 5]

Remove left part → get middle part!

🎯 Approach 1: Brute Force (No Preprocessing)

The Most Natural Thinking 💭

Core Logic:

For each query:
1. Loop from left to right
2. Add all elements
3. Return sum

Simple but inefficient for multiple queries

Implementation

class NumArray {
    private int[] nums;

    public NumArray(int[] nums) {
        this.nums = nums;
    }

    public int sumRange(int left, int right) {
        int sum = 0;
        for (int i = left; i <= right; i++) {
            sum += nums[i];
        }
        return sum;
    }
}

⏰ Time: - Constructor: O(1) - sumRange: O(n) per query - Total for q queries: O(q × n)

💾 Space: O(1) - only store original array

✅ Approach 2: Prefix Sum (Optimal)

The Breakthrough Insight 💡

Core Logic:

Precompute prefix sums during initialization:
prefixSum[i] = sum of nums[0] to nums[i]

For range sum query [left, right]:
- If left = 0: return prefixSum[right]
- Otherwise: return prefixSum[right] - prefixSum[left - 1]

This removes the left part from the total sum!

Visual Explanation:

nums     = [-2,  0,  3, -5,  2, -1]
prefixSum = [-2, -2,  1, -4, -2, -3]

Query: sumRange(2, 5)

Option 1: Add directly
  nums[2] + nums[3] + nums[4] + nums[5]
  = 3 + (-5) + 2 + (-1) = -1

Option 2: Use prefix sum
  prefixSum[5] - prefixSum[1]
  = -3 - (-2) = -1 ✓

Same answer, but O(1) instead of O(4)!

Why This Works:

prefixSum[right] = nums[0] + nums[1] + ... + nums[right]
prefixSum[left-1] = nums[0] + nums[1] + ... + nums[left-1]

Subtract:
prefixSum[right] - prefixSum[left-1]
= (nums[0] + ... + nums[left-1] + nums[left] + ... + nums[right])
  - (nums[0] + ... + nums[left-1])
= nums[left] + nums[left+1] + ... + nums[right]

Exactly what we want!

Implementation (Standard)

class NumArray {
    private int[] prefixSum;

    public NumArray(int[] nums) {
        int n = nums.length;
        prefixSum = new int[n];

        // Build prefix sum array
        prefixSum[0] = nums[0];
        for (int i = 1; i < n; i++) {
            prefixSum[i] = prefixSum[i - 1] + nums[i];
        }
    }

    public int sumRange(int left, int right) {
        if (left == 0) {
            return prefixSum[right];
        }
        return prefixSum[right] - prefixSum[left - 1];
    }
}

⏰ Time: - Constructor: O(n) - build prefix sum array - sumRange: O(1) per query - Total for q queries: O(n + q)

💾 Space: O(n) - for prefix sum array

Implementation (Alternative: Padding with 0)

class NumArray {
    private int[] prefixSum;

    public NumArray(int[] nums) {
        int n = nums.length;
        // Extra space at index 0 to avoid edge case
        prefixSum = new int[n + 1];

        // prefixSum[0] = 0
        // prefixSum[i] = sum of nums[0] to nums[i-1]
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }
    }

    public int sumRange(int left, int right) {
        // No need to check left == 0
        return prefixSum[right + 1] - prefixSum[left];
    }
}

Why Padding?

Avoids special case for left = 0

Standard version:
if (left == 0) return prefixSum[right];
else return prefixSum[right] - prefixSum[left - 1];

Padded version:
return prefixSum[right + 1] - prefixSum[left];  // Always works!

Trade-off:
+ Simpler query code (no if statement)
+ No edge case handling
- Extra space for one element
- Index offset (can be confusing)

⏰ Time: - Constructor: O(n) - sumRange: O(1)

💾 Space: O(n + 1) = O(n)

🔍 Step-by-Step Execution

Example: nums = [-2, 0, 3, -5, 2, -1]

═══════════════════════════════════════════════════════════════════
INITIALIZATION (Constructor)
═══════════════════════════════════════════════════════════════════

nums = [-2, 0, 3, -5, 2, -1]

Building prefixSum array:

i = 0: prefixSum[0] = nums[0] = -2
i = 1: prefixSum[1] = prefixSum[0] + nums[1] = -2 + 0 = -2
i = 2: prefixSum[2] = prefixSum[1] + nums[2] = -2 + 3 = 1
i = 3: prefixSum[3] = prefixSum[2] + nums[3] = 1 + (-5) = -4
i = 4: prefixSum[4] = prefixSum[3] + nums[4] = -4 + 2 = -2
i = 5: prefixSum[5] = prefixSum[4] + nums[5] = -2 + (-1) = -3

Result:
nums      = [-2,  0,  3, -5,  2, -1]
Index:       0   1   2   3   4   5
prefixSum = [-2, -2,  1, -4, -2, -3]


═══════════════════════════════════════════════════════════════════
QUERY 1: sumRange(0, 2)
═══════════════════════════════════════════════════════════════════

left = 0, right = 2

Since left == 0:
  return prefixSum[2] = 1

Verification:
  nums[0] + nums[1] + nums[2]
  = -2 + 0 + 3 = 1 ✓


═══════════════════════════════════════════════════════════════════
QUERY 2: sumRange(2, 5)
═══════════════════════════════════════════════════════════════════

left = 2, right = 5

Since left != 0:
  return prefixSum[5] - prefixSum[1]
  = -3 - (-2)
  = -3 + 2
  = -1

Visualization:
  prefixSum[5] = sum from index 0 to 5
               = -2 + 0 + 3 + (-5) + 2 + (-1) = -3

  prefixSum[1] = sum from index 0 to 1
               = -2 + 0 = -2

  Difference = sum from index 2 to 5
             = 3 + (-5) + 2 + (-1) = -1 ✓

Visual diagram:
  [0    1][2    3    4    5]
  [-2   0][3  (-5)  2  (-1)]
   sum=-2   sum=-1

  Total sum (0 to 5) = -2 + (-1) = -3
  Remove (0 to 1)    = -2
  Get (2 to 5)       = -1 ✓


═══════════════════════════════════════════════════════════════════
QUERY 3: sumRange(0, 5)
═══════════════════════════════════════════════════════════════════

left = 0, right = 5

Since left == 0:
  return prefixSum[5] = -3

Verification:
  nums[0] + nums[1] + nums[2] + nums[3] + nums[4] + nums[5]
  = -2 + 0 + 3 + (-5) + 2 + (-1) = -3 ✓


═══════════════════════════════════════════════════════════════════
SUMMARY
═══════════════════════════════════════════════════════════════════

Query 1: sumRange(0, 2) = 1
Query 2: sumRange(2, 5) = -1
Query 3: sumRange(0, 5) = -3

Each query took O(1) time!

🔍 Edge Cases

Case 1: Single element array
Input: nums = [5], sumRange(0, 0)
Output: 5
prefixSum = [5]

Case 2: All positive numbers
Input: nums = [1, 2, 3, 4], sumRange(1, 3)
Output: 9
prefixSum = [1, 3, 6, 10]
Result: 10 - 1 = 9

Case 3: All negative numbers
Input: nums = [-1, -2, -3], sumRange(0, 2)
Output: -6
prefixSum = [-1, -3, -6]

Case 4: Query entire array
Input: nums = [1, 2, 3], sumRange(0, 2)
Output: 6
prefixSum = [1, 3, 6]

Case 5: Query single element
Input: nums = [1, 2, 3], sumRange(1, 1)
Output: 2
prefixSum = [1, 3, 6]
Result: 3 - 1 = 2

Case 6: Zeros in array
Input: nums = [0, 0, 0], sumRange(0, 2)
Output: 0
prefixSum = [0, 0, 0]

Case 7: Mixed positive and negative
Input: nums = [5, -3, 2, -1], sumRange(1, 2)
Output: -1
prefixSum = [5, 2, 4, 3]
Result: 4 - 5 = -1

Common Mistakes

Mistake 1: Not handling left = 0 case
❌ Wrong: 
    return prefixSum[right] - prefixSum[left - 1];
    // Index out of bounds when left = 0
✓ Right: 
    if (left == 0) return prefixSum[right];
    return prefixSum[right] - prefixSum[left - 1];
Reason: prefixSum[-1] doesn't exist

Mistake 2: Using wrong prefix sum formula
❌ Wrong: 
    prefixSum[i] = prefixSum[i] + nums[i];
    // prefixSum[i] is not initialized
✓ Right: 
    prefixSum[i] = prefixSum[i - 1] + nums[i];
Reason: Build from previous sum

Mistake 3: Storing nums instead of prefixSum
❌ Wrong: 
    this.nums = nums;
    // Then calculate sum each time
✓ Right: 
    this.prefixSum = new int[n];
    // Precompute prefix sums
Reason: Purpose of this approach is preprocessing

Mistake 4: Wrong subtraction in range sum
❌ Wrong: 
    return prefixSum[left] - prefixSum[right];
    // Backwards!
✓ Right: 
    return prefixSum[right] - prefixSum[left - 1];
Reason: Remove left part from total

Mistake 5: Padding but forgetting offset
❌ Wrong (with padding): 
    return prefixSum[right] - prefixSum[left - 1];
    // Wrong indices with padding
✓ Right (with padding): 
    return prefixSum[right + 1] - prefixSum[left];
Reason: Padding shifts indices by 1

Mistake 6: Not building prefix sum in constructor
❌ Wrong: 
    // Build prefix sum in sumRange
    for (int i = left; i <= right; i++) sum += nums[i];
✓ Right: 
    // Build in constructor, use in sumRange
    prefixSum[i] = prefixSum[i-1] + nums[i];
Reason: Defeats the purpose of preprocessing

🎯 Key Takeaways

⚡ Algorithm Comparison

Approach 1: Brute Force (No Preprocessing)
  Constructor: O(1)
  Query: O(n)
  Total (q queries): O(q × n)
  Space: O(1)
  Use: Only if very few queries

Approach 2: Prefix Sum (RECOMMENDED)
  Constructor: O(n)
  Query: O(1)
  Total (q queries): O(n + q)
  Space: O(n)
  Use: Multiple queries (optimal)

🔑 The Core Insight

Prefix Sum Pattern:
═══════════════════════════════════════════════════════════════

When to use:
- Multiple range sum queries
- Immutable array (doesn't change)
- Need fast query time

Key idea: Trade space for time
- Use O(n) space to store prefix sums
- Get O(1) query time instead of O(n)

Formula:
═══════════════════════════════════════════════════════════════

Build:
  prefixSum[i] = prefixSum[i-1] + nums[i]

Query [left, right]:
  if left == 0:
    return prefixSum[right]
  else:
    return prefixSum[right] - prefixSum[left - 1]

Visual Understanding:
═══════════════════════════════════════════════════════════════

         0   1   2   3   4   5
nums = [-2,  0,  3, -5,  2, -1]
         └───┘
      prefixSum[1] = -2

         └───────────┘
      prefixSum[3] = -4

Range [2, 3]:
  prefixSum[3] - prefixSum[1]
  = -4 - (-2)
  = -2
  = nums[2] + nums[3]
  = 3 + (-5) ✓

Padding Technique:
═══════════════════════════════════════════════════════════════

Standard (size n):
  prefixSum[0] = nums[0]
  prefixSum[i] = prefixSum[i-1] + nums[i]

  Query:
    if (left == 0) return prefixSum[right];
    return prefixSum[right] - prefixSum[left - 1];

Padded (size n+1):
  prefixSum[0] = 0  // Extra element!
  prefixSum[i+1] = prefixSum[i] + nums[i]

  Query:
    return prefixSum[right + 1] - prefixSum[left];
    // No if statement needed!

Trade-offs:
+ Padding: Cleaner code, no edge case
- Padding: Extra space, index offset

Time Complexity Analysis:
═══════════════════════════════════════════════════════════════

Example: 10,000 queries on array of 1,000 elements

Brute Force:
  10,000 × 1,000 = 10,000,000 operations

Prefix Sum:
  1,000 (build) + 10,000 (queries) = 11,000 operations

Speedup: ~909x faster!

🎯 Pattern Recognition

Problem Type: Range Query with Preprocessing
Core Pattern: Prefix Sum

When to Apply:
✓ Multiple range sum queries
✓ Array doesn't change (immutable)
✓ Need O(1) query time
✓ Can afford O(n) preprocessing
✓ Can afford O(n) extra space

Recognition Keywords:
- "Multiple queries"
- "Range sum"
- "Immutable" or "doesn't change"
- "Initialize" + "query"
- Many calls to query function

Variations:
┌────────────────────────────────────────────┐
│ 1D prefix sum → This problem              │
│ 2D prefix sum → Matrix range sum          │
│ Prefix XOR → Range XOR queries            │
│ Difference array → Range update queries   │
└────────────────────────────────────────────┘

Related Problems:
- Range Sum Query 2D - Immutable (LC 304)
- Product of Array Except Self (LC 238)
- Subarray Sum Equals K (LC 560)
- Continuous Subarray Sum (LC 523)

🧠 Interview Strategy

Step 1: "Multiple range sum queries on immutable array"
Step 2: "Brute force: O(n) per query = O(q×n) total"
Step 3: "Can we preprocess to speed up queries?"
Step 4: "Use prefix sum array for O(1) queries"
Step 5: "Build: O(n), Query: O(1), Total: O(n+q)"

Key Points to Mention:
- Recognize multiple queries → need preprocessing
- Immutable array → can precompute once
- Prefix sum definition: sum from 0 to i
- Range sum formula: prefixSum[right] - prefixSum[left-1]
- Handle left = 0 edge case (or use padding)
- Space-time tradeoff: O(n) space for O(1) queries
- Build time: O(n)
- Query time: O(1)
- Much better for multiple queries

Why Preprocessing?
"With multiple queries, it's worth spending O(n) time
once to build the prefix sum array, because then each
of the potentially thousands of queries becomes O(1)
instead of O(n)."

The Formula Explanation:
"Prefix sum at i contains the sum from 0 to i. To get
sum from left to right, I take the sum from 0 to right
and subtract the sum from 0 to left-1. This removes
the unwanted left part."

This is the foundational prefix sum problem! 🏆

📝 Quick Revision Notes

🎯 Core Concept:

Precompute prefix sums for O(1) queries. Range sum = prefixSum[right] - prefixSum[left-1]. Handle left = 0 edge case.

⚡ Quick Implementation (Standard):

class NumArray {
    private int[] prefixSum;

    public NumArray(int[] nums) {
        int n = nums.length;
        prefixSum = new int[n];
        prefixSum[0] = nums[0];
        for (int i = 1; i < n; i++) {
            prefixSum[i] = prefixSum[i - 1] + nums[i];
        }
    }

    public int sumRange(int left, int right) {
        if (left == 0) return prefixSum[right];
        return prefixSum[right] - prefixSum[left - 1];
    }
}

⚡ Quick Implementation (Padded):

class NumArray {
  int[] prefixSum;

  public NumArray(int[] a) {
    int len = a.length;
    prefixSum = new int[len + 1];

    for (int i = 1; i <= len; i++) {
      prefixSum[i] = prefixSum[i - 1] + a[i - 1];
    }
  }

  public int sumRange(int left, int right) {
    // [1, 2, 3, 4] => [0, 1, 3, 6, 10]
    // sumRange(1, 2) = 5 => prefixSum[3] - prefixSum[1]
    // sumRange(0, 2) = 6 => prefixSum[3] - prefixSum[0]
    return prefixSum[right + 1] - prefixSum[left];
  }
}

🔑 Key Insights:

Pattern: Preprocessing for multiple queries
Build: prefixSum[i] = prefixSum[i-1] + nums[i]
Query: prefixSum[right] - prefixSum[left-1]
Edge case: When left = 0, return prefixSum[right]
Padding trick: Add prefixSum[0] = 0 to avoid edge case
Build time: O(n) - one pass
Query time: O(1) - simple subtraction
Space: O(n) - prefix sum array
When to use: Multiple queries on immutable array
Trade-off: O(n) space for O(1) queries

🎪 Memory Aid:

"PREFIX sum = sum from START! Range = TOTAL minus LEFT part!"
Think: "Precompute once, query FAST!"

💡 The Visual Trick:

[----prefixSum[right]----]
[prefixSum[left-1]][RANGE]

Remove left part → get range!

prefixSum[right] - prefixSum[left-1] = RANGE sum

🔥 Why Prefix Sum Wins:

10,000 queries on 1,000-element array:

Brute Force: 10,000 × 1,000 = 10,000,000 operations
Prefix Sum:  1,000 + 10,000 =     11,000 operations

~909x FASTER!

Range Sum Query 2D - Immutable (LC 304)
Product of Array Except Self (LC 238)
Subarray Sum Equals K (LC 560)
Continuous Subarray Sum (LC 523)

Happy practicing! 🎯