SegmentTree.java

private static class SegmentTree {

    private final long[] tree;
    private final int size;

    public SegmentTree(int size) {
        this.tree = new long[size * 4];
        this.size = size;
    }

    protected long merge(long l, long r) {
        return l + r;
    }

    public void build(long[] values) {
        build(0, 0, size - 1, values);
    }

    private long build(int v, int tl, int tr, long[] values) {
        if (tl == tr) {
            return tree[v] = values[tl];
        } else {
            var tm = (tl + tr) / 2;
            var vl = build(v * 2 + 1, tl, tm, values);
            var vr = build(v * 2 + 2, tm + 1, tr, values);
            return tree[v] = merge(vl, vr);
        }
    }

    public void update(int index, long value) {
        update(0, 0, size - 1, index, value);
    }

    private long update(int v, int tl, int tr, int index, long value) {
        if (tl == tr) {
            return tree[v] = value;
        } else {
            var tm = (tl + tr) / 2;
            long vl, vr;
            if (index <= tm) {
                vl = update(v * 2 + 1, tl, tm, index, value);
                vr = tree[v * 2 + 2];
            } else {
                vl = tree[v * 2 + 1];
                vr = update(v * 2 + 2, tm + 1, tr, index, value);
            }
            return tree[v] = merge(vl, vr);
        }
    }

    public long query(int l, int r) {
        return query(0, 0, size - 1, l, r);
    }

    private long query(int v, int tl, int tr, int l, int r) {
        if (l == tl && r == tr) {
            return tree[v];
        } else {
            var tm = (tl + tr) / 2;
            if (r <= tm) {
                return query(v * 2 + 1, tl, tm, l, r);
            } else if (l >= tm + 1) {
                return query(v * 2 + 2, tm + 1, tr, l, r);
            } else {
                var lq = query(v * 2 + 1, tl, tm, l, tm);
                var rq = query(v * 2 + 2, tm + 1, tr, tm + 1, r);
                return merge(lq, rq);
            }
        }
    }

}