Pattern - When to Use Prefix Sums

Use prefix sums when you need many range sum queries on a static array. The $O(n)$ preprocessing pays off if $q$ queries would otherwise take $O(nq)$.

Also useful for: counting subarrays with target sum (hashmap variant), product queries (prefix/suffix products), 2D range sums (2D prefix). Don't use when: array updates frequently (use segment tree instead), only one query needed (just sum directly), or range operation isn't sum (may need different structure).

The pattern generalizes: any associative operation with an inverse can use a prefix-like approach. XOR, addition, multiplication (with care for zeros).