This module provides functionality to compute the prefix sum of an array and to calculate the sum of elements in a specified range using the prefix sum array. It is useful for efficiently answering range-sum queries after a preprocessing step. The prefix sum at each index is the sum of all previous elements including the current one. It allows for quick calculation of sums over subarrays and is a common technique in algorithm design.

author

- Roy Ratcliffe

 prefix_sum(+Numbers:list(number), -PrefixSum:list(number)) is det

Calculates the inclusive prefix sum of the given array. The prefix sum at each index is the sum of all previous elements including the current one. This is useful for efficiently computing cumulative sums. The function is deterministic and will always produce the same output for the same input.

The Numbers array must be ground numerical values. The resulting PrefixSum array will have the same length as the input Numbers array.

Why is this useful?

• It allows for quick calculation of sums over subarrays.
• It can be used in various algorithms that require cumulative sums.

It answers range-sum queries in constant time O(1) after a linear time O(n) preprocessing step. This is particularly useful in scenarios where multiple range-sum queries are performed on the same array. The sum of A[i..j] can be computed as PrefixSum[j] - PrefixSum[i-1].

Arguments:

Numbers	- A list of numerical values for which the prefix sum is to be calculated.
PrefixSum	- The resulting array containing the prefix sums.

 range_sum(+PrefixSum:list(number), +Index0:integer, +Index:integer, -Sum:number) is det

Computes the sum of elements in the original array from Index0 to Index using the provided PrefixSum array.

This function assumes that the PrefixSum array has been computed using the prefix_sum/2 predicate.

Arguments:

PrefixSum	- The prefix sum array.
Index0	- The starting index of the range (inclusive).
Index	- The ending index of the range (inclusive).
Sum	- The resulting sum of elements from Index0 to Index.