Fenwick Tree

Example: Let's consider an example to understand Fenwick Tree better. We'll create a Fenwick Tree and perform update and prefix sum operations on it.

# Function to initialize Fenwick Tree
def initialize_tree(nums):
    n = len(nums)
    tree = [0] * (n + 1)
    
    for i in range(n):
        update(tree, i, nums[i])
    
    return tree

# Function to update a value in the Fenwick Tree
def update(tree, index, value):
    index += 1
    
    while index < len(tree):
        tree[index] += value
        index += index & -index

# Function to calculate the prefix sum of a range in the Fenwick Tree
def prefix_sum(tree, index):
    index += 1
    result = 0
    
    while index > 0:
        result += tree[index]
        index -= index & -index
    
    return result

# Create an array
nums = [1, 2, 3, 4, 5]

# Initialize the Fenwick Tree
tree = initialize_tree(nums)

# Update value at index 2 to 10
update(tree, 2, 10)

# Calculate prefix sum of values in the range [1, 3]
range_sum = prefix_sum(tree, 3) - prefix_sum(tree, 0)

print("Fenwick Tree:", tree)
# Output: Fenwick Tree: [0, 1, 3, 13, 10, 15]

print("Prefix Sum of Range [1, 3]:", range_sum)
# Output: Prefix Sum of Range [1, 3]: 17

In this example, we define three functions: initialize_tree, update, and prefix_sum.

The initialize_tree function takes an array nums as input and initializes the Fenwick Tree. It creates a tree list with an extra element at the beginning, initializes all elements to 0, and then calls the update function to populate the tree with the values from the nums array.

The update function updates a value at a specific index in the Fenwick Tree. It takes the tree list, index, and value as input. It uses a while loop to iterate through the tree, adding the value to each node that covers the index. It updates the index by adding the least significant bit (LSB) of the index.

The prefix_sum function calculates the prefix sum of a range of values in the Fenwick Tree. It takes the tree list and index as input. It uses a while loop to iterate through the tree, adding the values of each node that cover the range to the result. It updates the index by subtracting the LSB of the index.

In the main code, we create an array nums with values [1, 2, 3, 4, 5]. We then initialize the Fenwick Tree using the initialize_tree function.

Next, we update the value at index 2 to 10 using the update function.

Finally, we calculate the prefix sum of the values in the range [1, 3] using the prefix_sum function and print the result.

The time complexity of the update and prefix sum operations in the Fenwick Tree is O(log n), where n is the number of elements in the array. The space complexity of the Fenwick Tree is O(n), where n is the number of elements in the array.

Let's use a example to explain the concept of Fenwick Tree. The problem is "Range Sum Query - Mutable".

Problem Statement: Given an integer array nums, we need to implement two operations:

1. update(i, val): Update the value of nums[i] to be val.
2. sumRange(i, j): Return the sum of the elements in the array from index i to j (inclusive).

Example:

class NumArray:
    def __init__(self, nums):
        self.nums = nums
        self.tree = [0] * (len(nums) + 1)
        for i in range(len(nums)):
            self._update(i, nums[i])

    def _update(self, index, value):
        index += 1
        while index < len(self.tree):
            self.tree[index] += value
            index += index & -index

    def update(self, i, val):
        diff = val - self.nums[i]
        self.nums[i] = val
        self._update(i, diff)

    def _prefix_sum(self, index):
        index += 1
        result = 0
        while index > 0:
            result += self.tree[index]
            index -= index & -index
        return result

    def sumRange(self, i, j):
        return self._prefix_sum(j) - self._prefix_sum(i - 1)

# Test the implementation
nums = [1, 3, 5]
obj = NumArray(nums)
print(obj.sumRange(0, 2))  # Output: 9
obj.update(1, 2)
print(obj.sumRange(0, 2))  # Output: 8

In this example, we define a class NumArray to solve the "Range Sum Query - Mutable" problem using Fenwick Tree.

The constructor __init__ initializes the nums array and creates a Fenwick Tree with an extra element at the beginning. It then populates the Fenwick Tree by calling the _update function for each element in nums.

The _update function updates a value at a specific index in the Fenwick Tree. It uses a while loop to iterate through the tree, adding the value to each node that covers the index. It updates the index by adding the least significant bit (LSB) of the index.

The update function updates the value at index i in both the nums array and the Fenwick Tree. It calculates the difference between the new value and the original value and calls the _update function to update the Fenwick Tree accordingly.

The _prefix_sum function calculates the prefix sum of a range of values in the Fenwick Tree. It uses a while loop to iterate through the tree, adding the values of each node that cover the range to the result. It updates the index by subtracting the LSB of the index.

The sumRange function calculates the sum of elements in the array from index i to j (inclusive) by subtracting the prefix sum at index i-1 from the prefix sum at index j.

In the main code, we create an instance of the NumArray class with the nums array [1, 3, 5]. We then call the sumRange function to compute the sum of the elements from index 0 to 2, which gives the output 9.

Next, we update the value at index 1 to 2 using the update function. Finally, we call the sumRange function again to compute the sum of the elements from index 0 to 2, which gives the output 8.

The time complexity for both the update and sumRange operations in the Fenwick Tree implementation is O(log n), where n is the number of elements in the array. The space complexity is O(n), where n is the number of elements in the array.