query method

num query(int low, int high)

Combined value over the inclusive range [low..high], in O(log n). Requires 0 <= low <= high < length.

Example:

final SegmentTree t = SegmentTree.max(<num>[3, 1, 4, 1, 5]);
t.query(1, 3); // 4

Audited: 2026-06-12 11:26 EDT

Implementation

num query(int low, int high) {
  // Enforced in release: `low > high` silently returns the identity (the walk
  // loop never runs) rather than signaling bad input; a negative low or
  // out-of-range high reads the wrong slots or throws far from the cause.
  if (low < 0 || low > high) {
    throw RangeError('low ($low) must be in 0..high ($high)');
  }
  if (high >= _n) {
    throw RangeError.range(high, low, _n - 1, 'high');
  }
  num result = _identity;
  // Walk both boundaries inward, folding in any node that sits fully inside
  // the range (signaled by the boundary index being odd / even respectively).
  int l = low + _n;
  int r = high + _n + 1;
  while (l < r) {
    if (l & 1 == 1) result = _combine(result, _tree[l++]);
    if (r & 1 == 1) result = _combine(result, _tree[--r]);
    l >>= 1;
    r >>= 1;
  }
  return result;
}