Fenwick Tree (Binary Indexed Tree) Implementation in Go

A Fenwick Tree, also known as a Binary Indexed Tree (BIT), is a data structure that provides efficient methods for cumulative frequency tables or prefix sums. It allows querying prefix sums and updating individual elements in logarithmic time, making it highly efficient for dynamic cumulative frequency tables.

Program Structure

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

1. FenwickTree Struct: This struct represents the Fenwick Tree, containing a slice that stores the tree data.
2. NewFenwickTree Function: This function initializes a new Fenwick Tree with a specified size.
3. Update Method: This method updates the tree by adding a value to a specific index.
4. PrefixSum Method: This method returns the prefix sum up to a given index.
5. RangeSum Method: This method calculates the sum of elements in a specific range.

Go Code Implementation

package main

import "fmt"

// FenwickTree represents a Fenwick Tree (Binary Indexed Tree)
type FenwickTree struct {
    tree []int
    size int
}

// NewFenwickTree creates a new Fenwick Tree of a given size
func NewFenwickTree(size int) *FenwickTree {
    return &FenwickTree{
        tree: make([]int, size+1), // We use 1-based indexing
        size: size,
    }
}

// Update adds a value to the element at index idx
func (ft *FenwickTree) Update(idx, value int) {
    for idx <= ft.size { ft.tree[idx] += value idx += idx & -idx // Move to the next index } } // PrefixSum returns the prefix sum up to and including index idx func (ft *FenwickTree) PrefixSum(idx int) int { sum := 0 for idx > 0 {
        sum += ft.tree[idx]
        idx -= idx & -idx // Move to the parent index
    }
    return sum
}

// RangeSum returns the sum of elements in the range [left, right]
func (ft *FenwickTree) RangeSum(left, right int) int {
    return ft.PrefixSum(right) - ft.PrefixSum(left-1)
}

func main() {
    // Create a Fenwick Tree with 10 elements
    fenwick := NewFenwickTree(10)

    // Update the tree with some values
    fenwick.Update(1, 5)
    fenwick.Update(2, 3)
    fenwick.Update(3, 7)
    fenwick.Update(4, 6)
    fenwick.Update(5, 5)

    // Print prefix sums
    fmt.Println("Prefix sum up to index 5:", fenwick.PrefixSum(5)) // Output: 26

    // Print range sum from index 2 to 4
    fmt.Println("Range sum from index 2 to 4:", fenwick.RangeSum(2, 4)) // Output: 16
}
    

Explanation of the Code

Here’s a breakdown of the code:

• FenwickTree Struct: The FenwickTree struct represents the Binary Indexed Tree and stores the data in a slice called tree. The tree uses 1-based indexing for simplicity.
• NewFenwickTree Function: This function initializes a new Fenwick Tree with a given size. The tree slice is initialized with a size of size + 1 to accommodate 1-based indexing.
• Update Method: This method updates the tree by adding a value to the element at the specified index. It iterates over the relevant tree nodes by repeatedly adding the value and moving to the next index using the formula idx += idx & -idx.
• PrefixSum Method: This method calculates the prefix sum up to and including a given index by iterating over the tree nodes using the formula idx -= idx & -idx to move to the parent index.
• RangeSum Method: This method calculates the sum of elements in a specified range by subtracting the prefix sum of the left boundary from the prefix sum of the right boundary.

Usage Example

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

func main() {
    // Create a Fenwick Tree with 10 elements
    fenwick := NewFenwickTree(10)

    // Update the tree with some values
    fenwick.Update(1, 5)
    fenwick.Update(2, 3)
    fenwick.Update(3, 7)
    fenwick.Update(4, 6)
    fenwick.Update(5, 5)

    // Print prefix sums
    fmt.Println("Prefix sum up to index 5:", fenwick.PrefixSum(5)) // Output: 26

    // Print range sum from index 2 to 4
    fmt.Println("Range sum from index 2 to 4:", fenwick.RangeSum(2, 4)) // Output: 16
}
    

Conclusion

This Go program demonstrates a basic implementation of a Fenwick Tree (Binary Indexed Tree), a powerful data structure for efficiently calculating prefix sums and performing range queries. The Fenwick Tree is particularly useful in scenarios where dynamic cumulative frequency tables are required, such as in financial analysis, cumulative histograms, and other data aggregation tasks.