Maximum Fenwick Tree

A Maximum Fenwick Tree, also known as a Binary Indexed Tree (BIT), is a data structure that efficiently supports finding the maximum value in a prefix of an array and updating individual elements. It is an extension of the Fenwick Tree. Here's an example of implementing a Maximum Fenwick Tree in Python:


class MaxFenwickTree:
    def __init__(self, arr):
        self.arr = arr
        self.tree = [float('-inf')] + arr.copy()
        for i in range(1, len(arr)):
            j = i + self._lsb(i)
            if j < len(arr):
                self.tree[j] = max(self.tree[j], self.tree[i])
    
    def _lsb(self, x):
        return x & -x
    
    def update(self, idx, value):
        while idx < len(self.tree):
            self.tree[idx] = max(self.tree[idx], value)
            idx += self._lsb(idx)
    
    def get_max(self, idx):
        result = float('-inf')
        while idx > 0:
            result = max(result, self.tree[idx])
            idx -= self._lsb(idx)
        return result

# Create a Maximum Fenwick Tree
arr = [3, 2, 5, 1, 6, 4]
fenwick_tree = MaxFenwickTree(arr)

# Perform updates and get maximum values
fenwick_tree.update(2, 7)
fenwick_tree.update(4, 9)

print("Maximum value in prefix [1]:", fenwick_tree.get_max(1))
print("Maximum value in prefix [1, 4]:", fenwick_tree.get_max(4))

 In this example, we define a MaxFenwickTree class with methods for building the tree, updating values, and getting the maximum value in a prefix. The tree is constructed by initializing the tree array with negative infinity values and then updating the appropriate indices with the maximum value. The update method updates an element in the tree and propagates the changes to the subsequent nodes. The get_max method retrieves the maximum value in a prefix by traversing the tree in a specific pattern. We create a Maximum Fenwick Tree, perform updates, and retrieve maximum values.

Next Post Previous Post