RangeMinimumQuery, RangeMaximumQuery, BitIndexTree coded by Python

I show the RangeMinimumQuery, RangeMaximumQuery and BitIndexTree python class implementations.

RangeMinimumQuery and RangeMaximumQuery are data structures for faster obtaining the minimum and maximum value of sub sequential array.

BitIndexTree is a data structure for faster obtaining the summation of sub sequential array whose head is a 0-index element.

RangeMinimumQuery and RangeMaximumQuery

def near_pow2(n):
    ret = 1
    while ret < n:
        ret <<= 1
    return ret


class RangeMinimumQuery:
    def __init__(self, a):
        self.n = near_pow2(len(a))
        self.rmq = [float("inf")] * (2 * self.n - 1)
        for i in range(len(a)):
            self.update(i, a[i])

    def min(self, a, b):
        return self.__min(a, b, 0, 0, self.n)

    def __min(self, a, b, k, l, r):
        if r <= a or b <= l:
            return float("inf")
        elif a <= l and r <= b:
            return self.rmq[k] 
        else:
            vl = self.__min(a, b, (k << 1) + 1, l, (l + r) >> 1)
            vr = self.__min(a, b, (k << 1) + 2, (l + r) >> 1, r)
            return min(vl, vr)

    def update(self, k, x):
        k += self.n - 1
        self.rmq[k] = x
        while k > 0:
            k = (k - 1) >> 1
            self.rmq[k] = min(self.rmq[(k << 1) + 1], self.rmq[(k << 1) + 2])

    def __str__(self):
        return str(self.rmq)

    def __repr__(self):
        return f"RangeMinimumQuery({self.rmq})"


class RangeMaximumQuery:
    def __init__(self, a):
        self.n = near_pow2(len(a))
        self.rmq = [float("-inf")] * (2 * self.n - 1)
        for i in range(len(a)):
            self.update(i, a[i])

    def max(self, a, b):
        return self.__max(a, b, 0, 0, self.n)

    def __max(self, a, b, k, l, r):
        if r <= a or b <= l:
            return float("-inf")
        elif a <= l and r <= b:
            return self.rmq[k] 
        else:
            vl = self.__max(a, b, (k << 1) + 1, l, (l + r) >> 1)
            vr = self.__max(a, b, (k << 1) + 2, (l + r) >> 1, r)
            return max(vl, vr)

    def update(self, k, x):
        k += self.n - 1
        self.rmq[k] = x
        while k > 0:
            k = (k - 1) >> 1
            self.rmq[k] = max(self.rmq[(k << 1) + 1], self.rmq[(k << 1) + 2])

    def __str__(self):
        return str(self.rmq)

    def __repr__(self):
        return f"RangeMaximumQuery({self.rmq})"



if __name__ == "__main__":
    source = [1, 2, 3, 4]
    rmq = RangeMinimumQuery(source)
    print(source, "min", 0, "--", 1, "=", rmq.min(0, 1))
    print(source, "min", 1, "--", 2, "=", rmq.min(1, 2))
    print(source, "min", 1, "--", 3, "=", rmq.min(1, 3))

    source = [1, 2, 3, 4]
    rmq = RangeMaximumQuery(source)
    print(source, "max", 0, "--", 1, "=", rmq.max(0, 1))
    print(source, "max", 1, "--", 2, "=", rmq.max(1, 2))
    print(source, "max", 1, "--", 3, "=", rmq.max(1, 3))

BitIndexTree

def near_pow2(n):
    ret = 1;
    while ret < n:
        ret <<= 1
    return ret;


class BinaryIndexTree:
    def __init__(self, a):
        self.n = near_pow2(len(a))
        self.bit = [None] + [0] * self.n
        for i in range(len(a)):
            self.add(i, a[i])

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, x):
        i += 1
        while i <= self.n:
            self.bit[i] += x
            i += i & -i

    def __str__(self):
        return str(self.bit)

    def __repr__(self):
        return f"BinaryIndexTree({self.bit})"


if __name__ == "__main__":
    bit = BinaryIndexTree([1, 2, 3, 4])
    print(bit)
    print(1, bit.sum(1))
    print(2, bit.sum(2))
    print(3, bit.sum(3))
    print(4, bit.sum(4))

    bit = BinaryIndexTree([1, 2, 3])
    print(bit)
    print(1, bit.sum(1))
    print(2, bit.sum(2))
    print(3, bit.sum(3))