Range Sum Query — Immutable

Given an array that never changes, answer many range-sum queries (l, r) — each asking for the sum of nums[l..r] inclusive — as fast as possible.

Example

Input: -2 0 3 -5 2 -1, queries (0,2) (2,5) (0,5) Output: 1 -1 -3

Approach

Recomputing each range sum from scratch is O(n) per query. Instead, precompute a prefix-sum array once: prefix[i] is the sum of the first i elements, with prefix[0] = 0. Any range sum (l, r) is then just prefix[r+1] - prefix[l] — O(n) to build, O(1) per query.

Input format

Line 1: the array, space-separated Line 2: flattened query pairs, space-separated (l1 r1 l2 r2 ...)

Print each query's answer, space-separated.