maximum fenwick tree more info https cpalgorithms comdatastructuresfenwick html ft maxfenwicktree5 ft query0 5 0 ft update4 100 ft query0 5 100 ft update4 0 ft update2 20 ft query0 5 20 ft update4 10 ft query2 5 20 ft query1 5 20 ft update2 0 ft query0 5 10 ft maxfenwicktree10000 ft update255 30 ft query0 10000 30 ft maxfenwicktree6 ft update5 1 ft query5 6 1 ft maxfenwicktree6 ft update0 1000 ft query0 1 1000 create empty maximum fenwick tree with specified size parameters size size of array returns none get next index in o1 get previous index in o1 set index to value in olg2 n parameters index index to update value value to set returns none answer the query of maximum range l r in olg2 n parameters left left index of query range inclusive right right index of query range exclusive returns maximum value of range left right maximum fenwick tree more info https cp algorithms com data_structures fenwick html ft maxfenwicktree 5 ft query 0 5 0 ft update 4 100 ft query 0 5 100 ft update 4 0 ft update 2 20 ft query 0 5 20 ft update 4 10 ft query 2 5 20 ft query 1 5 20 ft update 2 0 ft query 0 5 10 ft maxfenwicktree 10000 ft update 255 30 ft query 0 10000 30 ft maxfenwicktree 6 ft update 5 1 ft query 5 6 1 ft maxfenwicktree 6 ft update 0 1000 ft query 0 1 1000 create empty maximum fenwick tree with specified size parameters size size of array returns none get next index in o 1 get previous index in o 1 set index to value in o lg 2 n parameters index index to update value value to set returns none answer the query of maximum range l r in o lg 2 n parameters left left index of query range inclusive right right index of query range exclusive returns maximum value of range left right because of right is exclusive
class MaxFenwickTree:
    

    def __init__(self, size: int) -> None:
        
        self.size = size
        self.arr = [0] * size
        self.tree = [0] * size

    @staticmethod
    def get_next(index: int) -> int:
        
        return index | (index + 1)

    @staticmethod
    def get_prev(index: int) -> int:
        
        return (index & (index + 1)) - 1

    def update(self, index: int, value: int) -> None:
        
        self.arr[index] = value
        while index < self.size:
            current_left_border = self.get_prev(index) + 1
            if current_left_border == index:
                self.tree[index] = value
            else:
                self.tree[index] = max(value, current_left_border, index)
            index = self.get_next(index)

    def query(self, left: int, right: int) -> int:
        
        right -= 1  
        result = 0
        while left <= right:
            current_left = self.get_prev(right)
            if left <= current_left:
                result = max(result, self.tree[right])
                right = current_left
            else:
                result = max(result, self.arr[right])
                right -= 1
        return result


if __name__ == "__main__":
    import doctest

    doctest.testmod()