Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Querying the segment tree
// V is the type of the required aggregate statistic
V getValue(int lo, int hi) {
SegmentTreeNode result = getValue(1, 0, N-1, lo, hi);
return result.getValue();
}
// nodes[stIndex] is responsible for the segment [left, right]
// and we want to query for the segment [lo, hi]
SegmentTreeNode getValue(int stIndex, int left, int right, int lo, int hi) {
if (left == lo && right == hi)
return nodes[stIndex];
int mid = (left + right) / 2;
if (lo > mid)
return getValue(2*stIndex+1, mid+1, right, lo, hi);
if (hi <= mid)
return getValue(2*stIndex, left, mid, lo, hi);
SegmentTreeNode leftResult = getValue(2*stIndex, left, mid, lo, mid);
SegmentTreeNode rightResult = getValue(2*stIndex+1, mid+1, right, mid+1, hi);
SegmentTreeNode result;
result.merge(leftResult, rightResult);
return result;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment