Static Range Sum Queries - Walkthrough

Problem: given array and queries $(l, r)$, answer each query with sum of $arr[l..r]$. Precompute prefix sums in $O(n)$. For each query, return $prefix[r+1] - prefix[l]$ in $O(1)$.

Example: $arr = [1, 2, 3, 4, 5]$, queries $[(0, 2), (1, 4), (2, 3)]$. Prefix: $[0, 1, 3, 6, 10, 15]$. Answers: $prefix[3] - prefix[0] = 6$, $prefix[5] - prefix[1] = 14$, $prefix[4] - prefix[2] = 7$. The pattern generalizes to any associative operation with an inverse, like XOR or modular addition.