Segment Tree Implementation in Go

A Segment Tree is a data structure that allows for efficient range queries and updates on an array. It is particularly useful when dealing with problems that require frequent queries for the sum, minimum, or maximum of elements in a subarray, along with updates to individual elements.

Program Structure

The Go program implementing the Segment Tree is structured into the following components:

1. SegmentTree Struct: This struct represents the Segment Tree, containing a slice that stores the tree data and the size of the original array.
2. NewSegmentTree Function: This function initializes a new Segment Tree for a given array by building the tree.
3. Build Method: This method recursively builds the Segment Tree from the given array.
4. Update Method: This method updates an element in the array and reflects the change in the Segment Tree.
5. RangeQuery Method: This method returns the result of a range query (e.g., sum, min, or max) over a specified range in the array.
6. Query Method: This helper method performs the actual recursive range query on the Segment Tree.

Go Code Implementation

package main

import (
    "fmt"
    "math"
)

// SegmentTree represents a Segment Tree for range queries
type SegmentTree struct {
    tree []int
    size int
}

// NewSegmentTree creates a new Segment Tree for a given array
func NewSegmentTree(arr []int) *SegmentTree {
    size := len(arr)
    treeSize := 2*int(math.Pow(2, math.Ceil(math.Log2(float64(size))))) - 1
    tree := make([]int, treeSize)
    st := &SegmentTree{tree: tree, size: size}
    st.build(arr, 0, size-1, 0)
    return st
}

// build recursively builds the Segment Tree from the array
func (st *SegmentTree) build(arr []int, start, end, node int) {
    if start == end {
        st.tree[node] = arr[start]
        return
    }
    mid := (start + end) / 2
    st.build(arr, start, mid, 2*node+1)
    st.build(arr, mid+1, end, 2*node+2)
    st.tree[node] = st.tree[2*node+1] + st.tree[2*node+2] // Sum operation
}

// Update updates an element at a specific index and reflects the change in the Segment Tree
func (st *SegmentTree) Update(index, value int) {
    st.update(0, st.size-1, index, value, 0)
}

// update is a helper function that performs the update operation
func (st *SegmentTree) update(start, end, index, value, node int) {
    if start == end {
        st.tree[node] = value
        return
    }
    mid := (start + end) / 2
    if index <= mid {
        st.update(start, mid, index, value, 2*node+1)
    } else {
        st.update(mid+1, end, index, value, 2*node+2)
    }
    st.tree[node] = st.tree[2*node+1] + st.tree[2*node+2] // Sum operation
}

// RangeQuery returns the sum of elements in the range [l, r]
func (st *SegmentTree) RangeQuery(l, r int) int {
    return st.query(0, st.size-1, l, r, 0)
}

// query is a helper function that performs the range query operation
func (st *SegmentTree) query(start, end, l, r, node int) int {
    if l <= start && r >= end {
        return st.tree[node]
    }
    if end < l || start > r {
        return 0
    }
    mid := (start + end) / 2
    leftSum := st.query(start, mid, l, r, 2*node+1)
    rightSum := st.query(mid+1, end, l, r, 2*node+2)
    return leftSum + rightSum
}

func main() {
    arr := []int{1, 3, 5, 7, 9, 11}
    st := NewSegmentTree(arr)

    fmt.Println("Sum of values in range [1, 3]:", st.RangeQuery(1, 3)) // Output: 15
    fmt.Println("Sum of values in range [2, 5]:", st.RangeQuery(2, 5)) // Output: 32

    st.Update(1, 10)
    fmt.Println("After update, sum of values in range [1, 3]:", st.RangeQuery(1, 3)) // Output: 22
}
    

Explanation of the Code

Here’s a breakdown of the code:

• SegmentTree Struct: The SegmentTree struct represents the Segment Tree, containing a slice tree that stores the tree data and the size of the original array.
• NewSegmentTree Function: This function initializes a new Segment Tree for a given array. The size of the Segment Tree is determined based on the size of the array, and the tree is built using the build method.
• Build Method: This method recursively builds the Segment Tree from the given array. It combines the values from child nodes to form the parent nodes. In this implementation, the sum operation is used, but it can be modified for min, max, etc.
• Update Method: This method updates an element in the array and reflects the change in the Segment Tree by recursively updating the necessary nodes in the tree.
• RangeQuery Method: This method returns the result of a range query (sum in this case) over a specified range in the array.
• Query Method: This helper method performs the actual recursive range query on the Segment Tree, considering cases where the query range overlaps with the current node’s range.

Usage Example

Here’s an example of how you might use this Segment Tree implementation in a Go program:

func main() {
    arr := []int{1, 3, 5, 7, 9, 11}
    st := NewSegmentTree(arr)

    fmt.Println("Sum of values in range [1, 3]:", st.RangeQuery(1, 3)) // Output: 15
    fmt.Println("Sum of values in range [2, 5]:", st.RangeQuery(2, 5)) // Output: 32

    st.Update(1, 10)
    fmt.Println("After update, sum of values in range [1, 3]:", st.RangeQuery(1, 3)) // Output: 22
}
    

Conclusion

This Go program demonstrates a basic implementation of a Segment Tree, a powerful data structure for efficient range queries and updates. Segment Trees are particularly useful in scenarios where frequent queries for the sum, minimum, or maximum of elements in a subarray are required, along with updates to individual elements. The flexibility of Segment Trees allows them to be adapted for various operations beyond just sum queries.