Problem:

Range Minimum Query (RMQ)

Write a program which manipulates a sequence A = {a0, a1, . . .  , an-1} with the following operations:

find(s, t): report the minimum element in as, as+1, . . . ,at.

update(i, x): change ai to x.

Note that the initial values of ai (i = 0, 1, . . .  , n&minus;1) are  231-1.

Input

n q
com0 x0 y0
com1 x1 y1
...
comq&minus;1 xq&minus;1 yq&minus;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(xi, yi) and '1' denotes find(xi, yi).

Output

For each find operation, print the minimum element.

Constraints

1 ≤ n ≤ 100000

1 ≤ q ≤ 100000

If comi is 0, then 0 ≤ xi < n, 0 ≤ yi < 231-1.

If comi is 1, then 0 ≤ xi < n, 0 ≤ yi < 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



Sample input:
3 5
0 0 1
0 1 2
0 2 3
1 0 2
1 1 2


Sample output:
1
2

Submission status: Accepted

Solution code:
#http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3990970#1

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)

#print(s.node)

Submission status: Accepted

Solution code:
class Rmq:
    # 平方分割
    # 値を変更すると元のリストの値も書き換わる
    # 検証: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3990652#1
    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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

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

# 一点更新　区間取得　1-indexed
class SegmentTree:
    def __init__(self, n):
        tmp = 1
        while tmp < n:
            tmp <<= 1
        # self.N : 完全二分木の葉の数(N以上の最小の2べき)
        self.N = tmp
        # 2*self.N - 1 : 完全二分木のノード数
        # 1-indexedで管理するので１つ余分に設ける
        self.Data = [inf for _ in range(2*self.N)]

    # k (0-indexed)
    def update(self, k, x):
        #　インデックスを補正
        k += self.N
        # 指定ノードを更新
        self.Data[k] = x
        # kを含む区間ノードを更新していく
        while k != 1:
            k >>= 1
            self.Data[k] = min([self.Data[2*k], self.Data[2*k+1]])

    # [l, r) (0-indexed)
    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))

Submission status: Accepted

Solution code:
INF_MAX = 2 ** 31 - 1


class Segment_tree():
    def __init__(self, N):
        self.N = 1
        while self.N < N:
            # 完全二分木にするために2のべき乗にする
            self.N *= 2

        self.dat = []
        for i in range(2 * self.N - 1):
            # indexが0を頂点とするsegment_treeを作る
            self.dat.append(INF_MAX)

    def update(self, k, x):
        k += self.N - 1
        # 指定しているkにsegmenttreeのindexを合わせる
        self.dat[k] = x
        while k > 0:
            # datの下から更新して行く
            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:
            # a,bが区間に存在しないとき
            return INF_MAX
        if a <= l and r <= b:
            # 区間a,bがl,rを完全に含んでいるとき
            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()

Submission status: Accepted

Solution code:
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):#区間[a,b)についてｋが答える
    if r<=a or b<=l:#はみ出る
        return 2**31-1
    if a<=l and r<=b:#含まれる
        return A[k]
    else:#ノード追うのが大変,##+1,+2
        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)###-1
        A[x] = y
        while x>0:
            x =(x-1)//2
            A[x] = min(A[x*2+1],A[x*2+2])##+1,+2
        #print(A)
            
    else:
        print(query(x,y+1,0,0,s))

Submission status: Accepted

Solution code:
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
        #print(len(self.array))
        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)

Submission status: Accepted

Solution code:
# AOJ DSL_2_A "Range Minimum Query"
# SegmantTreeの実装
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)]

    # k番目の値(0-indexed)をaに変更
    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][:]

    # [l, r)の最小値取得
    # kがNodeの番号、対応する区間が[a, b)
    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])

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

class SegmentTree:
    # リストからセグメントツリーを構成
    def __init__(self, list_, ide_ele=0):
        tmp = 1
        while tmp < len(list_):
            tmp *= 2
        self.n = tmp
        self.l = [ide_ele] * (2 * self.n - 1)
        self.ide_ele = ide_ele
        self.init_val(list_)

    def func(self, x, y):
        return min(x, y)

    def init_val(self, list_):
        # list_の値で葉を埋める
        for i, val in enumerate(list_):
            self.l[self.n - 1 + i] = val
        # 下の段から初期値を埋めていく
        for i in range(self.n-2, -1, -1):
            self.l[i] = self.func(self.l[i*2+1], self.l[i*2+2])
    
    # i番目をvalで更新
    def update(self, i, val):
        i = self.n - 1 + i
        self.l[i] = val
        while i > 0:
            i = (i-1) // 2
            self.l[i] = self.func(self.l[i*2+1], self.l[i*2+2])
    
    # [a, b)の最小値を返す. l, rはノードkに対応した区間
    def query(self, a, b, k, l, r):
        if r <= a or b <= l:# 存在しない区間を参照
            return self.ide_ele  # エラーを返す
        if a <= l and r <= b:# 区間を完全に含む
            return self.l[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.func(vl, vr)

def main():
    N, Q = map(int, input().split())
    tmp = (1 << 31) - 1
    seg = SegmentTree([tmp] * N, ide_ele=tmp)

    # print("init")
    # print(seg.l)

    for i in range(Q):
        c, x, y = map(int, input().split())
        if c == 0:
            # print("update: l[{}]={} -> {}".format(x, seg.l[x], y))
            seg.update(x, y)
        else:
            # print("min: {}~{}".format(x, y))
            print(seg.query(x, y+1, 0, 0, seg.n))
        # print(seg.l)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
INT_MAX = 2**31-1
MAX_N = 10**5

def init(n_):
    n = 1
    while n < n_:
        n *= 2
    dat = [INT_MAX] * (2*n-1)
    return n, dat

def update(k, a):
    k += n-1
    dat[k] = a
    while k > 0:
        k = (k-1) // 2
        dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2])

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

if __name__ == "__main__":
    n, q = map(int, input().split())
    n, dat = init(n)
    for i in range(q):
        com, x, y = map(int, input().split())
        if com == 0:
            update(x, y)
        elif com == 1:
            print(query(x, y+1, 0, 0, n))

Submission status: Accepted

Solution code:
class SqrtDecomposition():
    def __init__(self, array, f):
        self.dat = array
        self.f = f
        m = int(pow(len(array), 0.5))
        if m**2 < len(array):
            m += 1
        self.m = m
        self.dat2 = []
        for i in range(m):
            if i * m >= len(array):
                break
            self.dat2 += [f(self.dat[m * i:m * (i + 1)])]

    def update(self, a, x):
        m = self.m
        dat = self.dat
        dat2 = self.dat2
        f = self.f
        dat[a] = x
        a2 = a // m
        al = m * a2
        ar = al + m
        dat2[a2] = f(dat[al:ar])

    def query(self, a, b):
        dat = self.dat
        dat2 = self.dat2
        f = self.f
        m = self.m
        a2 = a // m
        ar = a2 * m + m
        b2 = b // m
        bl = b2 * m
        if ar > bl:
            return f(dat[a:b])
        else:
            return f(dat[a:ar] + dat2[a2 + 1:b2] + dat[bl:b])


N, Q = [int(_) for _ in input().split()]
Query = [[int(_) for _ in input().split()] for _ in range(Q)]
SD = SqrtDecomposition(array=[2**31 - 1] * N, f=min)
for query in Query:
    if query[0]:
        query[2] += 1
        print(SD.query(*query[1:]))
    else:
        SD.update(*query[1:])

Submission status: Accepted

Solution code:
class SegTree:
    def __init__(self,N,f,ini):
        """
        f(val,ini)=ini
        """
        n=1
        while n<N: n<<=1
        self.n=n
        self.arr=[ini]*(2*n-1)
        self.f,self.ini=f,ini
    
    def update(self,i,val):
        i += self.n-1
        self.arr[i]=val
        while i>0:
            i=(i-1)//2
            self.arr[i]=self.f(self.arr[2*i+1],self.arr[2*i+2])

    def find(self,s,t):
        """
        [s,t)
        """
        return self.__find(s,t,0,0,self.n)

    def __find(self,s,t,k,l,r):
        if t<=l or s>=r: return self.ini
        if s<=l and t>=r: return self.arr[k]
        vl=self.__find(s,t,2*k+1,l,(l+r)//2)
        vr=self.__find(s,t,2*k+2,(l+r)//2,r)
        return self.f(vl,vr)

N,Q=map(int,input().split())
CXY=[map(int,input().split()) for _ in range(Q)]
st = SegTree(N, lambda x,y: min(x,y), 2**31-1)

for c,x,y in CXY:
    if c==0:
        # update
        st.update(x,y)
    elif c==1:
        # find
        print(st.find(x,y+1))

Submission status: Accepted

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]

INF = (1<<31)-1

class Rmin():
	def __init__(self, size):
		#the number of nodes is 2n-1
		self.n = 1
		while self.n < size:
			self.n *= 2
		self.node = [INF] * (2*self.n-1)

	def Access(self, x):
		return self.node[x+self.n-1]

	def Update(self, 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])
		return

	#[a, b)
	def Get(self, a, b, k=0, l=0, r=-1):
		if r < 0:
			r = self.n

		if a >= r or b <= l:
			return INF
		elif a <= l and b >= r:
			return self.node[k]
		else:
			vl = self.Get(a, b, 2*k+1, l, (l+r)//2)
			vr = self.Get(a, b, 2*k+2, (l+r)//2, r)
			return min(vl, vr)

n, q = map(int, input().split())
SegT = Rmin(n)
for _ in range(q):
	c, x, y = map(int, input().split())
	if c == 0:
		SegT.Update(x, y)
	else:
		print(SegT.Get(x, y+1))

Submission status: Accepted

Solution code:
class RMQ(object):
    INF = 2 ** 31 - 1

    def __init__(self, num) -> None:
        n = 1
        while n < num:
            n = n * 2
        self.n = n
        self.val = [self.INF] * (2 * n - 1)

    @staticmethod
    def merge(a: int, b: int) -> int:
        return min(a, b)

    def update(self, k: int, x: int) -> None:
        k = k + self.n - 1
        self.val[k] = x
        while k:
            k = (k - 1) // 2
            self.val[k] = self.merge(self.val[k * 2 + 1], self.val[k * 2 + 2])

    def dfs(self, beg: int, end: int, k: int, l: int, r: int) -> int:
        if (end <= l or r <= beg):
            return self.INF
        if (beg <= l and r <= end):
            return self.val[k]
        vl = self.dfs(beg, end, k * 2 + 1, l, (l + r) // 2)
        vr = self.dfs(beg, end, k * 2 + 2, (l + r) // 2, r)
        return self.merge(vl, vr)

    def query(self, beg: int, end: int) -> int:
        return self.dfs(beg, end, 0, 0, self.n)


if __name__ == "__main__":
    n, q = map(lambda x: int(x), input().split())
    rmq = RMQ(n)

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

Submission status: Accepted

Solution code:
class SegmentTree:
    def __init__(self, N, mode=min):
        n_ = 1
        
        while n_ < N:
            n_ *= 2
            
        self.n = n_
        self.mode = mode
        
        if self.mode == min:
            self.arr = [2**31-1] * (2*self.n - 1)
        elif self.mode == max:
            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] = self.mode(self.arr[2*k+1], self.arr[2*k+2])
    
    def query(self, l, r):
        L, R = l + self.n, r + self.n
        
        if self.mode == min:
            res = 2**31-1
        else:
            res = -2**31+1
        
        while L < R:
            if R & 1:
                R -= 1
                res = self.mode(res, self.arr[R-1])
            
            if L & 1:
                res = self.mode(res, self.arr[L-1])
                L += 1
            
            L >>= 1
            R >>= 1
        
        return res

n, q = map(int, input().split())
st = SegmentTree(n, min)

for _ in range(q):
    com_i, xi, yi = map(int, input().split())
    
    if com_i == 0:
        st.update(xi, yi)
    else:
        print(st.query(xi, yi+1))

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

class SegmentTree:
    def __init__(self,N,d):
        self.NN = 1
        while self.NN < N:
            self.NN *= 2
        self.SegTree = [d]*(self.NN*2-1)

    def update(self,i,x): #iの値をxに更新
        i += self.NN - 1
        self.SegTree[i] = x
        while i>0:
            i = (i-1)//2
            self.SegTree[i] = self.process(self.SegTree[i*2+1],self.SegTree[i*2+2])

    def query(self,a,b,k=0,l=0,r=None): #[A,B)の値, 呼ぶときはquery(a,b)
        if r == None: r = self.NN
        if r <= a or b <= l: #完全に含まない
            return INF
        elif a <= l and r <= b : #完全に含む
            return self.SegTree[k]
        else: #交差する
            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.process(vl,vr))

    def process(self,x,y): #x,yが子の時，親に返る値
        return min(x,y)


N,Q = inpl()
ST = SegmentTree(N,2**31-1)

for _ in range(Q):
    c,x,y = inpl()
    if c == 0:
        ST.update(x,y)
    else:
        print(ST.query(x,y+1))

Submission status: Accepted

Solution code:
class SegTree:
    init_val = float('inf')  # 問題によって変える

    def __init__(self, init_l):
        self.n = len(init_l)
        self.n0 = 2 ** (self.n - 1).bit_length()  # n以上で最小の2のべき乗
        self.l = [self.init_val] * 2 * self.n0  # 区間外の値を初期化
        for i in range(self.n):
            self.l[i + self.n0 - 1] = init_l[i]
        for i in range(self.n0 - 2, -1, -1):
            self.l[i] = self.func(self.l[2 * i + 1], self.l[2 * i + 2])

    # 問題によって変える
    def func(self, x, y):
        return min(x, y)

    def update(self, i, new):
        i += self.n0 - 1
        self.l[i] = new
        while i + 1:
            i = (i - 1) // 2
            self.l[i] = self.func(self.l[i * 2 + 1], self.l[i * 2 + 2])

    # Gets min between [a, b)
    def query(self, a, b):
        return self._query(a, b, 0, 0, self.n0)

    def _query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return self.init_val
        if a <= l and r <= b:
            return self.l[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.func(vl, vr)

n, q = map(int, input().split())
l = [2**31-1]*n
s = SegTree(l)
for i in range(q):
    c, x, y = map(int, input().split())
    if c == 0:
        s.update(x, y)
    else:
        print(s.query(x, y+1))

Submission status: Accepted

Solution code:
INF = 2 ** 31 - 1
class SegmentTree:
	def __init__(self, n):
		self.N = 1
		while self.N < n:
			self.N *= 2
		self.tree = [INF] * (self.N * 2 - 1)

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

	def find(self, a, b, k, l, r):
		"""[a, b), ノードkが[l, r)を担当する"""
		if r <= a or b <= l:
			return INF
		if a <= l and r <= b:
			return self.tree[k]
		else:
			c1 = self.find(a, b, 2*k+1, l, (r+l)//2)
			c2 = self.find(a, b, 2*k+2, (l+r)//2, r)
			return min(c1, c2)

import sys
input = sys.stdin.readline
from operator import itemgetter

def main():
	n, q = map(int, input().strip().split())
	st = SegmentTree(n)
	for _ in range(q):
		com, x, y = map(int, input().strip().split())
		if com:
			print(st.find(x, y+1, 0, 0, st.N))
		else:
			st.update(x, y)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
class SegmentTree():
    """一点更新、区間取得クエリをそれぞれO(logN)で答えるデータ構造を構築する
    update: i番目をvalに変更する
    get_min: 区間[begin, end)の最小値を求める
    """
    def __init__(self, n):
        self.n = n
        self.INF = 2**31 - 1
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.node = [self.INF] * (2*self.size - 1)

    def update(self, i, val):
        i += (self.size - 1)
        self.node[i] = val
        while i > 0:
            i = (i - 1) // 2
            self.node[i] = min(self.node[2*i + 1], self.node[2*i + 2])

    def get_min(self, begin, end):
        begin += (self.size - 1)
        end += (self.size - 1)
        s = self.INF
        while begin < end:
            if (end - 1) & 1:
                end -= 1
                s = min(s, self.node[end])
            if (begin - 1) & 1:
                s = min(s, self.node[begin])
                begin += 1
            begin = (begin - 1) // 2
            end = (end - 1) // 2
        return s

    def debug(self):
        """Segment Tree上の葉の配列を出力する"""
        return(self.node[self.size - 1: self.size - 1 + self.n])


n, q = map(int, input().split())
info = [list(map(int, input().split())) for i in range(q)]
st = SegmentTree(n)

for i in range(q):
    com, x, y = info[i]
    if com == 0:
        st.update(x, y)
    else:
        print(st.get_min(x, y + 1))

Submission status: Accepted

Solution code:

class SegmentTree:

    def __init__(self, n, fn=lambda x, y: min(x, y), unity=(1 << 31) - 1):
        self.n = 1
        while self.n < n:
            self.n *= 2

        self.arr = [unity] * (2 * self.n - 1)
        self.fn = fn
        self.unity = unity

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

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

    def query(self, l, r):
        return self._inner_query(l, r, 0, 0, self.n)

    def _inner_query(self, l, r, k, il, ir):
        if ir <= l or r <= il:
            return self.unity

        elif l <= il and ir <= r:
            return self.arr[k]

        vl = self._inner_query(l, r, k * 2 + 1, il, (il + ir) // 2)
        vr = self._inner_query(l, r, k * 2 + 2, (il + ir) // 2, ir)
        return self.fn(vl, vr)

    def __str__(self):
        return self.arr[0: 2 * self.n].__str__()

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

for _ in range(q):
    com, o1, o2 = map(int, input().split())

    if com == 0:
        st.update(o1, o2)
    else:
        print(st.query(o1, o2 + 1))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline

import math
import sys
from collections import deque

class SegmentTree(object):

    def __init__(self,a,default):
        real_size=len(a)
        self.elem_size=elem_size=1<<math.ceil(math.log2(real_size))
        self.tree=tree=[default]*(elem_size*2-1)
        tree[elem_size:elem_size+real_size]=a
        self.default=default

        for i in range(elem_size-2,-1,-1): #ここで初期のsegtreeの構築
            l,r=tree[2*i+1],tree[2*i+2]
            tree[i]=l if l<r else r
    def get_value(self,x,y):#[x,y)で注意
        stack=deque([(x,y,0,0,self.elem_size)])
        tree=self.tree
        ans=self.default
        while(stack):
            x,y,k,l,r=stack.pop()
            if r<=x or y<=l:
                continue
            if x<=l and r<=y:
                ans=min(ans,tree[k])
            else:
                stack.append((x,y,k*2+1,l,(l+r)//2))
                stack.append((x,y,k*2+2,(l+r)//2,r))
        return ans
    def update(self,i,x):
        i+=self.elem_size-1
        tree=self.tree
        tree[i]=x
        while(i>0):
            i=(i-1)//2
            tree[i]=min(tree[i*2+1],tree[i*2+2])


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

Submission status: Accepted

Solution code:
class SegmentTree:
    
    def __init__(self, n):
        self.n = n
        self.T = T = [2**31 - 1 for _ in range(2*n-1)]
        
    def update(self, i, x):
        i += self.n - 1
        self.T[i] = x
        while(i > 0):
            i = (i - 1) // 2
            self.T[i] = min(self.T[i*2+1], self.T[i*2+2])
            
    def find(self, a, b, k, l, r):
        if r<= a or b<= l:
            return 2**31 - 1
        if a <= l and r <= b:
            return self.T[k]
        vl = self.find(a, b, k*2+1, l,(l+r)//2)
        vr = self.find(a, b, k*2+2, (l+r)//2,r)
        return min(vl, vr)
    

n_, q = [int(i) for i in input().split()]
n = 1
while(n < n_):
    n *= 2
T = SegmentTree(n)
for _ in range(q):
    c, x, y = [int(i) for i in input().split()]
    if c == 0:
        T.update(x, y)
    else:
        print(T.find(x, y+1, 0, 0, n))

Submission status: Accepted

Solution code:
import math

line = input()
n, q = list(map(int, line.split()))
N = 1
while N < n:
    N *= 2
a = [2 ** 31 - 1 for _ in range(0, 2 * N - 1)]

def update(k, v):
    k += N - 1
    a[k] = v
    while k > 0:
        k = (k - 1) // 2
        a[k] = min(a[k * 2 + 1], a[k * 2 + 2])

def query(x, y, k, l, r):
    if r <= x or y <= l:
        return 2 ** 31 - 1
    elif x <= l and r <= y:
        return a[k]
    m = (l + r) // 2
    return min(query(x, y, k * 2 + 1, l, m), query(x, y, k * 2 + 2, m, r))

for _ in range(0, q):
    line = input()
    c, x, y = list(map(int, line.split()))
    if c == 0:
        update(x, y)
    elif c == 1:
        ans = query(x, y + 1, 0, 0, N)
        print(ans)