A Segment Tree is a powerful tree-based data structure designed to efficiently handle range queries and point update on arrays. Let’s explore its core concepts and structure in detail.
What is a Segment Tree?
A Segment Tree is a binary tree where each node represents an interval(segment) of the original array. The leaf nodes represent individual array elements, while internal nodes store aggregated information(like sum, maximum, minimum) of their corresponding intervals.
Tree Structure and Properties
Storage Method
- Use array-based representation(similar to heap storage)
- Root Node at index 0
- For node at index
i:- Left Child at
2*i + 1 - Right Child at
2*i + 2 - Parent at
(i - 1) / 2
- Left Child at
- Usually requires up to
4*nspace for an array of sizento accommodate all segments.
Node Relationships
Original Array: [1, 3, 5, 7, 9, 11]
Tree Structure:
Node[0] [0,5]: 36
/ \
[0,2]: 9 [3,5]: 27
/ \ / \
[0,1]: 4 [2]: 5 [3,4]: 16 [5]: 11
/ \ / \
[0]: 1 [1]: 3 [3]: 7 [4]: 9Core Operations
1. Build - O(n)
Each array element is processed exactly once during the construction
- Recursively construct the tree from bottom to top
- Leaf nodes directly store array elements
- Internal nodes store merged result from children
2. Range Query - O(log n)
At most log n nodes are visited along the path from root to leaves. There are three cases:
- No overlap: Query range doesn’t intersect current node’s range -> return neutral value which doesn’t affect the result
- Complete overlap: Current node’s range is completely within query range -> return node’s value
- Partial overlap: Recursively query both children and merge results
3. Point Update - O(log n)
- Navigate to the target leaf node
- Update the leaf value
- Propagate changes up to the root by updating all ancestor nodes.
Use Cases
Segment Tree is versatile and can be adapted for various range query problems, including but not limited to:
- Range Sum Query
- Range Minimum/Maximum Query
- Range GCD Query
Also Segment Tree has some variants like:
- Lazy Propagation Segment Tree: Efficiently handles range updates
- Persistent Segment Tree: Maintains multiple versions of the array
- 2D Segment Tree: Handles 2D range queries
Example Implementation in Go
Sum Segment Tree with Range Sum Query and Point Update
Type SegmentTree struct {
tree []int // segment tree array
n int // size of the original array
}
func NewSegmenTree( arr []int) *SegmentTree {
n := len(arr)
st := &SegmentTree{
tree: make([]int, 4*n), // allocate enough space
n: n,
}
if n > 0 {
st.build(arr, 0, 0, n-1)
}
return st
}
func (st *SegmentTree) build(arr []int, node, start, end int) {
// Base case: Leaf node, store the array value
if start == end {
st.tree[node] = arr[start]
} else {
// Recursively build left and right subtrees
mid := ( start + end ) / 2
leftChild := 2*node + 1
rightChild := 2*node + 2
st.build(arr, leftChild, start, mid)
st.build(arr, rightChild, mid+1, end)
st.tree[node] = st.tree[leftChild] + st.tree[rightChild]
}
}
func (st *SegmentTree) Query(l, r int) int {
if l < 0 || r >= st.n || l > r {
return 0
}
return st.query(0, 0, st.n-1, l, r)
}
func (st *SegmentTree) query(node, start, end, l, r int) int {
// No overlap
if r < start || end < l {
return 0
}
// Complete overlap
if l <= start && end <= r {
return st.tree[node]
}
// Partial overlap
mid := ( start + end ) / 2
leftChild := 2*node + 1
rightChild := 2*node + 2
leftSum := st.query(leftChild, start, mid, l, r)
rightSum := st.query(rightChild, mid+1, end, l, r)
return leftSum + rightSum
}
func (st *SegmentTree) Update(index, val int) {
if idnex < 0 || index >= st.n {
return
}
st.update(0, 0, st.n-1, index, val)
}
func (st *SegmentTree) update(node, start, end, index, val int) {
if start == end {
st.tree[node] = val
} else {
mid := ( start + end ) / 2
leftChild := 2*node + 1
rightChild := 2*node + 2
if index <= mid {
st.update(leftChild, start, mid, index, val)
} else {
st.update(rightChild, mid+1, end, index, val)
}
st.tree[node] = st.tree[leftChild] + st.tree[rightChild]
}
}