Fenwick Tree for Maximum

fenwick_tree_for_max.py

class FenwickTreeMax(object):
    """
    Fenwick Tree for Max
    """
    def __init__(self, nums):
        """
        Initialize tree
        """
        self.n = len(nums)
        self.left = [0] * (self.n + 1)
        self.right = [0] * (self.n + 1)
        self.nums = nums

        for i, k in enumerate(self.nums):
            self.add(i + 1, k)

    def add(self, n, x):
        """
        Adds a number
        """
        i = n
        while i <= self.n:
            self.left[i] = max(self.left[i], x)
            i += self.lowbit(i)
        j = n
        while j > 0:
            self.right[j] = max(self.right[j], x)
            j -= self.lowbit(j)

    def lowbit(self, x):
        """
        Calculates an index
        """
        return x & -x

    def max_range(self, begin, end):
        """
        Returns max number in range
        """
        res = 0
        if begin == 0 or end == 0:
            return res

        i = begin
        while i + self.lowbit(i) <= end:
            res = max(res, self.right[i])
            i += self.lowbit(i)
        res = max(res, self.nums[i - 1])
        j = end
        while j - self.lowbit(j) >= begin:
            res = max(res, self.left[j])
            j -= self.lowbit(j)
        return res