Prefix sums

Precompute cumulative totals to answer range queries instantly.

The idea

If you need to find the sum of elements between index L and R many times, adding them up one by one takes O(N) time for every single query. If you have thousands of queries, this becomes painfully slow.

Instead, we can do a single pass beforehand to build a prefix sum array where each element stores the running total up to that point. Once we have this, any range sum from L to R is just the total up to R minus the total right before L. We get the answer in O(1) time.

L: R:

Drag L and R to instantly query the sum of the range.

How it works

By adding a dummy 0 at the beginning of the prefix array, the math becomes extremely clean: Sum(L, R) = P[R + 1] - P[L]. You don't have to write messy if L == 0 boundary checks.

class RangeQuery:
    def __init__(self, nums):
        # Build prefix array: P[i] holds sum of first i elements
        self.P = [0] * (len(nums) + 1)
        for i in range(len(nums)):
            self.P[i + 1] = self.P[i] + nums[i]

    def query(self, L, R):
        # O(1) time query
        return self.P[R + 1] - self.P[L]

Cost

Time Complexity O(N) build + O(1) query

Space Complexity O(N)

We trade O(N) extra memory (to store the prefix array) for lightning-fast O(1) queries.

Watch out for

Modifying the array: Prefix sums are perfect for static data. If the underlying numbers are frequently updated, rebuilding the prefix array takes O(N) each time. (If you need both fast updates and fast queries, you need a Segment Tree or Fenwick Tree).
Difference Arrays: The inverse pattern! If you need to add +V to a range [L, R] many times and only check the final array once at the end, use a difference array (diff[L] += V; diff[R+1] -= V), then run a prefix sum on it.