Math Fundamentals18 sections · 814 units
Open in Course

Problem - Range Sum Query

LeetCode 303

Given an array of integers numsnums, handle multiple queries asking for the sum of elements between indices ii and jj (inclusive).

For example, if nums=[2,0,3,5,2,1]nums = [-2, 0, 3, -5, 2, -1] and you query range [0,2][0, 2], the answer is 2+0+3=1-2 + 0 + 3 = 1.

You could loop through the range each time, but that takes O(n)O(n) per query. Can you precompute something to answer in O(1)O(1)?