Building Segment Tree
Building a segment tree from an array involves recursively constructing nodes. We typically store the tree in an array (heap-like indexing). For an array of size n, we allocate size 4*n to be safe.
Algorithm:
1. If the segment is a leaf (l == r), store arr[l] at tree[node].
2. Else, recursively build left and right children, then combine.
Java implementation for sum segment tree:
int[] tree;
int[] arr;
int n;
public void build(int node, int start, int end) {
if (start == end) {
tree[node] = arr[start];
} else {
int mid = (start + end) / 2;
int leftChild = 2 * node;
int rightChild = 2 * node + 1;
build(leftChild, start, mid);
build(rightChild, mid + 1, end);
tree[node] = tree[leftChild] + tree[rightChild];
}
}
Time complexity: O(n).
Two Minute Drill
- Segment tree built recursively, splitting range into halves.
- Use array of size 4*n for storage.
- Leaf nodes store array elements; internal nodes store combination (sum/min/max).
- Build time O(n).
Need more clarification?
Drop us an email at career@quipoinfotech.com