Range Sum Query — Immutable

Problem Overview

Given a fixed array and a list of [left, right] range queries, return the sum of each range. DeepLogic's adaptation asks for every query's answer at once, in a single call, rather than modeling repeated method calls on a stored object.

Why solve this?

The foundational reason prefix sums exist: turning many O(n) range-sum queries into O(1) lookups after a single O(n) preprocessing pass — the return on investment gets larger the more queries you answer.

Pattern Recognition

Whenever the same array is queried for range sums repeatedly and the array itself never changes between queries, precompute a running-total prefix array once so every future query becomes a single subtraction.

Prerequisites

• Running Sum of 1d Array — the prefix array this problem's queries are built on.

Hints

1. Recomputing a range's sum by looping over it for every query costs O(n) per query — with many queries that adds up fast.
2. Build one prefix array where prefix[i] holds the sum of the first i elements (prefix[0] = 0).
3. The sum of nums[left..right] is exactly prefix[right + 1] - prefix[left].

Approach

This is a DeepLogic curriculum adaptation of the classic 'Range Sum Query — Immutable' idea: instead of modeling a constructor that builds a reusable query object with a separate method called once per query, this version takes the full batch of queries up front and returns every answer in one call — the same underlying prefix-sum technique, expressed as a single function so it fits this course's one-method-per-problem format. Build a prefix array of length n + 1 where prefix[0] = 0 and prefix[i] = prefix[i-1] + nums[i-1], so prefix[i] holds the sum of the first i elements. Once built, the sum of any range [left, right] is prefix[right + 1] - prefix[left] — an O(1) lookup per query after the one-time O(n) build.

Code

class Solution {
    public int[] rangeSumQueries(int[] nums, int[][] queries) {
        int n = nums.length;
        int[] prefix = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        int[] result = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int left = queries[i][0], right = queries[i][1];
            result[i] = prefix[right + 1] - prefix[left];
        }
        return result;
    }
}

Related Problems

• Reverse an Arrayeasy
• Second Largest Element in an Arrayeasy
• Plus Oneeasy
• Running Sum of 1d Arrayeasy