SegmentTree.py

# st = SegmentTree(n, lambda a,b: a if a > b else b)
class SegmentTree:
    def __init__(self,n,f):
        self.N = 1
        self.f = f
        while(self.N < n):
            self.N *= 2
        self.seg = [0] * (self.N * 2 -1)

    def update(self,k,a):
        k += self.N - 1
        self.seg[k] = a

        while(0 < k):
            k = (k-1)//2;
            self.seg[k] = self.f(self.seg[2*k +1], self.seg[2*k + 2])

    def _query(self,a, b, k, l, r):
        if r <= a or b <= l:
            return 0
        if a <= l and r <= b:
            return self.seg[k]
        else:
            vl = self._query(a, b, k * 2 + 1, l, (l + r)//2)
            vr = self._query(a, b, k * 2 + 2, (l + r)//2, r)
            return self.f(vl,vr)
    
    def query(self, a, b):
        return self._query(a, b, 0, 0, self.N)