Range Sum Query — Immutable

Prefix sums · Precompute once, answer many times · Easy · about 16 min

Why it matters

Precomputation is a recurring trade: a little setup for very fast queries.

How it connects

The running sum becomes a reusable lookup table for many ranges.

Try first

What is the sum from i to j if you already know the sums before i and before j?

Interview cue

Construction costs O(n); each range query becomes O(1).