Prefix Sum

Solve repeated range-sum queries by preprocessing once, then subtracting two prefix values.

Query: 1/3 · Step: 0/5
Array → Prefix Array
Original arrayL = 2, R = 4
Prefix sumprefix[0] = 0
Range query: sum(2, 4)
Problem
Find the sum of values between indices L and R.
L = 2 · R = 4
prefix[R + 1] − prefix[L]
Build the prefix array first.
Direct range scanO(n)
Prefix queryO(1)
1 · BuildPrecompute prefix sums
2 · SelectHighlight [L, R]
3 · RightTake prefix[R + 1]
4 · RemoveSubtract prefix[L]
5 · AnswerRange sum in O(1)