Introduction

The Range Sum Query problem involves finding the sum of elements between two indices in an array.

Given an array arr[] and multiple queries (left,rigjt), the task is to calculate the sum of elements from index left to index right.

This is one of the most important Prefix Sum problems and helps in understanding preprocessing techniques, range queries, and efficient repeated computations.

Example
Input: arr[] = [2, 4, 1, 6, 3]Query:
left = 1
right = 3
Output: 11
Explanation:
Elements from index 1 to 3 are:
[4, 1, 6]
Sum = 4 + 1 + 6 = 11

Input: arr[] = [5, 2, 7, 1, 4]
Query:
left = 0
right = 2
Output: 14
Explanation:
Elements from index 0 to 2 are:
[5, 2, 7]
Sum = 14
    Constraints
   1 <= n <= 10^5-10^9 <= arr[i] <= 10^9
0 <= left <= right < n

Approach 1 : Brute Force

Explanation

The simplest way to solve this problem is:

  1. Traverse elements from left to right.
  2. Add all elements
  3. Return the sum

This approach works but becomes inefficient when multiple queries are present.

Steps

  1. Initialize sum = 0.
  2. Traverse from index  left to right.
  3. Add every element into sum.
  4. Return final sum.

Dry Run

Input Array: [2, 4, 1, 6, 3]left = 1
right = 3
Traverse index 1:
Sum = 4
Traverse index 2:
Sum = 4 + 1 = 5
Traverse index 3:
Sum = 5 + 6 = 11
Final Result:
11

Brute Force Code 

Complexity Analysis

Time Complexity: O(n)Explanation:
Elements between left and right indices are traversed.

Space Complexity: O(1)
Explanation:
No extra data structures are used.


Approach 2 : Optimized Solution (Prefix Sum)

Explanation

Instead of recalculating sums for every query, we can preprocess the array using a Prefix Sum Array.

The idea is:

  1. Prefix Sum at index i stores:
    • sum of elements from 0 to i.
  2. Range Sum can then be calculated using:
 Range Sum = prefix[right] - prefix[left - 1]

This allows queries to be answered in constant time.

Steps

  1.  Create prefix sum array.
  2. Store cumulative sums.
  3. For query:
    • if left == 0:
      • answer = prefix[right]
    • otherwise:
      • answer = prefix[right] - prefix[left - 1]

This becomes inefficient for multiple queries.

Dry Run

Input Array: [2, 4, 1, 6, 3]Build Prefix Sum Array:
prefix[0] = 2
prefix[1] = 2 + 4 = 6
prefix[2] = 6 + 1 = 7
prefix[3] = 7 + 6 = 13
prefix[4] = 13 + 3 = 16
Prefix Array:
[2, 6, 7, 13, 16]
Query:
left = 1
right = 3
Range Sum:
prefix[3] - prefix[0]
13 - 2 = 11
Final Result:
11

Optimized Code

Complexity Analysis


Time Complexity: O(n)Explanation:
Building the prefix sum array takes O(n).
Each query can then be answered in O(1).

Space Complexity: O(n)
Explanation:
No extra data structures are used.

Edge Cases

  1. left=0.
  2. left=right.
  3. Array contains negative numbers
  4. Array contains only one element
  5. Multiple repeated queries

Why This Problem is Important

This problem helps in understanding:

  1. Prefix Sum Technique
  2. Range query optimization
  3. Preprocessing concepts
  4. Efficient repeated computations
  5. Query-based problem solving

It is one of the most important Prefix Sum interview problems.

Real-World Applications

Range Sum Query concepts are used in:

  1. Database systems
  2. Financial analytics
  3. Time-series processing
  4. Sensor monitoring
  5. Gaming score systems

Common Mistakes

  1. Incorrect prefix calculations
  2. Wrong subtraction formula
  3. Forgetting left = 0 condition
  4. Incorrect indexing

Interview Tips

Interviewers often expect:

  1. Prefix Sum optimization
  2. O(1) query handling
  3. Proper preprocessing explanation

Always explain why preprocessing improves repeated query performance.

Related Questions

  1. Running Sum
  2. Subarray Sum Equals K
  3. Prefix Maximum
  4. 2D Prefix Sum
  5. Product Except Self

Final Takeaway

The Range Sum Query problem is a fundamental Prefix Sum problem that teaches preprocessing, cumulative computations, and efficient query handling techniques. Understanding this problem builds a strong foundation for advanced range query and prefix-based interview problems.