Segment Tree Implementation in Bash

This document explains how to implement a Segment Tree using Bash. A Segment Tree is a data structure that allows for efficient range queries and updates on an array. It is widely used in scenarios where we need to repeatedly calculate sums, minimums, maximums, or other aggregate functions over a range of elements.

Program Structure

The program is structured into several key functions:

• initialize_tree: Initializes the Segment Tree with a given array.
• build_tree: Recursively builds the Segment Tree.
• range_query: Queries the Segment Tree for a range sum.
• update_tree: Updates the Segment Tree when an element in the array changes.

Implementation

#!/bin/bash

# Initialize the Segment Tree
initialize_tree() {
    local arr=("$@")
    n=${#arr[@]}
    segment_tree=()
    build_tree arr 0 $((n - 1)) 0
}

# Recursively build the Segment Tree
build_tree() {
    local arr=("$@")
    local start=$2
    local end=$3
    local node=$4

    if [ $start -eq $end ]; then
        segment_tree[$node]=${arr[$start]}
    else
        local mid=$(( (start + end) / 2 ))
        local left_child=$(( 2 * node + 1 ))
        local right_child=$(( 2 * node + 2 ))
        
        build_tree arr $start $mid $left_child
        build_tree arr $((mid + 1)) $end $right_child
        
        segment_tree[$node]=$(( segment_tree[$left_child] + segment_tree[$right_child] ))
    fi
}

# Range query for sum
range_query() {
    local query_start=$1
    local query_end=$2
    query_tree 0 0 $((n - 1)) $query_start $query_end
}

# Recursively query the tree
query_tree() {
    local node=$1
    local start=$2
    local end=$3
    local query_start=$4
    local query_end=$5

    if [ $query_start -le $start ] && [ $query_end -ge $end ]; then
        echo ${segment_tree[$node]}
        return
    fi

    if [ $query_start -gt $end ] || [ $query_end -lt $start ]; then
        echo 0
        return
    fi

    local mid=$(( (start + end) / 2 ))
    local left_child=$(( 2 * node + 1 ))
    local right_child=$(( 2 * node + 2 ))

    local left_sum=$(query_tree $left_child $start $mid $query_start $query_end)
    local right_sum=$(query_tree $right_child $((mid + 1)) $end $query_start $query_end)

    echo $(( left_sum + right_sum ))
}

# Update the Segment Tree
update_tree() {
    local index=$1
    local value=$2
    update_recursive 0 0 $((n - 1)) $index $value
}

# Recursively update the tree
update_recursive() {
    local node=$1
    local start=$2
    local end=$3
    local index=$4
    local value=$5

    if [ $start -eq $end ]; then
        segment_tree[$node]=$value
    else
        local mid=$(( (start + end) / 2 ))
        local left_child=$(( 2 * node + 1 ))
        local right_child=$(( 2 * node + 2 ))
        
        if [ $index -le $mid ]; then
            update_recursive $left_child $start $mid $index $value
        else
            update_recursive $right_child $((mid + 1)) $end $index $value
        fi

        segment_tree[$node]=$(( segment_tree[$left_child] + segment_tree[$right_child] ))
    fi
}

# Example usage
initialize_tree 1 3 5 7 9 11

echo "Segment Tree: ${segment_tree[@]}"

# Query the sum of the range [1, 3]
echo "Sum of range [1, 3]: $(range_query 1 3)"

# Update index 1 to value 10
update_tree 1 10
echo "Segment Tree after update: ${segment_tree[@]}"

# Query the sum of the range [1, 3] again
echo "Sum of range [1, 3] after update: $(range_query 1 3)"
    

Explanation

The program implements a basic Segment Tree with the following components:

Initialization

The initialize_tree function sets up the Segment Tree for a given array. It calculates the size of the array and calls the build_tree function to recursively build the Segment Tree.

Building the Tree

The build_tree function recursively divides the array into segments and stores the sum of each segment in the Segment Tree. The leaves of the tree represent individual elements of the array, and each internal node represents the sum of a range of elements.

Range Queries

The range_query function queries the Segment Tree to find the sum of elements within a specified range. It calls the query_tree function, which recursively checks if the current segment overlaps with the query range and returns the appropriate sum.

Updating the Tree

The update_tree function updates the Segment Tree when an element in the array changes. It calls the update_recursive function, which recursively updates the value in the tree and recalculates the sums of the affected segments.

Example Usage

The example usage section demonstrates how to initialize a Segment Tree with an array of six elements, perform a range query on the sum of elements from index 1 to 3, update an element in the array, and perform the range query again to see the updated sum. The program outputs the Segment Tree structure and the results of the queries.

Conclusion

This Bash implementation of a Segment Tree provides a powerful tool for efficiently handling range queries and updates on an array. Segment Trees are particularly useful in scenarios where we need to perform multiple range queries and updates, such as in interval management, statistical analysis, and gaming applications.