DATA STRUCTURES • ALGORITHMS

Range Sum Query

Answering multiple requests for the sum of elements within a given range [L, R] using precomputed prefix sums for efficiency.

Time

O(1) per Query

Space

O(N)

Key Principle 1

Precompute Prefix Sum in O(N)

Key Principle 2

Query result = P[R] - P[L-1]

Key Principle 3

Optimal for static arrays

Key Principle 4

Handles large number of queries

RANGE_SUM_LAB
ARRAY:
RANGE:
Current Step
Querying Range Sum: [2, 5]. Using precomputed prefix sum array P.
Playback
Query Result ⠿
L2
R5
STATUSInit
Query Logic ⠿
1// Preprocessing
2P[i] = P[i-1] + arr[i];
3// Range Query [L, R]
4int sum = P[R] - (L > 0 ? P[L-1] : 0);
5return sum; // O(1)
-2
P[0]
-2
P[1]
1
P[2]
-4
P[3]
-2
P[4]
-3
P[5]

Loading Lab...