Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Updating the segment tree
// We want to update the value associated with index in the input array
void update(int index, T value) {
update(1, 0, N-1, index, value);
}
// nodes[stIndex] is responsible for segment [lo, hi]
void update(int stIndex, int lo, int hi, int index, T value) {
if (lo == hi) {
nodes[stIndex].assignLeaf(value);
return;
}
int left = 2 * stIndex, right = left + 1, mid = (lo + hi) / 2;
if (index <= mid)
update(left, lo, mid, index, value);
else
update(right, mid+1, hi, index, value);
nodes[stIndex].merge(nodes[left], nodes[right]);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment