# Segment Tree for RQM
class RMQ:
    N    # 满二叉树的节点数
    n    # 数列的元素数量 = 叶子节点的数量
    minv # 记录最小值的数列

    # 对所需的最低限度数量的数列元素进行初始化
    init(len): 
        n ← 1
        while n < len:
            n ← n*2  # 叶子节点的数量 n 乘以 2 的幂
        N ← 2*n - 1  # 调整满二叉树的节点数量 
        for i ← 0 to N-1:
            minv[i] ← INF

    # 求区间[a, b)的最小值		 
    findMin(a, b):
        return query(a, b, 0, 0, n)

    query(a, b, k, l, r):
        if r ≤ a or b ≤ l:
            res ← INF
        else if a ≤ l and r ≤ b:
            res ← minv[k]
        else:
            vl ← query(a, b, left(k), l, (l+r)/2)
            vr ← query(a, b, right(k), (l+r)/2, r)
            res ← min(vl, vr)

        return res

    # 将第 k 个元素的值替换为 x
    update(k, x):
        k ← k + n - 1
        minv[k] ← x

        while  k > 0:
            k ← parent(k)
            minv[k] ← min(minv[left(k)], minv[right(k)])

    left(k):
        return 2*k + 1

    right(k):
        return 2*k + 2

    parent(k):
        return (k - 1)/2