Java lazy segment tree: add to ranges and query sums

Last updated: 29 Sept 20264 min read

tutorial

A lazy segment tree records a deferred update on a covered interval so range additions do not visit every element immediately.

Download Java source kit

This complete program targets Java 8. Its displayed output is checked by the tutorial validation script.

Store both the aggregate and the deferred work

A capacity ledger needs to add the same reservation adjustment to every slot in an interval and read interval totals. Each tree node stores its sum and a pending addition for its descendants. Covering a node updates its sum by delta times interval length and records the deferred delta.

Before visiting part of a covered node, push its deferred addition to both children. Otherwise a later partial query reads old child sums even though the parent looks correct. Zero is the identity for an absent contribution, not a missing-value sentinel.

Specify the arithmetic boundary

The implementation accepts nonempty arrays up to 100000 elements and half-open intervals with at least one element. It uses long sums and requires callers to keep every intermediate sum and product within long range. The code does not detect overflow; wrapping invalidates the result. Production ledgers need an overflow or wider-number policy before using this model.

Queries can push deferred updates, so they mutate internal representation even though the logical values remain unchanged. Do not expose this tree to concurrent readers without synchronization. Compare it with point-update trees and Fenwick sums before choosing the state you need.

Working program

public class CapacityRangeTree {
    private final int count;
    private final long[] sums, pending;
    CapacityRangeTree(long[] values) {
        if (values.length == 0 || values.length > 100000) throw new IllegalArgumentException("size");
        count = values.length; sums = new long[4 * count]; pending = new long[4 * count];
        build(1, 0, count, values);
    }
    private void build(int node, int left, int right, long[] values) {
        if (right-left == 1) { sums[node] = values[left]; return; }
        int middle = left + (right-left)/2;
        build(node*2,left,middle,values); build(node*2+1,middle,right,values);
        sums[node] = sums[node*2] + sums[node*2+1];
    }
    private void apply(int node,int length,long delta) { sums[node] += delta * length; pending[node] += delta; }
    private void push(int node,int left,int right) {
        int middle = left + (right-left)/2;
        apply(node*2,middle-left,pending[node]); apply(node*2+1,right-middle,pending[node]); pending[node]=0;
    }
    private void bounds(int left,int right) {
        if (left<0 || right>count || left>=right) throw new IllegalArgumentException("range");
    }
    void add(int left,int right,long delta) { bounds(left,right); add(1,0,count,left,right,delta); }
    private void add(int node,int left,int right,int from,int until,long delta) {
        if (until<=left || right<=from) return;
        if (from<=left && right<=until) { apply(node,right-left,delta); return; }
        push(node,left,right); int middle=left+(right-left)/2;
        add(node*2,left,middle,from,until,delta); add(node*2+1,middle,right,from,until,delta);
        sums[node]=sums[node*2]+sums[node*2+1];
    }
    long sum(int left,int right) { bounds(left,right); return sum(1,0,count,left,right); }
    private long sum(int node,int left,int right,int from,int until) {
        if (until<=left || right<=from) return 0;
        if (from<=left && right<=until) return sums[node];
        push(node,left,right); int middle=left+(right-left)/2;
        return sum(node*2,left,middle,from,until)+sum(node*2+1,middle,right,from,until);
    }
    public static void main(String[] args) {
        CapacityRangeTree ledger=new CapacityRangeTree(new long[]{10,20,30,40});
        ledger.add(1,4,5); System.out.println(ledger.sum(0,4));
        ledger.add(0,2,-3); System.out.println(ledger.sum(1,3));
        try { ledger.sum(2,2); } catch (IllegalArgumentException rejected) { System.out.println("empty range rejected"); }
    }
}

Output

115
57
empty range rejected

Costs and boundaries

Construction costs O(n) time and O(n) storage. Each interval addition or sum query takes O(log n) time with O(log n) recursion depth. The bound is for one contiguous interval; arbitrary disjoint batches add more operations. This implementation is not persistent or thread-safe.

Common Mistakes

Push pending work before descending into part of an interval.
Use one interval convention consistently.
Do not assume long arithmetic cannot overflow.