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

Point Update Operation

Implementing single element updates in O(log n) time by propagating changes through parent nodes using index manipulation.

Point Update Operation in Fenwick Trees

What you'll learn: How to update a single element in a Fenwick Tree efficiently by propagating changes upward through parent nodes using index manipulation.

The Core Idea

When you update a single value in your original array, you need to reflect that change in the Fenwick Tree structure. Unlike updating every affected node manually, the Fenwick Tree uses a clever trick: by manipulating indices based on their binary representation, you can identify exactly which parent nodes need updating and reach them all in O(log n) time.

How Index Manipulation Works

Remember that each index in a Fenwick Tree is responsible for a specific range of elements. When you update position i, you must also update all nodes "above" it in the responsibility hierarchy.

The key operation: add the last set bit to the current index repeatedly. This moves you up the tree through all ancestors that depend on this position.

The Update Pattern

Starting at index i:

  1. Add the difference (new value - old value) to tree[i]
  2. Calculate the next parent index: i = i + (i & -i)
  3. Repeat until you exceed the array bounds

The expression (i & -i) extracts the lowest set bit, which tells you the "jump size" to the next responsible parent node.

Why This Works

The binary structure of Fenwick Trees ensures that each node's range overlaps with specific other nodes. By adding the last set bit, you're essentially climbing up levels of responsibility, updating every node whose range includes your changed element.

Key Takeaway: Point updates in a Fenwick Tree take O(log n) time by using bitwise operations to efficiently traverse upward through all parent nodes that need to reflect the change.