Segment Tree

arr = [0]*100005
seg = [0] * (4 * 100005)
 
def build(idx, low, high):
    if low == high:
        seg[idx] = arr[low]
        return 
 
    mid = (low + high) // 2;
    build(2*idx+1, low, mid)
    build(2*idx+2, mid + 1, high)
 
    seg[idx] = max(seg[2*idx+1], seg[2*idx+2])
 
def query(idx, low, high, l, r):
    if low >= l and high <= r:
        return seg[idx]
 
    if high < l or low > r:
        return float('-inf')
 
    mid = (low + high) // 2
    left = query(2*idx+1, low, mid, l, r)
    right = query(2*idx+2, mid + 1, high, l, r)
 
    return max(left, right)
 
if __name__ == "__main__":
    ar = [1, 3, 4, 6, 5, 9, 8]
    for i in range(len(ar)):
        arr[i] = ar[i]
    n = len(ar)
 
    build(0, 0, n-1)
    print(query(0, 0, n-1, 1, 3))
 

Youtube