Course contentsShow
← Computer Science
Lesson 645 of 2,87215. Tries and Specialized TreesFree lesson

Point Update Operations

Updating a single array element and propagating changes up the tree to maintain correct aggregate values.

Point Update Operations

You'll learn how to update a single element in an array backed by a segment tree and efficiently propagate that change upward to maintain correct range query results.

What Is a Point Update?

A point update means changing the value at one specific index in your original array. The challenge? Your segment tree stores aggregate values (sums, minimums, etc.) for ranges—so when you change a single element, all the range nodes that include that element must be recalculated.

Think of it like updating a single employee's salary in a company: you need to update not just their personal record, but also their department's total budget, their division's total, and the company-wide payroll—every level that includes them.

How Point Updates Work

When you update array[index] = newValue:

  1. Start at the leaf node representing that index
  2. Update the leaf with the new value
  3. Move up to the parent and recalculate its aggregate from its two children
  4. Continue upward through each ancestor until you reach the root

Each node you touch gets recalculated based on its children's current values. If you're maintaining a sum tree and change index 5 from 10 to 15, every ancestor node containing index 5 increases by 5.

Efficiency

Because the segment tree has logarithmic height, you only touch O(log n) nodes during an update—one at each level from leaf to root. This is dramatically faster than recalculating entire range sums from scratch.

The beauty of segment trees shines here: point updates remain fast while still supporting efficient range queries.

Key Takeaway:
Point updates in a segment tree require O(log n) time because you only recalculate values along the single path from the updated leaf to the root, propagating changes upward through each ancestor node.