The segment tree is constructed recursively. Each node tracks its segment boundaries [left, right]. Leaf nodes correspond to individual array elements, while enternal nodes store the sum of their children.

struct SegmentTree {
    int left[MAX_N * 4], right[MAX_N * 4];
    long long value[MAX_N * 4], lazy[MAX_N * 4];

    void build(int l, int r, int idx) {
        left[idx] = l;
        right[idx] = r;
        if (l == r) {
            scanf("%lld", &value[idx]);
            return;
        }
        int mid = (l + r) / 2;
        build(l, mid, idx * 2);
        build(mid + 1, r, idx * 2 + 1);
        value[idx] = value[idx * 2] + value[idx * 2 + 1];
    }
};

Point Update

To update a single element, traverse from the root to the target leaf, modifying values along the path.

void pointUpdate(int idx, int pos, int delta) {
    if (left[idx] == right[idx]) {
        value[idx] += delta;
        return;
    }
    if (lazy[idx]) pushLazy(idx);
    int mid = (left[idx] + right[idx]) / 2;
    if (pos <= mid) pointUpdate(idx * 2, pos, delta);
    else pointUpdate(idx * 2 + 1, pos, delta);
    value[idx] = value[idx * 2] + value[idx * 2 + 1];
}

Point Query

Retrieve a single element by traversing to the corresponding leaf node.

long long pointQuery(int idx, int pos) {
    if (left[idx] == right[idx]) return value[idx];
    if (lazy[idx]) pushLazy(idx);
    int mid = (left[idx] + right[idx]) / 2;
    if (pos <= mid) return pointQuery(idx * 2, pos);
    else return pointQuery(idx * 2 + 1, pos);
}

Range Query

For range queries, combine results from segments that fully or partially overlap with the query range.

long long rangeQuery(int ql, int qr, int idx) {
    if (ql <= left[idx] && right[idx] <= qr) return value[idx];
    if (lazy[idx]) pushLazy(idx);
    int mid = (left[idx] + right[idx]) / 2;
    long long result = 0;
    if (ql <= mid) result += rangeQuery(ql, qr, idx * 2);
    if (qr > mid) result += rangeQuery(ql, qr, idx * 2 + 1);
    return result;
}

Range Update with Lazy Propagation

Lazy propagation defers updates until necessary. When updating a range, mark nodes that fully cover the range and propagate changes later during queries or updates.

void pushLazy(int idx) {
    lazy[idx * 2] += lazy[idx];
    lazy[idx * 2 + 1] += lazy[idx];
    value[idx * 2] += lazy[idx] * (right[idx * 2] - left[idx * 2] + 1);
    value[idx * 2 + 1] += lazy[idx] * (right[idx * 2 + 1] - left[idx * 2 + 1] + 1);
    lazy[idx] = 0;
}

void rangeUpdate(int ql, int qr, int idx, int delta) {
    if (ql <= left[idx] && right[idx] <= qr) {
        value[idx] += delta * (right[idx] - left[idx] + 1);
        lazy[idx] += delta;
        return;
    }
    if (lazy[idx]) pushLazy(idx);
    int mid = (left[idx] + right[idx]) / 2;
    if (ql <= mid) rangeUpdate(ql, qr, idx * 2, delta);
    if (qr > mid) rangeUpdate(ql, qr, idx * 2 + 1, delta);
    value[idx] = value[idx * 2] + value[idx * 2 + 1];
}

Note: Array storage requires 4 times the original data size to accommodate the tree structure. Practice implementing and simulating these operations to gain proficiency.