Fenwick Trees

Fenwick Trees, also known as Binary Indexed Trees (BIT), are data structures that provide efficient methods for prefix sum queries and updates on an array of numbers. They allow both operations to be performed in $O(\log n)$ time. Here is an implementation of a Fenwick Tree in Go:

Fenwick Tree Implementation

1. Initialization: Construct the tree based on the input array.
2. Update: Update the value of an element and propagate the changes through the tree.
3. Query: Calculate prefix sums and range sums efficiently.

Here's a complete implementation:

go
package main

import (
	"fmt"
)

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

// NewFenwickTree initializes a Fenwick Tree with a given size
func NewFenwickTree(size int) *FenwickTree {
	return &FenwickTree{
		tree: make([]int, size+1),
		n:    size,
	}
}

// Update increases the value at index `i` by `value`
func (ft *FenwickTree) Update(i, value int) {
	i++ // Fenwick Tree is 1-indexed
	for i <= ft.n {
		ft.tree[i] += value
		i += i & -i
	}
}

// PrefixSum computes the prefix sum from index 0 to `i`
func (ft *FenwickTree) PrefixSum(i int) int {
	i++ // Fenwick Tree is 1-indexed
	sum := 0
	for i > 0 {
		sum += ft.tree[i]
		i -= i & -i
	}
	return sum
}

// RangeSum computes the sum of the range [left, right]
func (ft *FenwickTree) RangeSum(left, right int) int {
	if left > 0 {
		return ft.PrefixSum(right) - ft.PrefixSum(left-1)
	}
	return ft.PrefixSum(right)
}

func main() {
	arr := []int{1, 7, 3, 0, 7, 8, 3, 2, 6, 2}
	n := len(arr)
	ft := NewFenwickTree(n)

	// Build the Fenwick Tree with initial values
	for i, value := range arr {
		ft.Update(i, value)
	}

	fmt.Println("Fenwick Tree Range Sum Queries:")
	fmt.Printf("Sum of range [0, 5]: %d\n", ft.RangeSum(0, 5))
	fmt.Printf("Sum of range [3, 8]: %d\n", ft.RangeSum(3, 8))
	fmt.Printf("Sum of range [1, 7]: %d\n", ft.RangeSum(1, 7))

	// Update an element and query again
	ft.Update(3, 5) // arr[3] += 5
	fmt.Println("After updating arr[3] by +5:")
	fmt.Printf("Sum of range [0, 5]: %d\n", ft.RangeSum(0, 5))
	fmt.Printf("Sum of range [3, 8]: %d\n", ft.RangeSum(3, 8))
	fmt.Printf("Sum of range [1, 7]: %d\n", ft.RangeSum(1, 7))
}

Explanation

1. Initialization:

   • We create a FenwickTree structure with an internal slice tree to hold the data. The size of the tree slice is size + 1 because Fenwick Trees are typically implemented using 1-based indexing for easier manipulation with bitwise operations.

2. Update Operation:

   • The Update method increases the value at a given index i by value. It then propagates this change through the tree to ensure all relevant sums are updated. The bitwise operation i += i & -i efficiently moves to the next index that needs to be updated.

3. Prefix Sum Operation:

   • The PrefixSum method calculates the sum of elements from the start of the array up to index i. It traverses the tree from the given index to the root, summing up the values stored in the tree. The bitwise operation i -= i & -i efficiently moves to the parent index.

4. Range Sum Operation:

   • The RangeSum method calculates the sum of elements in a given range [left, right] using the PrefixSum method. If left is greater than 0, it subtracts the prefix sum up to left - 1 from the prefix sum up to right to get the sum of the specified range.

Usage

• The main function demonstrates how to initialize a Fenwick Tree with an array, perform range sum queries, and update an element's value in the array. After updating, it queries the range sums again to show the updated results.

Fenwick Trees are highly efficient for scenarios where you need to perform frequent prefix sum or range sum queries and updates on an array.