Point Updates
When a single element in the array changes, we need to update the segment tree. This involves updating the leaf node and propagating the change up to the root.
Algorithm:
1. If the leaf node (start == end), update tree[node] = new value.
2. Else, recurse to the appropriate child (left or right).
3. After recursion, recompute tree[node] = tree[left] + tree[right] (or combine).
Java implementation:
public void update(int node, int start, int end, int idx, int newVal) {
if (start == end) {
arr[idx] = newVal;
tree[node] = newVal;
} else {
int mid = (start + end) / 2;
int leftChild = 2 * node;
int rightChild = 2 * node + 1;
if (idx <= mid) {
update(leftChild, start, mid, idx, newVal);
} else {
update(rightChild, mid + 1, end, idx, newVal);
}
tree[node] = tree[leftChild] + tree[rightChild];
}
}
Time complexity: O(log n).
Two Minute Drill
- Point update changes a single element and updates ancestors.
- Recursively find leaf, then recompute upwards.
- Time O(log n).
- Supports dynamic array with range queries.
Need more clarification?
Drop us an email at career@quipoinfotech.com