rangesum

Rangesum refers to the operation of computing the sum of a contiguous subsequence of elements in an array. Formally, for an array A with indices, the range sum for a range [l, r] is the sum of A[i] for i from l to r, often with l and r being inclusive and the indexing either 0-based or 1-based, depending on the context.

A naive implementation computes the sum by iterating over the range, giving a time complexity of O(r−l+1) per query. To speed up multiple queries, prefix sums can be used. Let P[0] = 0 and P[i+1] = P[i] + A[i]. Then the range sum is P[r+1] − P[l]. This yields O(1) query time after O(n) preprocessing, but updates to A require rebuilding or partial recalculation of prefixes, which can be costly.

For dynamic workloads with frequent updates, data structures such as Fenwick trees (Binary Indexed Trees) or segment trees are employed. A Fenwick tree supports point updates and range sum queries in O(log n) time, using a cumulative frequency representation where sum(1..r) is queried and the range sum is sum(r) − sum(l−1). Segment trees provide similar capabilities and can be extended to handle more complex queries, such as range updates or combination with other operations.

Two-dimensional extensions use 2D prefix sums or 2D Fenwick/segment trees for range sums over submatrices. Important considerations include the indexing convention, handling empty ranges, and integer overflow in large datasets or modular arithmetic contexts.

Applications of rangesum include statistical data analysis, financial time series aggregation, database query optimization, and image processing. See also: prefix sum, range query, Fenwick tree, segment tree, Mo’s algorithm.