rangeSum method

num rangeSum(int low, int high)

Sum of elements [low..high] inclusive (0-based), in O(log n). Requires 0 <= low <= high < length.

Example:

final FenwickTree t = FenwickTree.fromList(<num>[1, 2, 3, 4]);
t.rangeSum(1, 3); // 9

Audited: 2026-06-12 11:26 EDT

Implementation

num rangeSum(int low, int high) {
  // Throw in release: invalid bounds must not silently flow into the
  // prefixSum subtraction below and yield a meaningless range total.
  if (low < 0 || low > high) {
    throw RangeError('low ($low) must be in 0..high ($high)');
  }
  if (high >= _size) {
    throw RangeError('high ($high) out of range [0, $_size)');
  }
  // Subtract the prefix below `low`; when low is 0 there is nothing to remove.
  if (low == 0) {
    return prefixSum(high);
  }
  return prefixSum(high) - prefixSum(low - 1);
}