Segment Tree Intro
Imagine you have an array and you need to answer many queries like "what is the sum of elements from index L to R?" or "what is the minimum value in this range?" A segment tree is a binary tree data structure that answers range queries efficiently and also allows updates. It can answer range sum, min, max, gcd, etc., in O(log n) time.
A segment tree is a full binary tree where each node stores information about a segment of the array. Leaf nodes represent individual elements, and internal nodes combine their children (e.g., sum).
Properties:
- Size: roughly 4*n to safely store all nodes.
- Construction: O(n) time.
- Query: O(log n).
- Update (point update): O(log n).
Segment trees are used in problems where we need frequent range queries with occasional updates.
Two Minute Drill
- Segment tree answers range queries in O(log n).
- Each node stores aggregated info for a segment.
- Leaf nodes store single elements; internal nodes combine children.
- Used for sum, min, max, gcd, etc., with point or range updates.
Need more clarification?
Drop us an email at career@quipoinfotech.com