Range Sum Query Immutable

0Easy

Range Sum Query Immutable

Given an integer array nums, implement sumRange(left, right) which returns the sum of elements from index left to right (inclusive). Use prefix sums for O(1) queries.

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

Jnaneshwara Reddy Satti

Builder · ClearCode

Hi — I'm a 21yo CS grad from India. I built ClearCode while recovering from a surgery, because I genuinely believe DSA should be visual, free, and accessible to everyone. No VC funding. No team. Just me, my laptop, and a lot of chai. ☕

If ClearCode helped you understand even one concept — consider supporting it. Every rupee keeps the servers running and new videos coming.

Support via Razorpay

Found this helpful? Support ClearCode ☕ — keeps it free forever

Algorithm Visualizer

O(1) for sumRange queries, O(N) for preprocessing

Before starting this video, please check the description to ensure you know the prerequisites. If you're comfortable with arrays and hash maps, let's go! This problem is a favorite in interviews at companies like Google and Facebook because it teaches you how to optimize range queries using prefix sums.

TEST CASE: []O(N)

clearcode.in

Execution Trace

1class NumArray:

2 def __init__(self, nums):

3 self.prefix_sums = [0] * (len(nums) + 1)

4 for i in range(len(nums)):

5 self.prefix_sums[i + 1] = self.prefix_sums[i] + nums[i]

7 def sumRange(self, left, right):

8 return self.prefix_sums[right + 1] - self.prefix_sums[left]

0:00 / 4:58

Range Sum Query Immutable — Easy Arrays Algorithm | ClearCode