Problem:
Range Minimum Query (RMQ) Write a program which manipulates a sequence A = { a 0 , a 1 , . . .  , a n-1 } with the following operations:  find(s, t) : report the minimum element in a s , a s+1 , . . . ,a t .  update(i, x) : change a i to x .  Note that the initial values of a i ( i = 0, 1, . . .  , n−1 ) are  2 31 -1. Input  n  q  com 0  x 0  y 0  com 1  x 1  y 1 ... com q−1  x q−1  y q−1  In the first line, n (the number of elements in A ) and q (the number of queries) are given. Then, q queries are given where com represents the type of queries. '0' denotes update(x i , y i ) and '1' denotes find(x i , y i ) . Output For each find operation, print the minimum element. Constraints   1 ≤ n ≤ 100000    1 ≤ q ≤ 100000   If com i is 0, then 0 ≤ x i < n , 0 ≤ y i < 2 31 -1 .  If com i is 1, then 0 ≤ x i < n , 0 ≤ y i < n .  Sample Input 1 3 5
0 0 1
0 1 2
0 2 3
1 0 2
1 1 2 Sample Output 1 1
2 Sample Input 2 1 3
1 0 0
0 0 5
1 0 0 Sample Output 2 2147483647
5

Solution (Python):

import sys
input = sys.stdin.readline

n, q = map(int, input().split())

class RMQ:
    def __init__(self, n, e):
        
        self.e = e
        
        self.num_min =2**(n-1).bit_length()
        self.seg_min=[self.e]*2*self.num_min

    def init_min(self, init_min_val):
        
        
        for i in range(n):
            self.seg_min[i+self.num_min-1]=init_min_val[i]
        
        for i in range(self.num_min-2,-1,-1) :
            self.seg_min[i]=min(self.seg_min[2*i+1],self.seg_min[2*i+2])

    def update_min(self, k, x):
        k += self.num_min-1
        self.seg_min[k] = x
        while k:
            k = (k-1)//2
            self.seg_min[k] = min(self.seg_min[k*2+1],self.seg_min[k*2+2])

    def query_min(self, p, q):
        q += 1
        if q<=p:
            return self.e
        p += self.num_min-1
        q += self.num_min-2
        res=self.e
        while q-p>1:
            if p&1 == 0:
                res = min(res,self.seg_min[p])
            if q&1 == 1:
                res = min(res,self.seg_min[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = min(res,self.seg_min[p])
        else:
            res = min(min(res,self.seg_min[p]),self.seg_min[q])
        return res

e = (2**31) - 1
rmq = RMQ(n, e)

for i in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        rmq.update_min(x, y)
    else:
        ans = rmq.query_min(x, y)
        print(ans)

Solution (Python):
class segmentTreeMin():
    
    inf = 2**31 - 1
    dat = []
    lenData = -1

    def __init__(self):
        pass

    def load(self, l):
        
        self.lenData = 2 ** (len(l) - 1).bit_length()  
        self.dat = [self.inf] * (self.lenData * 2)
        
        for i in range(len(l)):
            self.dat[self.lenData - 1 + i] = l[i]
        self.build()

    def build(self):
        for i in range(self.lenData - 2, -1, -1):
            self.dat[i] = min(self.dat[2 * i + 1], self.dat[2 * i + 2])

    def setValue(self, i, a):
        """
        set a to list[i]
        """
        
        nodeId = (self.lenData - 1) + i
        
        self.dat[nodeId] = a
        while nodeId != 0:
            nodeId = (nodeId - 1) // 2
            
            self.dat[nodeId] = min(self.dat[nodeId * 2 + 1], self.dat[nodeId * 2 + 2])

    def querySub(self, a, b, nodeId, l, r):
        """
        [a,b) 区間の親クエリに対するノードnodeへ[l, r)の探索をデリゲート
        区間については、dataの添え字は0,1,2,3,4としたときに、
        [0,3)なら0,1,2の結果を返す
        """
        
        if (r <= a or b <= l):
            return self.inf
        if a <= l and r <= b:
            
            return self.dat[nodeId]
        resLeft = self.querySub(a, b, 2 * nodeId + 1, l, (l + r) // 2)
        resRight = self.querySub(a, b, 2 * nodeId + 2, (l + r) // 2, r)
        
        return min(resLeft, resRight)

    def query(self, a, b):
        return self.querySub(a, b, 0, 0, self.lenData)


initVal = 2**31 - 1
n, q = map(int, input().split())
dat = [initVal] * n
stm = segmentTreeMin()
stm.load(dat)
stm.build()
for _ in range(q):
    cmd, a, b = map(int, input().split())
    if cmd == 0: 
        stm.setValue(a, b)
    else:
        print(stm.query(a, b+1))

Solution (Python):
INF = 2 ** 31 - 1


class SegmentTree:
    """
    参考: https://www.creativ.xyz/segment-tree-abstraction-979/
    """
    n = 1
    data = None  
    def_ = None  

    def __init__(self, n, _def=INF, _operation=min, _update=lambda x, y: y):
        """
        _def は イミュータブルな値を想定
        """
        self.n = 1
        while self.n < n:
            self.n *= 2
        self.data = [INF for _ in range(self.n * 2 - 1)]

        self.operation = _operation
        self.update = _update
        self.def_ = _def

    def change(self, i, x):
        i += self.n - 1
        self.data[i] = self.update(self.data[i], x)
        while i > 0:
            i = (i - 1) // 2
            self.data[i] = self.operation(self.data[i * 2 + 1], self.data[i * 2 + 2])

    def _query(self, a, b, k, l, r):
        """
        区間 [a,b) のクエリ, コール時はノード k=[l, r) に着目. (蟻本 p.155)
        """
        
        if r <= a or b <= l: return self.def_

        
        if a <= l and r <= b: return self.data[k]

        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.operation(vl, vr)

    def query(self, a, b):
        """
        [a, b) 区間のクエリ
        """
        return self._query(a, b, 0, 0, self.n)

    def get(self, i):
        """
        添字アクセスの代わり
        """
        return self.data[i + self.n - 1]


n, q = [int(_) for _ in input().split()]
seg_t = SegmentTree(n)
for i in range(q):
    c, x, y = [int(_) for _ in input().split()]
    if c == 0:
        seg_t.change(x, y)
    else:
        print(seg_t.query(x, y + 1))

Solution (Python):
import sys
input = sys.stdin.readline

class SegmentTree():
    def __init__(self,arr,func=min,ie=2**63-1):
        self.n = 2**(len(arr)-1).bit_length()
        self.ie = ie
        self.func = func
        self.tree = [ie for _ in range(2*self.n)]
        for i in range(len(arr)):
            self.tree[self.n+i-1] = arr[i]
        for i in range(self.n-1)[::-1]:
            self.tree[i] = func(self.tree[2*i+1],self.tree[2*i+2])
    def update(self,index,x): 
        index += self.n-1
        self.tree[index] = x
        while index>0:
            index = (index-1)//2
            self.tree[index] = self.func(self.tree[2*index+1],self.tree[2*index+2])
    def query(self,left,right): 
        if right <= left:
            return self.ie
        left += self.n-1
        right += self.n-2
        res = self.ie
        while right-left > 1:
            if left & 1 == 0:
                res = self.func(res,self.tree[left])
            if right & 1 == 1:
                res = self.func(res,self.tree[right])
                right -= 1
            left = left//2
            right = (right-1)//2
        if left == right:
            res = self.func(res,self.tree[left])
        else:
            res = self.func(self.func(res,self.tree[left]),self.tree[right])
        return res

N,Q = map(int,input().split())
ans = []
A = [2**31-1 for _ in range(N)]
sg = SegmentTree(A)
for _ in range(Q):
    c,x,y = map(int,input().split())
    if c==0:
        sg.update(x,y)
    else:
        ans.append(sg.query(x,y+1))
print(*ans,sep='\n')

Solution (Python):
class SegmentTree:
    def __init__(self, array, seg_func, ide_ele):
        n = len(array)
        self.size = 2**(n - 1).bit_length()
        self.seg_func = seg_func
        self.ide_ele = ide_ele
        self.seg = [self.ide_ele] * (2 * self.size - 1)

        for i in range(n):
            self.seg[i + self.size - 1] = array[i]
        for i in range(self.size - 2, -1, -1):
            self.seg[i] = self.seg_func(self.seg[2 * i + 1], self.seg[2 * i + 2])

    def update(self, index, value):
        index += self.size - 1
        self.seg[index] = value
        while index:
            index = (index - 1) // 2
            self.seg[index] = self.seg_func(self.seg[index * 2 + 1], self.seg[index * 2 + 2])

    def query(self, lower_ep, upper_ep):
        if upper_ep <= lower_ep:
            return self.ide_ele
        lower_ep += self.size - 1
        upper_ep += self.size - 2
        res = self.ide_ele
        while (upper_ep - lower_ep) > 1:
            if lower_ep & 1 == 0:
                res = self.seg_func(res, self.seg[lower_ep])
            if upper_ep & 1 == 1:
                res = self.seg_func(res, self.seg[upper_ep])
                upper_ep -= 1

            lower_ep //= 2
            upper_ep = (upper_ep - 1) // 2
        if lower_ep == upper_ep:
            res = self.seg_func(res, self.seg[lower_ep])
        else:
            res = self.seg_func(self.seg_func(res, self.seg[lower_ep]), self.seg[upper_ep])
        return res


n, q = map(int, input().split())
seg = SegmentTree([2**31 - 1] * n, min, 2**31 - 1)
for _ in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        seg.update(x, y)
    if com == 1:
        print(seg.query(x, y + 1))

Solution (Python):
"""
http://tsutaj.hatenablog.com/entry/2017/03/29/204841
セグメント木について
高速で区間クエリを実施する方法
(基本的な最小化問題のセグ木)
区間[a,b)にある要素の最小値を答えることを考える
※ 半開区間であることに注意しよう

要求区間 : クエリの範囲
対象区間 : 各ノードがカバーしている区間

1. 要求区間と対象区間が交わらない場合
    操作を進めても無意味なので、影響のない適当な値を返す
2. 要求区間が対象区間を完全に被覆している
    対象区間は要求区間の計算に必要なので、現状の答えと比較・更新する
3. 要求区間が対象区間の一部を被覆している場合
    対象区間の子に当たる区間に移動して、完全に被覆するまで操作を行う

最上段から下がっていきながらが、値を取得する
"""

class SegmentTree:
    def __init__(self,v):
        """
        :param v:元配列
        """
        size = len(v)
        self.n = 1
        while self.n < size:
            self.n *= 2
        
        self.node = [0] * (2*self.n-1)
        
        for i, e in enumerate(v):
            self.node[i+self.n-1] = e
        
        for i in range(self.n-2,-1,-1):
            self.node[i] = min(self.node[2*i+1], self.node[2*i+2])

    def update(self, x, val):
        """
        :param x: インデックス
        :param val: 更新する値
        """
        
        x += (self.n-1)
        
        self.node[x] = val
        while(x > 0):
            x = (x-1) // 2
            self.node[x] = min(self.node[2*x+1],self.node[2*x+2])
    
    def getmin(self, a, b, k=0, l=0, r=-1):
        """
        :param a: 要求区間の左 [
        :param b: 要求区間の右 )
        :param k: 現在のインデックス
        :param l: 対象区間の左
        :param r: 対象区間の右
        """
        INF = 2**31-1
        
        if (r < 0): r = self.n        
        
        
        
        if (r<=a or b<=l): 
            return INF

        
        if (a <= l and r <= b): 
            return self.node[k]

        
        
        vl = self.getmin(a, b, 2*k+1, l, (l+r)//2)
        vr = self.getmin(a, b, 2*k+2, (l+r)//2, r)
        return min(vl, vr)

if __name__ == '__main__':
    """
    テストケース含問題
    """
    n,q  = map(int, input().split())
    v = [2**31-1] * n
    st = SegmentTree(v)
    A = []
    for i in range(q):
        com, x, y = map(int, input().split())
        if com == 0:   
            st.update(x,y)
        else:
            ans = st.getmin(x,y+1)
            print(ans)

Solution (Python):
class SegmentTree:
    """Segment Tree (Point Update & Range Query)

    Query
        1. update(i, val): update i-th value to val
        2. query(low, high): find f(value) in [low, high)

    Complexity
        time complexity: O(log n)
        space complexity: O(n)
    """

    def __init__(self, N, f, default):
        self.N = 1 << (N-1).bit_length()
        self.default = default
        self.f = f
        self.segtree = [self.default] * ((self.N << 1) - 1)

    @classmethod
    def create_from_array(cls, arr, f, default):
        N = len(arr)
        self = cls(N, f, default)
        for i in range(N):
            self.segtree[self.N - 1 + i] = arr[i]

        for i in reversed(range(self.N - 1)):
            self.segtree[i] = self.f(
                self.segtree[(i << 1) + 1], self.segtree[(i << 1) + 2])
        return self

    def update(self, i, val):
        i += self.N - 1
        self.segtree[i] = val
        while i > 0:
            i = (i - 1) >> 1
            self.segtree[i] = self.f(
                self.segtree[(i << 1)+1], self.segtree[(i << 1)+2])

    def query(self, low, high):
        
        low, high = low + self.N, high + self.N
        ret = self.default
        while low < high:
            if low & 1:
                ret = self.f(ret, self.segtree[low-1])
                low += 1
            if high & 1:
                high -= 1
                ret = self.f(ret, self.segtree[high-1])
            low, high = low >> 1, high >> 1
        return ret


def yosupo():
    
    _, Q = map(int, input().split())
    A = [int(x) for x in input().split()]
    rmq = SegmentTree.create_from_array(A, min, 10**9)
    for _ in range(Q):
        l, r = map(int, input().split())
        print(rmq.query(l, r))


def aoj():
    
    N, Q = map(int, input().split())
    default = (1 << 31) - 1
    rmq = SegmentTree(N, min, default)
    for _ in range(Q):
        com, x, y = map(int, input().split())
        if com == 0:
            rmq.update(x, y)
        else:
            print(rmq.query(x, y+1))


if __name__ == '__main__':
    
    aoj()

Solution (Python):
import operator
import os
import sys
from functools import reduce

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


class SegmentTree:
    
    def __init__(self, size, fn=operator.add, default=None, initial_values=None):
        """
        :param int size:
        :param callable fn: 区間に適用する関数。引数を 2 つ取る。min, max, operator.xor など
        :param default:
        :param list initial_values:
        """
        default = default or 0

        
        n = 1
        while n < size:
            n *= 2
        self._size = n
        self._fn = fn

        self._tree = [default] * (self._size * 2 - 1)
        if initial_values:
            i = self._size - 1
            for v in initial_values:
                self._tree[i] = v
                i += 1
            i = self._size - 2
            while i >= 0:
                self._tree[i] = self._fn(self._tree[i * 2 + 1], self._tree[i * 2 + 2])
                i -= 1

    def set(self, i, value):
        """
        i 番目に value を設定
        :param int i:
        :param value:
        :return:
        """
        x = self._size - 1 + i
        self._tree[x] = value

        while x > 0:
            x = (x - 1) // 2
            self._tree[x] = self._fn(self._tree[x * 2 + 1], self._tree[x * 2 + 2])

    def add(self, i, value):
        """
        もとの i 番目と value に fn を適用したものを i 番目に設定
        :param int i:
        :param value:
        :return:
        """
        x = self._size - 1 + i
        self.set(i, self._fn(self._tree[x], value))

    def get(self, from_i, to_i=None, k=0, L=None, r=None):
        """
        [from_i, to_i) に fn を適用した結果を返す
        :param int from_i:
        :param int to_i:
        :param int k: self._tree[k] が、[L, r) に fn を適用した結果を持つ
        :param int L:
        :param int r:
        :return:
        """
        if to_i is None:
            return self._tree[self._size - 1 + from_i]

        L = 0 if L is None else L
        r = self._size if r is None else r

        if from_i <= L and r <= to_i:
            return self._tree[k]

        if to_i <= L or r <= from_i:
            return None

        ret_L = self.get(from_i, to_i, k * 2 + 1, L, (L + r) // 2)
        ret_r = self.get(from_i, to_i, k * 2 + 2, (L + r) // 2, r)
        if ret_L is None:
            return ret_r
        if ret_r is None:
            return ret_L
        return self._fn(ret_L, ret_r)


N, Q = list(map(int, sys.stdin.buffer.readline().split()))
CXY = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(Q)]

st = SegmentTree( N, fn=min, default=2**31 - 1)
for c, x, y in CXY:

    if c == 0:
        st.set(x, y)
    else:
        print(st.get(x, y + 1))

Solution (Python):
def update(bin_tree, x, y, n):
    i = n - 1 + x
    bin_tree[i] = y

    while i > 0:
        i = int((i - 1) / 2)
        bin_tree[i] = min(bin_tree[2*i+1], bin_tree[2*i+2])


def find(bin_tree, x, y, k, l, r):
    if r <= x or y <= l:
        return 2**31-1
    elif x <= l and r <= y:
        return bin_tree[k]
    else:
        vl = find(bin_tree, x, y, 2 * k + 1, l, int((l + r) / 2))
        vr = find(bin_tree, x, y, 2 * k + 2, int((l + r) / 2), r)
        return min(vl, vr)


def main():
    [n, q] = [int(num) for num in input().split()]

    m = 1
    while m < n:
        m *= 2

    bin_tree = [2**31-1 for _ in range(2*m-1)]

    for i in range(q):
        
        [com, x, y] = [int(num) for num in input().split()]

        if com == 0:
            update(bin_tree, x, y, m)
        else:
            print(find(bin_tree, x, y+1, 0, 0, m))


if __name__ == '__main__':
    main()

Solution (Python):
n, q = [int(s) for s in input().split()]
max_n = 2**31-1
m = 1
while m < n:
    m *= 2

dat = [max_n] * (2*m-1)


def update(i, x):
    i += m-1
    dat[i] = x
    while i > 0:
        i = int((i-1)/2)
        dat[i] = min(dat[2*i+1], dat[2*i+2])

def find(a, b, k, l, r):
    if r <= a or b <= l:
        return max_n
    elif a <= l and r <= b:
        return dat[k]
    else:
        vl = find(a, b, 2*k+1, l, int((l+r)/2))
        vr = find(a, b, 2*k+2, int((l+r)/2), r)
        return min(vl, vr)

for _ in range(q):
    com, i, x = [int(s) for s in input().split()]
    if com == 0:
        update(i, x)
    else:
        ans = find(i, x+1, 0, 0, m)
        print(ans)

Solution (Python):
maximam = 2**31 - 1

class Segment_Tree:
    def __init__(self,n):
        self.n = n
        self.tree = [maximam]*(2*self.n - 1)
    def update(self,i,x):
        i += self.n-1
        self.tree[i] = x
        while i>0:
            i = int((i-1)/2)
            self.tree[i] = min(self.tree[2*i+1],self.tree[2*i+2])
    def find(self,a,b,k,l,r):
        if r <= a or b <= l:
            return maximam
        if a <= l and r <= b:
            return self.tree[k]
        vl = self.find(a,b,k*2+1,l,int((l+r)/2))
        vr = self.find(a,b,k*2+2,int((l+r)/2),r)
        return min(vl, vr)

n, q = map(int, input().split())
N = 1
while N < n:
    N *= 2

segtre = Segment_Tree(N)

for _ in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        segtre.update(x,y)
    else:
        print(segtre.find(x,y+1,0,0,N))

Solution (Python):

def make_ST(n,first): 

    i = 0
    ret = []
    while 2 ** (i-1) < n:

        for j in range(2 ** i):
            ret.append(first)

        i += 1

    return ret

def RMQ_update_point(num,point,tree): 

    i = (len(tree) - 1) // 2 + point
    tree[i] = num
    while i > 0:
        i = (i - 1) // 2
        tree[i] = min(tree[i * 2 + 2] , tree[i * 2 + 1])

    return

def RMQ_query(a,b,k,l,r,tree): 

    if r <= a or b <= l: 
        return float("inf")
    
    if a <= l and r <= b: 
        return tree[k]

    c1 = RMQ_query(a,b,2*k+1,l,(l+r)//2,tree)
    c2 = RMQ_query(a,b,2*k+2,(l+r)//2,r,tree)   

    return min(c1,c2)
        

n,q = map(int,input().split())

ABLE_MAX = 2 ** 31 - 1
segt = make_ST(n,ABLE_MAX)

for i in range(q):

    com,x,y = map(int,input().split())

    if com == 0:
        RMQ_update_point(y,x,segt)
    else:
        print (RMQ_query(min(x,y+1),max(x,y+1),0,0,(len(segt)+1)//2,segt))

Solution (Python):
def func(x,y):
    return  x if x < y else y

class SegmentTree:
    def __init__(self, n): 
        n_ = 1
        while n_ < n:
            n_ *= 2

        self.n = n_
        self.arr = [2**31-1] * (2*self.n-1)

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

        while k > 0:
            k = (k-1) // 2
            self.arr[k] = func(self.arr[2*k+1], self.arr[2*k+2])

    def query(self, l, r):
        L, R = l+self.n, r+self.n
        ide_ele = 2**31-1
         
         
         
         
        res = ide_ele
        while L < R:
            if R & 1:
                R -= 1
                res = func(res, self.arr[R-1])

            if L & 1:
                res = func(res, self.arr[L-1])
                L += 1

            L >>= 1
            R >>= 1

        return res

n,q=map(int,input().split())
sg=SegmentTree(n)
for _ in range(q):
    c,x,y=map(int,input().split())
    if c==0:
        sg.update(x,y)
    else:
        print(sg.query(x,y+1))

Solution (Python):


import sys
input=sys.stdin.readline

class MIN_SEGMENTTREE:
    def __init__(self,lis):
        length=len(lis)
        self.n=2**length.bit_length()
        self.node=[float("inf")]*(2*self.n-1)
        
        for i in range(length):
            self.node[i+self.n-1]=lis[i]
        for i in range(self.n-2,-1,-1):
            if self.node[2*i+1]>self.node[2*i+2]:
                self.node[i]=self.node[2*i+2]
            else:
                self.node[i]=self.node[2*i+1]

    def update(self,point,value):
        point+=self.n-1
        self.node[point]=value
        while point>0:
            point=(point-1)//2
            if self.node[2*point+1]>self.node[2*point+2]:
                self.node[point]=self.node[2*point+2]
            else:
                self.node[point]=self.node[2*point+1]
    
    def getmin(self,a,b):
        l,r = a+self.n,b+self.n
        ret = float("inf")
        while l<r:
            if r&1:
                r-=1
                if ret>self.node[r-1]:
                    ret=self.node[r-1]

            if l&1:
                if ret>self.node[l-1]:
                    ret=self.node[l-1]
                l+=1

            l>>=1
            r>>=1
        return ret

n,q=map(int,input().split())
s=MIN_SEGMENTTREE([2**31-1]*n)
for i in range(q):
    f,a,b=map(int,input().split())
    if f:
        print(s.getmin(a,b+1))
    else:
        s.update(a,b)

Solution (Python):
class Rmq:
    
    
    
    def __init__(self, a, sqrt_n=150, inf=(1<<31)-1):
        self.sqrt_n = sqrt_n
        if hasattr(a, "__iter__"):
            from itertools import zip_longest
            self.n = len(a)
            self.layer0 = [min(values) for values in zip_longest(*[iter(a)]*sqrt_n, fillvalue=inf)]
            self.layer1 = a
        elif isinstance(a, int):
            self.n = a
            self.layer0 = [inf] * ((a - 1) // sqrt_n + 1)
            self.layer1 = [inf] * a
        else:
            raise TypeError

    def get_min(self, l, r):
        sqrt_n = self.sqrt_n
        parent_l, parent_r = l//sqrt_n+1, (r-1)//sqrt_n
        if parent_l < parent_r:
            return min(min(self.layer0[parent_l:parent_r]),
                       min(self.layer1[l:parent_l*sqrt_n]),
                       min(self.layer1[parent_r*sqrt_n:r]))
        else:
            return min(self.layer1[l:r])

    def set_value(self, idx, val):
        self.layer1[idx] = val
        idx0 = idx // self.sqrt_n
        idx1 = idx0 * self.sqrt_n
        self.layer0[idx0] = min(self.layer1[idx1:idx1+self.sqrt_n])

    def chmin(self, idx, val):
        if self.layer1[idx] > val:
            self.layer1[idx] = val
            idx //= self.sqrt_n
            self.layer0[idx] = min(self.layer0[idx], val)

    def debug(self):
        print("layer0=", self.layer0)
        print("layer1=", self.layer1)

    def __getitem__(self, item):
        return self.layer1[item]

    def __setitem__(self, key, value):
        self.set_value(key, value)


def main():
    N, Q, *queries = map(int, open(0).read().split())
    seg = Rmq(N)
    Ans = []
    for com, x, y in zip(*[iter(queries)]*3):
        if com==0:
            seg.set_value(x, y)
        else:
            Ans.append(seg.get_min(x, y+1))
    print("\n".join(map(str, Ans)))


main()

Solution (Python):
class SegmentTree:
	def __init__(self, orig, func, unit):
		_len = len(orig)
		self.func = func
		self.size = 1 << (_len - 1).bit_length()
		self.tree = [unit] * self.size + orig + [unit] * (self.size - _len)
		self.unit = unit

		for i in range(self.size - 1, 0, -1):
			self.tree[i] = func(self.tree[i * 2], self.tree[i * 2 + 1])

	def update(self, i, v):
		i += self.size
		self.tree[i] = v
		while i:
			i //= 2
			self.tree[i] = self.func(self.tree[i * 2], self.tree[i * 2 + 1])

	def find(self, l, r):
		l += self.size
		r += self.size
		ret = self.unit
		while l < r:
			if l & 1:
				ret = self.func(ret, self.tree[l])
				l += 1
			if r & 1:
				r -= 1
				ret = self.func(ret, self.tree[r])
			l //= 2
			r //= 2
		return ret


def main():
	N, Q, *L = map(int, open(0).read().split())
	tree = SegmentTree([(1 << 31) - 1] * N, min, (1 << 31) - 1)
	ans = []
	for c, x, y in zip(*[iter(L)] * 3):
		if c:
			ans.append(tree.find(x, y + 1))
		else:
			tree.update(x, y)
	print(*ans, sep="\n")


if __name__=="__main__":
	main()

Solution (Python):
inf = (1 << 31) - 1


class SegmentTree:
    def __init__(self, n):
        tmp = 1
        while tmp < n:
            tmp <<= 1
        
        self.N = tmp
        
        
        self.Data = [inf for _ in range(2*self.N)]

    
    def update(self, k, x):
        
        k += self.N
        
        self.Data[k] = x
        
        while k != 1:
            k >>= 1
            self.Data[k] = min([self.Data[2*k], self.Data[2*k+1]])

    
    def query(self, l, r):
        
        l += self.N
        r += self.N
        
        res = inf
        while l < r:
            
            
            if l & 1:
                res = min([res, self. Data[l]])
                l += 1
            
            
            if r & 1:
                r -= 1
                res = min([res, self.Data[r]])
            l >>= 1; r >>= 1
        return res

N, Q = map(int,input().split())
st = SegmentTree(N)

for _ in range(Q):
    com, x, y = map(int,input().split())
    if com == 0:
        st.update(x, y)
    elif com == 1:
        y += 1
        print(st.query(x, y))

Solution (Python):
INF_MAX = 2 ** 31 - 1


class Segment_tree():
    def __init__(self, N):
        self.N = 1
        while self.N < N:
            
            self.N *= 2

        self.dat = []
        for i in range(2 * self.N - 1):
            
            self.dat.append(INF_MAX)

    def update(self, k, x):
        k += self.N - 1
        
        self.dat[k] = x
        while k > 0:
            
            k = int((k - 1) / 2)
            self.dat[k] = min(self.dat[k * 2 + 1], self.dat[k * 2 + 2])

    def find(self, a, b, k, l, r):
        if r < a or b < l:
            
            return INF_MAX
        if a <= l and r <= b:
            
            return self.dat[k]
        else:
            mid = int((l + r) / 2)
            
            vl = Segment_tree.find(self, a, b, k * 2 + 1, l, mid)
            vr = Segment_tree.find(self, a, b, k * 2 + 2, mid + 1, r)
            return min(vl, vr)


def main():
    N, Q = map(int, input().split())
    segment_tree = Segment_tree(N)
    for i in range(Q):
        command, a, b = map(int, input().split())
        if command == 0:
            Segment_tree.update(segment_tree, a, b)
        else:
            if a > b:
                a, b = b, a
            min_number = Segment_tree.find(segment_tree, a, b, 0, 0, segment_tree.N - 1)
            print(min_number)


if __name__ == "__main__":
    main()

Solution (Python):
n,q = map(int,input().split( ))
s = 1
while s < n:
    s*=2

A = [(1<<31)-1]*(2*s-1)

def query(a,b,k,l,r):
    if r<=a or b<=l:
        return 2**31-1
    if a<=l and r<=b:
        return A[k]
    else:
        c1 = query(a,b,2*k+1,l,(l+r)//2)    
        c2 = query(a,b,2*k+2,(l+r)//2,r)
        return min(c1,c2)

for _ in range(q):
    c,x,y = map(int, input().split( ))
    if not c:
        x += (s-1)
        A[x] = y
        while x>0:
            x =(x-1)//2
            A[x] = min(A[x*2+1],A[x*2+2])
        
            
    else:
        print(query(x,y+1,0,0,s))

Solution (Python):
import sys

sys.setrecursionlimit(10**6)

class rmq_segment_tree:
    inf=(1<<31)-1
    n,n_=0,0
    array=[]
    def __init__(self,n_):
        n=1
        while n<n_: n*=2
        self.n=n
        self.n_=n_
        self.array=[self.inf]*(2*n-1)

    def update(self,i,x):
        i+=self.n-1
        self.array[i]=x
        
        while i>0:
            i=(i-1)//2
            self.array[i]=min(self.array[i*2+1],self.array[i*2+2])
    
    def rec(self,a,b,k,left,right):
        if right<=a or b<=left: return self.inf
        if a<=left and right<=b: return self.array[k]
        mid=(left+right)//2
        value_left=self.rec(a,b,k*2+1,left,mid)
        value_right=self.rec(a,b,k*2+2,mid,right)
        return min(value_left,value_right)

    def f(self,a,b):
        return self.rec(a,b,0,0,self.n)
n,q=map(int,input().split())
tree=rmq_segment_tree(n)

for _ in range(q):
    c,x,y=map(int,input().split())
    if c==1:
        print(tree.f(x,y+1))
    else:
        tree.update(x,y)

Solution (Python):


import sys
input = sys.stdin.readline


INF = (1 << 31) - 1

class SegmentTree:
    def __init__(self, N):
        self.N = 2**(N-1).bit_length()
        self.data = [[INF, -1] for _ in range(2*self.N-1)]

    
    def update(self, k, a):
        self.data[k+self.N-1] = [a, k]
        k += self.N - 1
        while k > 0:
            k = (k-1)//2
            if self.data[2*k+1][0] < self.data[2*k+2][0]:
                self.data[k] = self.data[2*k+1][:]
            else:
                self.data[k] = self.data[2*k+2][:]

    
    
    def query_min(self, l, r):
        L = l + self.N
        R = r + self.N
        s = [INF, -1]
        while L < R:
            if R & 1:
                R -= 1
                if s[0] > self.data[R-1][0]:
                    s = self.data[R-1]
            if L & 1:
                if s[0] > self.data[L-1][0]:
                    s = self.data[L-1]
                L += 1
            L >>= 1; R >>= 1
        return s

N, Q = map(int, input().split())
Query = [list(map(int, input().split())) for _ in range(Q)]

ST = SegmentTree(N)

for com, x, y in Query:
    if com == 0:
        ST.update(x, y)
    else:
        print(ST.query_min(x, y+1)[0])

Solution (Python):
class SegmentTree(object):
    def __init__(self,A,dot,e):
        n=2**((len(A)-1).bit_length())
        self.__n=n
        self.__dot=dot
        self.__e=e
        self.__node=[e]*(2*n-1)
        for i in range(len(A)):
            self.__node[n+i-1]=A[i]
        for i in range(n-2,-1,-1):
            self.__node[i]=dot(self.__node[2*i+1],self.__node[2*i+2])

    def update(self,i,c):
        i+=self.__n-1
        node=self.__node
        node[i]=c
        while(i!=0):
            i=(i-1)//2
            node[i]=self.__dot(node[2*i+1],node[2*i+2])

    def __get_range(self,l,r):
        if l>=r: return [],[]
        Left,Right=[],[]
        n=self.__n
        l+=n-1; r+=n-2
        while(l<r):
            if l%2==0:
                Left.append(l)
            if r%2==1:
                Right.append(r)
                r-=1
            l=l//2; r=(r-1)//2
        if l==r:
            if l%2==0: Left.append(l)
            else: Right.append(l)
        return Left,Right

    def sum(self,l,r):
        Left,Right=self.__get_range(l,r)
        res=self.__e
        for i in Left+Right[::-1]:
            res=self.__dot(res,self.__node[i])
        return res

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,q=map(int,input().split())
    A=[(1<<31)-1]*n
    tree=SegmentTree(A,min,INF)
    for _ in range(q):
        c,x,y=map(int,input().split())
        if c==0: tree.update(x,y)
        else: print(tree.sum(x,y+1))
resolve()