Эффективный метод ранжирования проблемы запроса python3

Question

Я пытался задать вопрос с диапазоном в хакерранке ( 1 ). Я использовал дерево сегментов, чтобы решить эту проблему, но мой код не был эффективным. Мне нужно уточнить проблемы с моим кодом и найти более эффективное решение с python3. Какие есть другие подходы к решению этой проблемы. Какой самый эффективный подход.

Вот мой код.

import sys
from math import ceil,log2 
INT_MAX = sys.maxsize

def getMid(s, e) : 
    return s + (e - s) // 2

def RMQUtil( st, ss, se, qs, qe, index) : 
    if (qs <= ss and qe >= se) : 
        return st[index]
    if (se < qs or ss > qe) : 
        return INT_MAX 
    mid = getMid(ss, se) 
    a = RMQUtil(st, ss, mid, qs, qe, 2 * index + 1)
    b = RMQUtil(st, mid + 1, se, qs, qe, 2 * index + 2)
    return min(a, b, a+b)
def RMQ( st, n, qs, qe) : 
    if (qs < 0 or qe > n - 1 or qs > qe) : 
        print("Invalid Input")
        return -1
    return RMQUtil(st, 0, n - 1, qs, qe, 0) 

def constructSTUtil(arr, ss, se, st, si) : 
    if (ss == se) : 
        st[si] = arr[ss]
        return arr[ss]
    mid = getMid(ss, se)
    a = constructSTUtil(arr, ss, mid, st, si * 2 + 1)
    b = constructSTUtil(arr, mid + 1, se, st, si * 2 + 2)
    st[si] = min(a, b, a+b)   
    return st[si] 

def constructST( arr, n) : 
    x = (int)(ceil(log2(n)))
    max_size = 2 * (int)(2**x) - 1
    st = [0] * (max_size) 
    constructSTUtil(arr, 0, n - 1, st, 0) 
    return st

def update(n, st, k, v):
    def inner(si, ss, se):
        if k < ss or k > se:
            return
        if ss == se:
            st[si] = v
            return
        mid = getMid(ss, se)
        inner(2 * si +1, ss, mid)
        inner(2 * si +2, mid + 1, se)
        st[si] = min(st[2 * si +1], st[2 * si +2], st[2 * si +1] + st[2 * si +2])
    inner(0, 0, n-1)


if __name__ == "__main__" :
    for _ in range(int(input())):
        n = int(input())
        arr = [int(i) for i in input().split()] 
        st = constructST(arr, n)
        for _ in range(int(input())):
            a, x, y = [int(i) for i in input().split()]
            if a == 1:
                qs = x-1
                qe = y-1 
                print(RMQ(st, n, qs, qe)) 
            elif a == 0:
                if arr[x - 1] != y:
                    update(n, st, x-1, y)