Segment Tree Updates

March 2026 · 18 min read

We've seen how to build a segment tree and answer range queries. Now comes the part that makes segment trees truly useful: updating the array while keeping all queries fast.

We'll cover point updates in full detail, then move to the natural next question, "what about range updates?", which motivates lazy propagation.

Point Updates

The Problem

We want to change a single element: arr[i] = newVal. After this change, any node in the segment tree whose range includes index i might now have a stale value. We need to update all affected nodes.

Which Nodes Are Affected?

Think about which nodes cover index i:

• The leaf at index i, obviously needs updating.
• The leaf's parent, its range includes i.
• The parent's parent, and so on, all the way up to the root.

This is exactly one path from the leaf to the root. The path has length O(log n) because the tree has O(log n) levels. No other nodes are affected, if a node's range doesn't contain i, its value hasn't changed.

The Algorithm

1. Navigate down from the root to the leaf containing index i. At each node, check if i is in the left half or right half, and recurse accordingly.
2. At the leaf: Set the node's value to newVal.
3. Propagate up: As the recursion unwinds, recalculate each parent as tree[node] = tree[2*node] + tree[2*node+1].

Step 3 is the key insight: by recalculating from the bottom up, every ancestor of the changed leaf gets its correct new value. The post-order recalculation ensures children are correct before their parent is computed.

The Pseudocode

Walkthrough: update(2, 10) on tree built from [1, 3, 5, 7]

We want to set arr[2] = 10 (was 5). The built tree currently has: tree = [_, 16, 4, 12, 1, 3, 5, 7].

Only 3 nodes were visited and modified: the leaf (6), its parent (3), and the root (1). This is the single path from the leaf to the root.

C++ Implementation: Point Update

void update(vector<int>& tree, int node, int start, int end,
            int idx, int val) {
    if (start == end) {
        // Leaf: apply the update
        tree[node] = val;
        return;
    }
    int mid = (start + end) / 2;

    if (idx <= mid)
        update(tree, 2 * node,     start, mid,     idx, val);
    else
        update(tree, 2 * node + 1, mid + 1, end,   idx, val);

    // Recalculate this node from its children
    tree[node] = tree[2 * node] + tree[2 * node + 1];
}

// Usage: update index 2 to value 10
// update(tree, 1, 0, n - 1, 2, 10);

Point Update Complexity

Time: O(log n), We descend one path from root to leaf (O(log n) levels) and do O(1) work at each node (one comparison + one addition).

Space: O(log n) for the recursion stack.

Update Variants

Set vs. Add

The example above sets arr[i] to a new value. Sometimes you want to add to the existing value instead: arr[i] += delta. The only change is at the leaf:

// Set variant: tree[node] = val;
// Add variant: tree[node] += delta;

The rest of the algorithm (propagating up) stays identical, because the parent recalculation tree[node] = tree[2*node] + tree[2*node+1] works regardless of how the leaf was modified.

Increment Update: An Optimization

For the "add delta" variant, there's an alternative: instead of recalculating from children, just add delta to every node on the path. This avoids reading children at all:

void addUpdate(vector<int>& tree, int node, int start, int end,
               int idx, int delta) {
    tree[node] += delta;  // add delta to every node on the path
    if (start == end) return;
    int mid = (start + end) / 2;
    if (idx <= mid)
        addUpdate(tree, 2 * node,     start, mid,     idx, delta);
    else
        addUpdate(tree, 2 * node + 1, mid + 1, end,   idx, delta);
}

This works because every ancestor of index i includes arr[i] in its sum. Adding delta to every ancestor correctly adjusts all sums. Same O(log n) time, slightly simpler.

The Range Update Problem

What If We Want to Update a Range?

Suppose instead of updating one element, we want to add 5 to every element in arr[1..4]. With point updates, we'd do:

update(1, +5);  // O(log n)
update(2, +5);  // O(log n)
update(3, +5);  // O(log n)
update(4, +5);  // O(log n)

That's 4 point updates. If the range has k elements, it's O(k · log n). For k = n, that's O(n log n) per range update. We're back to being slow.

Can We Do Better?

Yes! The idea: just like a range query uses the tree to avoid touching every element, a range update should too. If a node's range is entirely inside the update range, we should be able to mark it "updated" without recursing into its children.

But there's a problem: if we update a parent without updating its children, the children's values become stale. Future queries that go through those children will get wrong answers.

The solution is lazy propagation: store the pending update at the parent, and only "push it down" to the children when we actually need them. This gives us O(log n) range updates.

A Preview of Lazy Propagation

Each node gets a lazy[] value representing a pending update that hasn't been pushed to its children yet. When we need to access a node's children, we first "push down" the lazy value, then proceed normally.

This is the most important concept in segment trees. The next post covers it in complete detail with step-by-step walkthroughs and animations.

Interleaved Queries and Updates

The real power of segment trees is handling a mixed sequence of queries and updates. For example:

Build from [1, 3, 5, 7, 9, 11, 2, 4]
query(2, 5)   → 32
update(3, 10) → arr[3] changes from 7 to 10
query(2, 5)   → 35 (5 + 10 + 9 + 11)
update(0, 6)  → arr[0] changes from 1 to 6
query(0, 7)   → 51 (6 + 3 + 5 + 10 + 9 + 11 + 2 + 4 - wait, that's wrong — we need to recalculate!)

Every query returns the correct answer because every update keeps the tree consistent. There's no "rebuild" or "invalidation" step. Each operation is independent and takes O(log n).

Total Complexity for Q Operations

Complete Class with Point Updates

class SegmentTree {
    int n;
    vector<int> tree;

    void build(const vector<int>& arr, int node, int s, int e) {
        if (s == e) { tree[node] = arr[s]; return; }
        int mid = (s + e) / 2;
        build(arr, 2 * node, s, mid);
        build(arr, 2 * node + 1, mid + 1, e);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }

    int query(int node, int s, int e, int l, int r) {
        if (r < s || e < l) return 0;
        if (l <= s && e <= r) return tree[node];
        int mid = (s + e) / 2;
        return query(2*node, s, mid, l, r) + query(2*node+1, mid+1, e, l, r);
    }

    void update(int node, int s, int e, int idx, int val) {
        if (s == e) { tree[node] = val; return; }
        int mid = (s + e) / 2;
        if (idx <= mid) update(2*node, s, mid, idx, val);
        else update(2*node+1, mid+1, e, idx, val);
        tree[node] = tree[2*node] + tree[2*node+1];
    }

public:
    SegmentTree(const vector<int>& arr) : n(arr.size()), tree(4*n, 0) {
        build(arr, 1, 0, n-1);
    }
    int query(int l, int r) { return query(1, 0, n-1, l, r); }
    void update(int idx, int val) { update(1, 0, n-1, idx, val); }
};

Summary

• Point update: Navigate down to the leaf, change its value, recalculate every ancestor on the way back up. O(log n).
• Only nodes on the single path from leaf to root are affected, all other nodes stay unchanged.
• Two flavors: set (replace the value) and add (increment the value). Both are O(log n).
• Range updates with point-by-point approach are O(k · log n), too slow for large ranges.
• Lazy propagation (next post) solves this by deferring work and pushing it down only when needed, giving O(log n) range updates.