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, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, log2
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
mod = 10 ** 9 + 7

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

n, q = MAP()
rmq = SegmentTree(n, min, (1<<31)-1)

for _ in range(q):
	c, x, y = MAP()
	if c == 0:  
		rmq.update(x, y)
	else:  
		print(rmq.query(x, y+1))

Solution (Python):

n,q = map(int,input().split())
NO = (n-1).bit_length()
INF = pow(2,31)-1
A = [INF]*(2<<(NO))

def update(i,x):
    v = pow(2,NO)+i
    A[v] = x
    while v>0:
        v//=2
        A[v] = min(A[v<<1],A[(v<<1)+1])

def find(i,j):
    s = INF
    l = i+pow(2,NO)
    r = j+pow(2,NO)
    while l<r:
        if l & 1:
            s = min(s,A[l])
            l+=1
        if r & 1:
            r-=1
            s = min(s,A[r])
        l//=2
        r//=2
    return s

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

Solution (Python):

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

A = [2**31 - 1] * N

q = [tuple(map(int, input().split())) for _ in range(Q)]

seg_num = 2**(N-1).bit_length()
ide_ele = float("inf")
func = min
seg_lst = [ide_ele] * 2 * seg_num

def init(lst):
    for i in range(N):
        
        seg_lst[i + seg_num - 1] = lst[i]
    
    
    for i in range(seg_num - 2, -1, -1):
        seg_lst[i] = func(seg_lst[2*i + 1], seg_lst[2*i + 2])

def update(i, x):
    
    i += seg_num - 1
    seg_lst[i] = x
    while i:
        
        i = (i - 1) // 2
        seg_lst[i] = func(seg_lst[2*i + 1], seg_lst[2*i + 2])

def query(l,r):
    if r <= l:
        return ide_ele

    l += seg_num - 1
    r += seg_num - 2

    ret = ide_ele

    while r - l > 1:

        if l & 1 == 0:
            ret = func(ret, seg_lst[l])
        if r & 1 == 1:
            ret = func(ret, seg_lst[r])
            r -= 1
        l  = l // 2
        r = (r - 1) // 2

    if l == r:
        ret = func(ret, seg_lst[l])
    else:
        ret = func(ret, seg_lst[l])
        ret = func(ret, seg_lst[r])
    return ret


init(A)

for c,x,y in q:
    if c == 0:
        update(x, y)
    else:
        print(query(x, y+1))

Solution (Python):




class SegmentTree:
    '''
    SegmentTree(arr, e)
        arr : 配列,
        e : 単位元\n
    segment_tree[i] で取得、更新\n
    segment_tree.query(a,b) で区間[a,b)の計算結果を得る(a<bでなければ単位元が返ってくる)
    '''
    def __init__(self, arr, e):
        self.e = e
        self.len = len(arr)
        
        n = 2 ** (len(bin(self.len + 1)) - 2)
        self.n = n
        
        node = [e] * (2 * n)
        node[n: n + self.len] = arr
        for i in range(n - 1, 0, -1):
            node[i] = node[2 * i] + node[2 * i + 1]
        self.node = node

    def __setitem__(self, i, val):
        
        i += self.n
        self.node[i] = val
        
        while i > 1:
            
            i //= 2
            
            self.node[i] = self.node[2 * i] + self.node[2 * i + 1]

    def __getitem__(self, i):
        return self.node[self.n + i]

    def query(self, a, b):
        a = self.trim(a, self.len)
        b = self.trim(b, self.len)

        
        
        
        def get(k, l, r):
            
            if r <= a or b <= l:
                return self.e
            if a <= l and r <= b:
                return self.node[k]
            m = (l + r) // 2
            return get(2 * k, l, m) + get(2 * k + 1, m, r)

        return get(1, 0, self.n)

    def getlist(self):
        return self.node[self.n:]

    def trim(self, i, n):
        i = max(i, -n)
        i = min(i, n)
        if i < 0:
            i += n
        return i




class Monoid:
    '''
    Monoid(val)\n
    演算は自分で定義する Monoid + Monoid
    ※単位元をクラス変数とし持たない
    '''

    def __init__(self, val):
        self.val = val
    def __repr__(self):
        return repr(self.val)

    
    def __add__(self, other):
        return Monoid(min(self.val, other.val))

n, q = map(int, input().split())
A = [Monoid(2 ** 31 - 1)] * n
st = SegmentTree(A, Monoid(2 ** 31 - 1))
for i in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        st[x] = Monoid(y)
    else:
        print(st.query(x, y + 1))

Solution (Python):
class SegmentTree:
    def __init__(self, lst, op, e):
        self.n = len(lst)
        self.N = 1 << ((self.n - 1).bit_length())
        self.op = op 
        self.e = e 
        self.v = self._build(lst) 
        
    def _build(self, lst):
        
        
        tree = [self.e] * (self.N) + lst + [self.e] * (self.N - self.n)
        for i in range(self.N - 1, 0, -1): tree[i] = self.op(tree[i << 1], tree[(i << 1)|1])
        return tree
    
    def __getitem__(self, i):
        return self.v[i + self.N]
    
    
    def update(self, i, x):
        i += self.N
        self.v[i] = x
        while i > 0:
            i >>= 1 
            self.v[i] = self.op(self.v[i << 1], self.v[(i << 1)|1])
    
    
    def fold(self, l, r):
        left = l + self.N; right = r + self.N
        L = self.e; R = self.e
        while left < right:
            if left & 1: 
                L = self.op(L, self.v[left])
                left += 1
            if right & 1: 
                right -= 1
                R = self.op(self.v[right], R)
            left >>= 1; right >>= 1
        return self.op(L, R)
    
N, Q = map(int, input().split())
op = min
e = 2**31 - 1
A = [e] * N
sg = SegmentTree(A, op, e)
for _ in range(Q):
    t, *arg, = map(int, input().split())
    if t == 0: sg.update(arg[0], arg[1])
    else: print(sg.fold(arg[0], arg[1]+1))

Solution (Python):

'''
org: 配列[list]
func: 関数 (min,max,sumなど)
unit: 初期値
'''
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

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,q = mi()
seg = SegmentTree([(1<<31) -1]*n,min,(1<<31) -1)
for _ in range(q):
    a,b,c = mi()
    if a == 1:
        print(seg.find(b,c+1))
    else:
        seg.update(b,c)

Solution (Python):



"""
https://komiyam.hatenadiary.org/entry/20131202/1385992406
大雑把に言って、平衡二分探索木からinsert,delete,split,mergeなどができないよう制限したのがsegment treeで、
segment treeの区間[L,R)に対するクエリをL=0に制限したのがbinary indexed treeだと見なすことができます。
"""


class SegmentTree():
    """
    update, get を提供するSegmentTree

    Attributes
    ----------
    __n : int
        葉の数。2 ^ i - 1
    __dot :
        Segment function
    __e: int
        単位元
    __node: list
        Segment Tree
    """
    def __init__(self, A, dot, e):
        """
        Parameters
        ----------
        A : list
            対象の配列
        dot :
            Segment function
        e : int
            単位元
        """
        n = 2 ** (len(A) - 1).bit_length()
        self.__n = n
        self.__dot = dot
        self.__e = e
        self.__node = [e] * (2 * n)
        for i in range(len(A)):
            self.__node[i + n] = A[i]
        for i in range(n - 1, 0, -1):
            self.__node[i] = self.__dot(self.__node[2 * i], self.__node[2 * i + 1])
    
    def update(self, i, c):
        i += self.__n
        node = self.__node
        node[i] = c
        while i > 1:
            i //= 2
            node[i] = self.__dot(node[2 * i], node[2 * i + 1])

    def get(self, l, r):
        vl, vr = self.__e, self.__e
        l += self.__n
        r += self.__n
        while (l < r):
            if l & 1:
                vl = self.__dot(vl, self.__node[l])
                l += 1
            l //= 2
            if r & 1:
                r -= 1
                vr = self.__dot(vr, self.__node[r])
            r //= 2
        return self.__dot(vl, vr)
    


def AOJ_DSL_2_A():
    n, q = map(int, input().split())
    e = (1 << 31) - 1
    A = [e] * n
    seg = SegmentTree(A, min, e)

    for i in range(q):
        t, x, y = map(int, input().split())
        if t == 0:
            seg.update(x, y)
        else:
            print(seg.get(x, y + 1))



def AOJ_DSL_2_B():
    from operator import add
    import sys
    n, q = map(int, input().split())
    e = 0
    A = [e] * n
    seg = SegmentTree(A, add, e)
    
    query = sys.stdin.readlines()
    for i in range(q):
        t, x, y = map(int, query[i].split())
        x -= 1
        if t == 0:
            A[x] += y
            seg.update(x, A[x])
        else:
            y -= 1
            print(seg.get(x, y + 1))


def ABC125_C():
    from fractions import gcd
    N = int(input())
    A = list(map(int, input().split()))
    
    seg = SegmentTree(A, gcd, 0)
    ans = 0
    for i in range(N):
        ans = max(ans, gcd(seg.get(0, i), seg.get(i + 1, N)))
    print(ans)


AOJ_DSL_2_A()

Solution (Python):
class segtree:
  def __init__(self, initArr, segfunc, idele):
    n = len(initArr)
    stn = 2**((n - 1).bit_length() + 1) - 1
    arr =  [idele for i in range(stn)]
    arr[stn//2:stn//2+n] = initArr
    for i in range(stn-1, 1, -2):
      arr[(i-1)//2] = segfunc(arr[i-1], arr[i])
  
    self.arr = arr
    self.segfunc = segfunc
    self.idele = idele
  
  def update(self, idx, val):
    idx += len(self.arr)//2
    self.arr[idx] = val
    while idx > 0:
      idx = (idx-1)//2
      self.arr[idx] = self.segfunc(self.arr[idx*2+1], self.arr[idx*2+2])
    return None

  def query(self, x, y, i=0, l=0, r=-1): 
    if r < 0: r = len(self.arr)//2 + 1
    if r <= x or y <= l: return self.idele
    if x <= l and r <= y: return self.arr[i]
    return self.segfunc(
      self.query(x, y, 2*i+1, l, (l+r)//2),
      self.query(x, y, 2*i+2, (l+r)//2, r)
    )
N, Q = map(int, input().split())
st = segtree(list([2**31-1]*N), min, 2**31-1)

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

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


class SEGMENT_TREE:
    def __init__(self, N):
        self.N = N
        inf = (1 << 31) - 1
        self.inf = inf
        self.tree = [inf] * (2 * N + 1)  

    def init(self, arr):
        N = self.N
        for i in range(N):
            self.tree[N + i] = arr[i]
        for i in range(N - 1, 0, -1):
            self.tree[i] = self.tree[i * 2] + self.tree[i * 2 + 1]  

    def update(self, p, value):
        """配列arr[p]をvalueに変更"""
        i = p + self.N
        self.tree[i] = value
        while i > 1:
            self.tree[i // 2] = min(self.tree[i], self.tree[i ^ 1])
            i //= 2

    def query(self, l, r):
        """
        l, r: 0-indexed
        半開区間[l, r)から条件を満たす数を返す
        """
        N = self.N
        res = self.inf   
        l += N
        r += N
        while l < r:
            if (l & 1):
                res = min(res, self.tree[l])
                l += 1
            if (r & 1):
                r -= 1
                res = min(res, self.tree[r])
            l //= 2
            r //= 2
        return res


if __name__ == "__main__":
    N, Q = map(int, input().split())
    seg = SEGMENT_TREE(N)

    ans = []

    for _ in range(Q):
        com, x, y = map(int, input().split())
        if com:
            ans.append(seg.query(x, y+1))
        else:
            seg.update(x, y)

    print(*ans, sep="\n")

Solution (Python):
class Segment_Tree:
    __slots__ = ['ide_ele', 'size', 'num', 'seg', 'segfunc']

    def __init__(self, size, func, element):
        
        self.ide_ele = element
        self.size = size

        
        self.num = 2 ** (self.size - 1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num

        
        self.segfunc = func

    def apply(self, apply_seq):
        
        for i in range(self.size):
            self.seg[i + self.num - 1] = apply_seq[i]    
        
        for i in range(self.num - 2, -1, -1) :
            self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2]) 
        
    def update(self, k, x):
        k += self.num - 1
        self.seg[k] = x
        while k:
            k = (k-1) // 2
            self.seg[k] = self.segfunc(self.seg[k * 2 + 1],  self.seg[k * 2 + 2])
        
    def query(self, p, q):
        if q <= p:
            return self.ide_ele
        p += self.num - 1
        q += self.num - 2
        res = self.ide_ele
        while q - p > 1:
            if p & 1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q & 1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2 
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

n,q = map(int,input().split())
st = Segment_Tree(n,min,float("inf"))
for _ in range(q):
  typo,x,y = map(int,input().split())
  if typo == 0:
    st.update(x,y)
  else:
    out = st.query(x,y+1)
    print(out if out != float("inf") else 2**31-1)

Solution (Python):
"""Range Minimum Query (RMQ)"""




def update(idx, x):
    idx += size-1  
    seg[idx] = x  
    
    while idx > 0:
        idx = (idx-1)//2  
        seg[idx] = min(seg[2*idx+1], seg[2*idx+2])  
    
    return



def query(a, b, k, l, r):  
    
    if r <= a or b <= l:  
        return INF  
    if a <= l and r <= b:
        return seg[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)  


N, Q = map(int, input().split())  
size = 1  
while N > size:
    size *= 2  



INF = 2**31-1  

seg = [INF]*(2*size-1)

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

Solution (Python):
from operator import add


class SegTree():
    def __init__(self, N, e, operator_func=add):
        self.e = e 
        self.size = N
        self.node = [self.e] * (2*N)
        self.operator_func = operator_func 

    def set_list(self, l):
        for i in range(self.size):
            self.node[i+self.size-1] = l[i]
        for i in range(self.size-1)[::-1]:
            self.node[i] = self.operator_func(self.node[2*i+1], self.node[2*i+2])
    
    def update(self, k, x):
        k += self.size-1
        self.node[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.node[k] = self.operator_func(self.node[2*k+1], self.node[2*k+2])

    def get(self, l, r):
        x = self.e
        l += self.size
        r += self.size

        while l<r:
            if l%2:
                x = self.operator_func(x, self.node[l-1])
                l += 1
            if r%2:
                r -= 1
                x = self.operator_func(x, self.node[r-1])
            l //= 2
            r //= 2
        return x

if __name__ == "__main__":
    n, q = map(int, input().split())
    inf = 2**31-1
    tree = SegTree(n, inf, min)

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

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    class SegmentTree():
        def __init__(self,n,ide_ele,segfunc):
            self.ide_ele=ide_ele
            self.segfunc=segfunc
            self.num=2**(n-1).bit_length()
            self.dat=[ide_ele]*2*self.num
        
        def init(self,iter):
            for i in range(n):
                self.dat[i+self.num-1]=iter[i]
            for i in range(self.num-2,-1,-1):
                self.dat[i]=self.segfunc(self.dat[2*i+1],self.dat[2*i+2])
        
        def update(self,k,x):
            k+=self.num-1
            self.dat[k]=x
            while k:
                k=(k-1)//2
                self.dat[k]=self.segfunc(self.dat[k*2+1],self.dat[k*2+2])
        
        def query(self,p,q):
            if q<=p:
                return self.ide_ele
            p+=self.num-1
            q+=self.num-2
            res=self.ide_ele
            while q-p>1:
                if p&1==0:
                    res=self.segfunc(res,self.dat[p])
                if q&1==1:
                    res=self.segfunc(res,self.dat[q])
                    q-=1
                p=p//2
                q=(q-1)//2
            if p==q:
                res=self.segfunc(res,self.dat[p])
            else:
                res=self.segfunc(self.segfunc(res,self.dat[p]),self.dat[q])
            return res
    
    n,q=map(int,input().split())
    seg=SegmentTree(n,INF,min)
    seg.init([2**31-1]*n)
    
    for _ in range(q):
        c,x,y=map(int,input().split())
        if c==0:
            seg.update(x,y)
        else:
            y+=1
            print(seg.query(x,y))

if __name__ == '__main__':
    main()

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     

class SegmentTree():
    def __init__(self, arr):
        self.arr = arr
        self.size = self.calc_size(arr)
        self.n = (self.size+ 1) // 2 
        self.value = [2**31 - 1 for _ in range(self.size)]

    def calc_size(self, array):
        i = 1
        while i < len(array):
            i = i << 1
        return (i << 1) - 1

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

    def query(self, l, r):
        
        def _query(l, r, node_i, node_l, node_r):
            
            
            

            if node_r <= l or r <= node_l:
                return inf

            if l <= node_l and node_r <= r:
                return self.value[node_i]

            c1 = _query(l, r, 2 * node_i + 1, node_l, (node_l + node_r) // 2)
            c2 = _query(l, r, 2 * node_i + 2, (node_l + node_r) // 2, node_r)
            return min(c1, c2)

        return _query(l, r+1, 0, 0, self.n)

def main():
    n, q = LI()
    ans = []
    st = SegmentTree([2**31 - 1 for _ in range(n)])
    for _ in range(q):
        c, x, y = LI()
        if c == 0:
            st.update(x, y)
        if c == 1:
            ans.append(st.query(x, y))
    for a in ans:
        print(a)


main()

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


class SegmentTree0():
    """
    0-indexed Segment Tree
    """
    def __init__(self, n_, ele_id, op_func):
        self.n = 1 << (n_ - 1).bit_length()  
        self.data = [ele_id] * (2 * self.n - 1)  
        self.ele_id = ele_id  
        self.op_func = op_func  

    def __getitem__(self, i):
        return self.data[i + self.n - 1]

    def build(self, data_init):
        for i in range(len(data_init)):
            self.data[i + self.n - 1] = data_init[i]  
        for i in range(self.n - 2, -1, -1):
            self.data[i] = self.op_func(self.data[2 * i + 1],
                                        self.data[2 * i + 2])

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

    def query(self, a, b):
        
        return self.query_(a, b, 0, 0, self.n)

    def query_(self, a, b, k, l, r):
        if r <= a or b <= l:
            
            return self.ele_id
        if a <= l and r <= b:
            
            return self.data[k]
        else:
            
            child_l = self.query_(a, b, 2 * k + 1, l, (l + r) // 2)
            child_r = self.query_(a, b, 2 * k + 2, (l + r) // 2, r)
            return self.op_func(child_l, child_r)


n, q = map(int, input().split())
ele_id = (1 << 31) - 1
op_func = min
st_rmq = SegmentTree0(n, ele_id, op_func)
for _ in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        st_rmq.update(x, y)
    elif com == 1:
        ans = st_rmq.query(x, y + 1)
        print(ans)

Solution (Python):


import sys

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N, Q = iim()
    val = 2**31-1

    A, S, i = [], [],  N
    while i > 1:
        i += i & 1
        A.append([val] * i)
        i >>= 1
    A.append([val])
    la = len(A)

    def update(i, x):
        i0 = i
        x0 = A[0][i]
        diff = x0 - x
        if diff == 0:
            return
        A[0][i] = x
        if diff > 0:
            for j in range(1, la):
                i, i0 = i >> 1, i
                y = A[j][i]
                if x >= y:
                    break
                A[j][i] = x
            return

        for j in range(0, la-1):
            y = A[j][i^1]
            if x >= y:
                x = y
            i >>= 1
            if A[j+1][i] == x:
                break
            A[j+1][i] = x


    def find(s, t):
        i, ans = 0, val
        while t - s > 1:
            if s & 1:
                ans = min(ans, A[i][s])
                s += 1
            if t & 1 == 0:
                ans = min(ans, A[i][t])
                t -= 1
            s, t , i= s // 2, t // 2, i + 1
            

        return min(A[i][s], A[i][t], ans)


    for com, *arg in (map(int, line.split()) for line in sys.stdin):
        if com == 0:
            update(*arg)
        else:
            
            
            
            res = find(*arg)
            print(res)

if __name__ == "__main__":
    resolve()

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

class SegTreeMin:

    def __init__(self, V):
        
        self.sz = len(V)
        N = 1
        while N < self.sz:
            N *= 2
        
        self.N = N
        self.node = [INITIAL] * (2 * self.N - 1)
        
        for i in range(self.sz):
            self.node[i + self.N - 1] = V[i]
        
        for i in range(self.N-2,0,-1):
            self.node[i] = min(self.node[2*i+1], self.node[2*i+2])

    def update(self, x, val):
        '''
        x番目の要素を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 get_min(self, a, b, k=0, l=0, r=-1):
        '''
        区間[a, b)の最小値をこたえる => 要求区間
        k := 自分がいるノードのインデックス
        [l,r)はノードがカバーする区間 => 対象区間
        '''
        
        if r < 0:
            r = self.N
        
        
        if r <= a or l >= b:
            return INITIAL
        
        
        if l >= a and r <= b:
            return self.node[k]

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

def main():
    n, q = map(int, input().split())
    V = [INITIAL] * n
    seg = SegTreeMin(V)

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

if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)




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


class SegmentTree:
    """
    引数：
        N: 処理する区間の長さ
        operator: モノイド演算 (max, min, __add__,ラムダ式,関数定義など)
        UNIT: 単位元
        a: 長さNの配列 a で初期化（a を与えない場合、単位元で初期化）
    注意: 内部的には 1-indexed
    """

    def __init__(self, N, operator, unit, a=None):
        self.op = operator
        self.UNIT = unit

        self.N0 = 2**(N-1).bit_length()
        self.tree = [self.UNIT]*(2*self.N0)
        if a != None:
            self.tree[self.N0:self.N0+N] = a[:]
            for k in range(self.N0-1, 0, -1):
                self.tree[k] = self.op(self.tree[2*k], self.tree[2*k+1])

    
    def update(self, k, x):
        k += self.N0
        self.tree[k] = x
        k //= 2
        while k:
            self.tree[k] = self.op(self.tree[2*k], self.tree[2*k+1])
            k //= 2

    
    def query(self, l, r):
        L = l + self.N0
        R = r + self.N0
        s = self.UNIT
        while L < R:
            if R & 1:
                R -= 1
                s = self.op(self.tree[R], s)
            if L & 1:
                s = self.op(s, self.tree[L])
                L += 1
            L >>= 1
            R >>= 1
        return s

    def get(self, k):  
        return self.tree[k + self.N0]

    def all(self):
        return self.tree[1]



INF = 2 ** 31 - 1
x = [INF] * N

seg = SegmentTree(N, min, INF)

ans = []

for com, x, y in QUERY:
    x, y = int(x), int(y)

    if com == '0':
        seg.update(x, y)
    else:
        q = seg.query(x, y + 1)
        ans.append(str(q))


print("\n".join(ans))

Solution (Python):
class SegmentTreeRMQ():
    """Range Minimum Query"""
    
    def __init__(self, lst, max_num=float("inf")):
        """
        Args:
            lst: 元のリスト
            max_num: セグ木の各ノードの初期値
        """
        self.MAX_NUM = max_num 
        N = len(lst)
        i, total = 1, 1
        while True:
            if N <= i:
                break
            i *= 2
            total += i
        self.N = i  
        self.nodes = [self.MAX_NUM for _ in range(total)]
        for i in range(len(lst)):
            self.update(i, lst[i])
    
    def update(self, i, x):
        """元のリストlst[i]に対応するセグ木のノード値をxに変更し、セグ木全体を更新する"""
        ni = self._lst2node(i)
        self.nodes[ni] = x
        while ni > 0:
            ni = (ni-1)//2
            l, r = ni*2+1, ni*2+2
            self.nodes[ni] = min(self.nodes[l], self.nodes[r])

    def query(self, a, b):
        """区間[a,b)のクエリに応答する"""
        return self._find(a, b, 0, 0, self.N)

    def _lst2node(self, i):
        """元の配列lst[i]は、セグ木のi+N-1番目のノード(Nは歯の数)"""
        return i+self.N-1
    
    def _find(self, a, b, k, l, r):
        """区間[a,b)のクエリに対して、担当区間[l,r)のノードkが応答する"""
        if r <= a or b <= l:
            
            return self.MAX_NUM
        if a <= l and r <= b:
            
            return self.nodes[k]
        
        ret1 = self._find(a, b, 2*k+1, l, (l+r)//2)  
        ret2 = self._find(a, b, 2*k+2, (l+r)//2, r)  
        return min(ret1, ret2)


N, Q = map(int, input().split())
lst = [2**31-1 for _ in range(N)]
rmq = SegmentTreeRMQ(lst, 2**31-1)

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