Static Range Sums — Solution & Editorial

Back to the Problem

Precompute prefix sums pre[i] = a₁+...+a_i; each query is pre[R] − pre[L−1].

Complexity: O(N + Q)

Watch out: Answers reach 10¹³ — use 64-bit sums.