Understanding the prefix sum pattern

Some problems involving sequential data structures (like arrays) require us to know the aggregated value of some function f over all subarrays. Here f is a binary function that combines a running aggregate with the next item (for example, + for sum or * for product). For some functions f like the sum function, these values can be easily derived from a corresponding prefix sum data structure. A prefix sum data structure stores the aggregated value of f for all prefixes for the given sequence.

Consider we have an array arr and a function f where agg[i] is the aggregated value of f over arr[0] .. arr[i] (inclusive at both ends, so agg[i] = f(f(... f(arr[0], arr[1]), ...), arr[i]); for sum, agg[i] = arr[0] + arr[1] + ... + arr[i]). A prefix sum data structure is one where we map the index i to agg[i]. In most cases, we can use an array as a prefix sum data structure by storing agg[i] at the index i as we can easily access aggregated values of prefixes using indices.

However, there are cases where we need to store the reverse mapping i.e., mapping agg[i] to i. We cannot use an array for this as the aggregated values themselves can be arbitrary and not be used as indices of an array. In such cases, we use a hash table to map agg[i] to i where agg[i] is the key and i is the mapped value since hash tables can map arbitrary values together.