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:
class SegmentTree:
    def __init__(self, size, f=lambda x,y : x+y, default=0):
        self.size = 2**(size-1).bit_length()
        self.default = default
        self.dat = [default]*(self.size*2)
        self.f = f

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])

    def query(self, l, r):
        l += self.size
        r += self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                rres = self.f(self.dat[r], rres)
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res

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

Submission status: Accepted

Solution code:
#A
import math
inf = 2**31 - 1

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

K = 1
while K < N:
    K *= 2


RMQ = [inf for _ in range(2*K-1)]
def find(s,t,i,l,r):
    if s > r or t < l:
        return inf
    
    if s <= l and t >= r:
        return RMQ[i]
    else:
        ml = find(s,t,2*i+1,l,(l+r)//2)
        mr = find(s,t,2*i+2,(l+r)//2+1,r)
        return min(ml,mr)
    

for _ in range(Q):
    c,x,y = map(int,input().split())
    
    if c == 0:
        RMQ[K+x-1] = y
        now = K+x-1
        while now > 0:
            n1 = now
            if now%2 == 0:
                now = now//2 - 1
            else:
                now //= 2
            RMQ[now] = min(RMQ[2*now+1],RMQ[2*now+2])
            
    else:
        print(find(x,y,0,0,(2*K-1)//2))

Submission status: Accepted

Solution code:
ide = 2**31-1
def func(a,b):
  return min(a,b)
class SegmentTree:
  def __init__(self,ls,commutative = True):
    if commutative:
      self.n = len(ls)
      self.tree = [ide for i in range(self.n)]+ls
    else:
      self.n = 2**((len(ls)-1).bit_length())
      self.tree = [ide for i in range(self.n)]+ls+[ide for i in range(self.n-len(ls))]
    for i in range(1,self.n)[::-1]:
      self.tree[i] = func(self.tree[i<<1|0],self.tree[i<<1|1])
  def getall(self):
    return self.tree[1]
  def get(self,l,r):
    ret = ide
    l += self.n
    r += self.n
    while l < r:
      if l&1:
        ret = func(self.tree[l],ret)
        l += 1
      if r&1:
        ret = func(ret,self.tree[r-1])
      l >>= 1
      r >>= 1
    return ret
  def update(self,i,x):
    i += self.n
    self.tree[i] = x
    while i > 1:
      i >>= 1
      self.tree[i] = func(self.tree[i<<1|0],self.tree[i<<1|1])
import sys
input = sys.stdin.readline
n,q = map(int,input().split())
a = [2**31-1]*n
sol = SegmentTree(a,commutative=False)
for _ in range(q):
  a,b,c = map(int,input().split())
  if a == 0:
    sol.update(b,c)
  else:
    print(sol.get(b,c+1))

Submission status: Accepted

Solution code:
class SegmentTree():
    maxval=(1<<31)-1

    def __init__(self,n,val=maxval):
        self.offset=self.setOffset(n)
        self.segTree=[val]*(2*self.offset+1)

    def init_array(self,array):
        for i in range(len(array)):
            self.segTree[i+self.offset]=array[i]
        for i in range(offset-1,-1,-1):
            self.segTree[i]=self.minChild(i)

    def setOffset(self,n):
        if n==1:
            return 1
        else:
            return (1<<(n-1).bit_length())-1

    def update(self,k,x):
        k+=self.offset
        self.segTree[k]=x
        while k:
            k=(k-1)>>1
            self.segTree[k]=self.minChild(k)

    def min_query(self,p,q):
        if p>=q:
            return

        p+=self.offset
        q+=self.offset-1
        segmin=self.maxval

        while q-p>1:
            #p%2==0
            if not p&1:
                segmin=min(segmin,self.segTree[p])
            #q%2==1
            if q&1:
                segmin=min(segmin,self.segTree[q])
                q-=1
            p=p>>1
            q=(q-1)>>1

        if p==q:
            return min(segmin,self.segTree[p])
        else:
            return min(min(segmin,self.segTree[p]),self.segTree[q])

    def minChild(self,n):
        return min(self.segTree[2*n+1],self.segTree[2*n+2])

n,q=map(int,input().split())
ST=SegmentTree(n)
for i in range(q):
    qry=list(map(int,input().split()))
    if qry[0]==0:
        ST.update(qry[1],qry[2])
    else:
        print(ST.min_query(qry[1],qry[2]+1))

Submission status: Accepted

Solution code:
class RMQ():
    def __init__(self, array):
        k = 1
        while k < len(array):
            k <<= 1
        self.halflen = k
        self.tree = [0] * k + array + [10 ** 18] * (k - len(array))
        for i in reversed(range(k)):
            self.tree[i] = min(self.tree[i << 1], self.tree[(i << 1) | 1])

    def update(self, i, value):
        i |= self.halflen
        self.tree[i] = value
        i >>= 1
        while i:
            self.tree[i] = min(self.tree[i << 1], self.tree[(i << 1) | 1])
            i >>= 1

    def query_(self, i, left, right, l, r):
        if (left, right) == (l, r):
            return self.tree[i]
        ret = 10 ** 18
        m = (l + r) >> 1
        if left <  m:
            ret = min(ret, self.query_(i << 1, left, min(m, right), l, m))
        if right > m:
            ret = min(ret, self.query_((i << 1) | 1, max(left, m), right, m, r))
        return ret

    def query(self, left, right):
        return self.query_(1, left, right, 0, self.halflen)

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

r = RMQ([2 ** 31 - 1] * n)
for com, x, y in query:
    if com == 0:
        r.update(x, y)
    else:
        print(r.query(x, y+1))

Submission status: Accepted

Solution code:

class RMQ:
    inf = 2147483647
    def __init__(self,n_):
        self.n_ = n_
        self.n = 1
        while self.n < n_: self.n*=2
        self.st = [self.inf]*(2*self.n-1)
    
    def update(self,k,x):
        k+=(self.n-1)
        self.st[k] = x
        while k >0:
            k = (k-1)//2
            self.st[k] = min(self.st[2*k+1],self.st[2*k+2])

    def search(self,a,b,k,l,r):
        if r<=a or b<=l :return self.inf
        if a<=l and r<=b:return self.st[k]
        L = self.search(a,b,k*2+1,l,(l+r)//2)
        R = self.search(a,b,k*2+2,(l+r)//2,r)
        return min(L,R)

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

def main():
    n,q = map(int,input().split())
    ST = RMQ(n)
    for _ in range(q):
        a,b,c = map(int,input().split())
        if a == 0:ST.update(b,c)
        else     :print (ST.query(b,c+1))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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):
        # query [l, r)
        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:  # update
		rmq.update(x, y)
	else:  # find
		print(rmq.query(x, y+1))

Submission status: Accepted

Solution code:

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))

Submission status: Accepted

Solution code:

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_lst1内のindexに変換
        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):
    # seg_lst1内のindexに変換
    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))

Submission status: Accepted

Solution code:
# Monoidクラスに+*/を定義するとLazySegmentTreeを使う時に便利？


# 1-indexed
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冪のうち最も小さいもの)
        n = 2 ** (len(bin(self.len + 1)) - 2)
        self.n = n
        # nodeの初期化
        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):
        # 最下層からはじめる。それより上にはn-1個のノードがある
        i += self.n
        self.node[i] = val
        # 最上層に辿り着くまで
        while i > 1:
            # 親に移動
            i //= 2
            # 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)

        # [a,b)が欲しい
        # k=0, [l=0,r=n)から始める
        # [l,r)が[a,b)の中に入るまで[l,mid), [mid,r)に分割して再帰
        def get(k, l, r):
            # そもそも[l,r)が[a,b)に入ってない時は計算に影響を与えない単位元を返す
            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

# https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_A

# 一例　([0..2^31-1],min)のモノイド
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))

Submission status: Accepted

Solution code:
class SegmentTree:
    def __init__(self, lst, op, e):
        self.n = len(lst)
        self.N = 1 << ((self.n - 1).bit_length())
        self.op = op # operation
        self.e = e # identity element
        self.v = self._build(lst) # self.v is set to be 1-indexed for simplicity
        
    def _build(self, lst):
        # construction of a tree
        # total 2 * self.N elements (tree[0] is not used)
        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]
    
    # update a_i to be x 
    def update(self, i, x):
        i += self.N
        self.v[i] = x
        while i > 0:
            i >>= 1 # move to parent
            self.v[i] = self.op(self.v[i << 1], self.v[(i << 1)|1])
    
    # returns answer for the query interval [l, r)
    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: # self.v[left] is the right child
                L = self.op(L, self.v[left])
                left += 1
            if right & 1: # self.v[right-1] is the left child
                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))

Submission status: Accepted

Solution code:
#普通のセグ木
'''
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])
    # l <= x <r
    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)

Submission status: Accepted

Solution code:
# operator.add(a, b)
# operator.mul(a, b)

"""
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)
    

# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_A
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))


# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B
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()
# AOJ_DSL_2_B()
# ABC125_C()

Submission status: Accepted

Solution code:
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): # [x, y)の半開区間を探索
    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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
class Segment_Tree:
    __slots__ = ['ide_ele', 'size', 'num', 'seg', 'segfunc']

    def __init__(self, size, func, element):
        #####単位元######
        self.ide_ele = element
        self.size = size

        #num:n以上の最小の2のべき乗
        self.num = 2 ** (self.size - 1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num

        #####segfunc######
        self.segfunc = func

    def apply(self, apply_seq):
        #set_val
        for i in range(self.size):
            self.seg[i + self.num - 1] = apply_seq[i]    
        #built
        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)

Submission status: Accepted

Solution code:
"""Range Minimum Query (RMQ)"""
# 丁寧に実装する


# 配列のidx番目の要素の値をxに変更する, 1点更新
def update(idx, x):
    idx += size-1  # 配列のidx番目の要素に対応するseg木のノードのindex
    seg[idx] = x  # 対象のノードの値を更新する
    # 親のノードの値も更新する
    while idx > 0:
        idx = (idx-1)//2  # ノードidxの親のindex, いつか0になる
        seg[idx] = min(seg[2*idx+1], seg[2*idx+2])  # 左右の子を見てminを計算する
    # 根ノードであるノード0まで修正したのでreturnする
    return


# この関数は半開区間[a, b)に対するクエリについて最小値を答えるもの
def query(a, b, k, l, r):  # 半開区間[a, b)に対するクエリについて、ノードk(担当している半開区間[l, r))が答える
    # 最初は根に質問を飛ばしている
    if r <= a or b <= l:  # ノードkの担当区間は[l, r)であり、この条件を満たすときは求めたい区間[a, b)と範囲が全く被っていない
        return INF  # 区間が被らない場合は単位元(minの単位元はINF)
    if a <= l and r <= b:
        return seg[k]  # ノードkの担当範囲が求めたい区間[a, b)に完全に含まれる場合はそのノードも持っている値をそのまま返す
    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)  # 左右の子のminを取る


N, Q = map(int, input().split())  # 配列のサイズ(管理したい要素の数), クエリの個数
size = 1  # seg木の葉の個数
while N > size:
    size *= 2  # seg木の葉の個数を計算する, N以上の最小の2冪数, 末端に来る葉の数が2の冪数でないと、seg木の構造がおかしくなる

# 単位元
# INF = float('inf')
INF = 2**31-1  # 今回の問題設定
# seg木を単位元で初期化する
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))  # ノード0(担当している半開区間[0, size))にクエリを投げる
        # y+1としているのは、半開区間とかの関係

Submission status: Accepted

Solution code:
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 # 処理(add or xor max minなど)

    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)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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()

Submission status: Accepted

Solution code:
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):
        # 1 + 2 + ... + N/2 = N-1
        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):
        # find [l, r)
        def _query(l, r, node_i, node_l, node_r):
            # node_i: node = value[node_i]
            # node_l: node.leftChild is in charge of [node_l, m)
            # node_r: node.rightChild is in charge of [m, 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()