Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Two Fenwick trees: add across ranges and query sums

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A point-update Fenwick tree cannot add a value to an entire range and then sum arbitrary ranges with the same formula. The two-tree variant stores a difference sequence in one Fenwick array and each difference multiplied by its zero-based position in another. For a prefix ending before position S, the element total is S times the first difference prefix minus the weighted difference prefix. A half-open update [start, stop) adds a difference at start and subtracts it at stop, when stop is inside the array. A range sum subtracts two prefixes. Empty intervals are valid and contribute zero. The public API uses zero-based positions and half-open stops throughout.

Operational case

Start with five depot capacities 23, 47, 19, 61, and 38. Add seven to positions [1, 4), then subtract four from [3, 5). The final values are 23, 54, 26, 64, and 34. Sum [1, 5) and get 178; sum [3, 4) and get 64. The second update overlaps the first at position three, and subtracts from position four without changing position two. A right boundary is excluded, so a correction to [1, 4) never touches the value at index four. Bounds are checked before any mutation to avoid partially applying an invalid request.

Working Python program

python
"""Two Fenwick trees for half-open range addition and range sums."""


class CapacityRangeIndex:
    def __init__(self, capacities: list[int]):
        self.length = len(capacities)
        self.differences = [0] * (self.length + 1)
        self.weighted_differences = [0] * (self.length + 1)
        for position, capacity in enumerate(capacities):
            self.add_between(position, position + 1, capacity)

    def _add(self, tree: list[int], position: int, amount: int) -> None:
        position += 1
        while position <= self.length:
            tree[position] += amount
            position += position & -position

    @staticmethod
    def _prefix(tree: list[int], stop: int) -> int:
        total = 0
        while stop:
            total += tree[stop]
            stop -= stop & -stop
        return total

    def add_between(self, start: int, stop: int, amount: int) -> None:
        if not 0 <= start <= stop <= self.length:
            raise IndexError((start, stop))
        if start == stop:
            return
        self._add(self.differences, start, amount)
        self._add(self.weighted_differences, start, amount * start)
        if stop < self.length:
            self._add(self.differences, stop, -amount)
            self._add(self.weighted_differences, stop, -amount * stop)

    def sum_before(self, stop: int) -> int:
        if not 0 <= stop <= self.length:
            raise IndexError(stop)
        return stop * self._prefix(self.differences, stop) - self._prefix(self.weighted_differences, stop)

    def sum_between(self, start: int, stop: int) -> int:
        if not 0 <= start <= stop <= self.length:
            raise IndexError((start, stop))
        return self.sum_before(stop) - self.sum_before(start)


capacity_index = CapacityRangeIndex([23, 47, 19, 61, 38])
capacity_index.add_between(1, 4, 7)
capacity_index.add_between(3, 5, -4)
print(capacity_index.sum_between(1, 5))
print(capacity_index.sum_between(3, 4))

Output

Output
178
64

Time, space, and tradeoff

Let N be the fixed array length. Each range addition makes at most four Fenwick point updates and costs O(log N) time, while each prefix or range sum costs O(log N) time. Two Fenwick arrays use O(N) memory. This program builds from initial values with N one-position updates, costing O(N log N); a specialized direct build could be faster. Values can be negative because the structure stores arithmetic totals, not a monotone count. Fixed-width languages need an accumulator wide enough for S times a difference and the total. A static prefix array is simpler for query-only data, while a lazy segment tree supports other aggregate and update combinations that this pair of additive trees cannot express directly.

Common Mistakes

  • Do not omit the weighted difference tree when asking for range sums.
  • Do not update the stop boundary when stop equals the array length.
  • Do not mix inclusive and half-open range endpoints.
  • Do not reuse this additive formula for assignment or minimum queries.

Connected lessons

Apply the invariant in the scan batch audit project, then check the operations quiz.

data structures
range-query-structures
Storage details