Java Fenwick tree: point additions and half-open prefix sums

Java 8+. The program uses JDK classes and requires no preview flags.

Keep external indices consistent

The service exposes zero-based positions and an exclusive prefix end. Internally, the array uses one-based positions because the lowest set bit identifies the parent interval. Mixing those conventions can create an infinite update loop at zero or include the wrong endpoint.

An update adds a delta; it does not assign a new absolute value. Replacing a stored measurement requires knowing its prior value and computing the difference. The range query subtracts two prefix sums and accepts an empty half-open interval.

The fixture supports signed totals but bounds their cumulative absolute update budget to Long.MAX_VALUE / 4. That conservative rule ensures all internal partial sums and range differences remain representable. It is a declared limitation, not a promise that arbitrary long updates are safe.

Reject before changing nodes

The budget and index checks run before the update walks the tree. A rejected delta therefore leaves every partial sum unchanged. Without that ordering, an overflow at a later ancestor could leave earlier nodes updated and the representation inconsistent.

Working program

public class ReceiptFenwickTotals {
    final long[] sums;long spent;
    ReceiptFenwickTotals(int size){if(size<0||size>1_000_000)throw new IllegalArgumentException("Tree size");sums=new long[size+1];}
    void add(int index,long delta){
        if(index<0||index>=sums.length-1||delta==Long.MIN_VALUE)throw new IllegalArgumentException("Update boundary");
        long cost=Math.abs(delta),budget=Long.MAX_VALUE/4;if(cost>budget-spent)throw new IllegalArgumentException("Magnitude budget");
        spent+=cost;for(int slot=index+1;slot<sums.length;slot+=slot&-slot)sums[slot]+=delta;
    }
    long prefix(int end){if(end<0||end>=sums.length)throw new IllegalArgumentException("Prefix boundary");long total=0;for(int slot=end;slot>0;slot-=slot&-slot)total+=sums[slot];return total;}
    long range(int start,int end){if(start<0||start>end||end>=sums.length)throw new IllegalArgumentException("Range boundary");return prefix(end)-prefix(start);}
    public static void main(String[] args){ReceiptFenwickTotals totals=new ReceiptFenwickTotals(4);totals.add(0,4);totals.add(1,7);totals.add(3,-2);System.out.println(totals.prefix(2));System.out.println(totals.range(1,4));System.out.println(totals.range(2,2));}
}

Output

11
5
0

Costs and boundaries

Point addition and prefix/range queries take O(log n); storage is O(n). This mutable structure is not synchronized. Its conservative cumulative-magnitude budget can reject later updates even when the current aggregate happens to be small after cancellations.

Common Mistakes

• The external prefix endpoint is exclusive.
• An addition is not an absolute assignment.
• Do not discover overflow after partially mutating the tree.

Read next

Array boundaries, Index reasoning.

Continue with range and graph boundaries

Continue with Java prefix sums: answer repeated half-open range totals, Java difference arrays: batch inclusive range additions.