Range Queries
After building the segment tree, we can answer range queries efficiently. For a range [L, R], we recursively search the tree, combining results from nodes that fully lie within the range.
Algorithm for sum query:
If current segment [start, end] is completely inside [L, R], return tree[node].
If completely outside, return 0 (identity for sum).
Otherwise, query left and right children and combine.
Java implementation:
public int query(int node, int start, int end, int L, int R) {
if (R < start || L > end) {
return 0; // no overlap
}
if (L <= start && end <= R) {
return tree[node]; // fully inside
}
int mid = (start + end) / 2;
int leftChild = 2 * node;
int rightChild = 2 * node + 1;
int leftSum = query(leftChild, start, mid, L, R);
int rightSum = query(rightChild, mid + 1, end, L, R);
return leftSum + rightSum;
}
Time complexity: O(log n).
Two Minute Drill
- Range query traverses the tree, combining nodes fully inside range.
- If no overlap, return identity (0 for sum, INF for min, -INF for max).
- Each query visits O(log n) nodes.
- Works for sum, min, max, gcd, etc.
Need more clarification?
Drop us an email at career@quipoinfotech.com