A segment tree supports efficient range updates and queries over an array. The following implementation uses an explicit tree structure with lazy propagation.

Node Representation

Each node stores its interval boundaries, the aggregated sum, and a pending lazy value that needs to be propagated to its childran before any further traversal.

static class Node {
    int start, end;
    long sum, pending;
}

Node[] tree;
long[] base;

Building the Tree

Build recursively from the oriignal array.

void build(int idx, int l, int r) {
    tree[idx] = new Node();
    tree[idx].start = l;
    tree[idx].end = r;
    tree[idx].pending = 0;
    if (l == r) {
        tree[idx].sum = base[l];
        return;
    }
    int m = (l + r) >> 1;
    build(idx << 1, l, m);
    build(idx << 1 | 1, m + 1, r);
    tree[idx].sum = tree[idx << 1].sum + tree[idx << 1 | 1].sum;
}

Pushing Down Lazy Updates

Apply pending updates to children and reset the current node’s pending flag.

void pushDown(int idx) {
    if (tree[idx].pending == 0) return;
    long tag = tree[idx].pending;
    int leftIdx = idx << 1;
    int rightIdx = leftIdx | 1;
    tree[leftIdx].pending += tag;
    tree[rightIdx].pending += tag;
    int m = (tree[idx].start + tree[idx].end) >> 1;
    tree[leftIdx].sum += tag * (m - tree[leftIdx].start + 1);
    tree[rightIdx].sum += tag * (tree[rightIdx].end - m);
    tree[idx].pending = 0;
}

Range Addition

Add a value delta to all elements in the range [ql, qr].

void rangeAdd(int idx, int ql, int qr, long delta) {
    if (tree[idx].start >= ql && tree[idx].end <= qr) {
        tree[idx].sum += delta * (tree[idx].end - tree[idx].start + 1);
        tree[idx].pending += delta;
        return;
    }
    pushDown(idx);
    if (tree[idx << 1].end >= ql)
        rangeAdd(idx << 1, ql, qr, delta);
    if (tree[idx << 1 | 1].start <= qr)
        rangeAdd(idx << 1 | 1, ql, qr, delta);
    tree[idx].sum = tree[idx << 1].sum + tree[idx << 1 | 1].sum;
}

Range Sum Query

Return the sum of elements in [ql, qr].

long querySum(int idx, int ql, int qr) {
    if (tree[idx].start >= ql && tree[idx].end <= qr)
        return tree[idx].sum;
    pushDown(idx);
    long res = 0;
    if (tree[idx << 1].end >= ql)
        res += querySum(idx << 1, ql, qr);
    if (tree[idx << 1 | 1].start <= qr)
        res += querySum(idx << 1 | 1, ql, qr);
    return res;
}

Always call pushDown before recursing into children to keep lazy values consistent.