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:
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()  # size
        self.data = [ele_id] * (2 * self.n - 1)  # binary tree (0-indexed)
        self.ele_id = ele_id  # identity element
        self.op_func = op_func  # binary operation of monoid

    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]  # set data in leaf
        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):
        # change i-th element to x (i : 0-indexed)
        i += self.n - 1
        self.data[i] = x
        while i > 0:
            i = (i - 1) // 2  # go to parenet-node
            self.data[i] = self.op_func(self.data[2 * i + 1],
                                        self.data[2 * i + 2])

    def query(self, a, b):
        # query for interval [a, b) (a, b : 0-indexed)
        return self.query_(a, b, 0, 0, self.n)

    def query_(self, a, b, k, l, r):
        if r <= a or b <= l:
            # [a, b) and [l, r) have no intersection
            return self.ele_id
        if a <= l and r <= b:
            # [a, b) includes [l, r)
            return self.data[k]
        else:
            # [a, b) and [l, r) have some overlap
            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)

Submission status: Accepted

Solution code:
#!python3

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
            #print(s, t)

        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:
            #for i,a in enumerate(A):
            #    print("*", " "*i*2,  *a)
            #print(*arg)
            res = find(*arg)
            print(res)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
INITIAL = 2 ** 31 - 1

class SegTreeMin:

    def __init__(self, V):
        # 元配列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)はノードがカバーする区間 => 対象区間
        '''
        # 最初に呼び出されたときのノードがカバーする区間は[0,N)
        if r < 0:
            r = self.N
        
        # 要求区間と対象区間が交わらない => 2147483647を返す
        if r <= a or l >= b:
            return INITIAL
        
        # 完全にカバーする場合
        if l >= a and r <= b:
            return self.node[k]

        # 一部分カバーする場合は子も探索する
        # 左側の子をvl 右側の子を vrとしている
        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()

Submission status: Accepted

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

# セグメント木
# senment-tree

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

    # a_k の値を x に更新
    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

    # 区間[l,r)をopでまとめる
    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):  # k番目の値を取得。query[k,k]と同じ
        return self.tree[k + self.N0]

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


#####単位元######
INF = 2 ** 31 - 1
x = [INF] * N
#seg = SegmentTree(x, segfunc=min, ide_ele=INF)
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))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/all/DSL_2_A
import sys
input = sys.stdin.readline

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

class RMQ:
    def __init__(self, n, e):
        # 単位元
        self.e = e
        # num_min:n以上の最小の2のべき乗
        self.num_min =2**(n-1).bit_length()
        self.seg_min=[self.e]*2*self.num_min

    def init_min(self, init_min_val):
        #初期値が指定されている場合
        #set_val
        for i in range(n):
            self.seg_min[i+self.num_min-1]=init_min_val[i]
        #built
        for i in range(self.num_min-2,-1,-1) :
            self.seg_min[i]=min(self.seg_min[2*i+1],self.seg_min[2*i+2])

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

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

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

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

Submission status: Accepted

Solution code:
class segmentTreeMin():
    # とりあえず9 * 12桁
    inf = 2**31 - 1
    dat = []
    lenData = -1

    def __init__(self):
        pass

    def load(self, l):
        # len(l)個よりも大きい2の二乗を得る
        self.lenData = 2 ** (len(l) - 1).bit_length()  # len 5 なら 2^3 = 8
        self.dat = [self.inf] * (self.lenData * 2)
        # 値のロード
        for i in range(len(l)):
            self.dat[self.lenData - 1 + i] = l[i]
        self.build()

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

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

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

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


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

Submission status: Accepted

Solution code:
INF = 2 ** 31 - 1


class SegmentTree:
    """
    参考: https://www.creativ.xyz/segment-tree-abstraction-979/
    """
    n = 1
    data = None  # データ
    def_ = None  # 初期値かつ単位元

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

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

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

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

        # 完全に内包
        if a <= l and r <= b: return self.data[k]

        vl = self._query(a, b, k * 2 + 1, l, (l + r) // 2)  # 左の子
        vr = self._query(a, b, k * 2 + 2, (l + r) // 2, r)  # 右の子
        return self.operation(vl, vr)

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

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


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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

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

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


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

Submission status: Accepted

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

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

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

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

class SegmentTree:
    def __init__(self,v):
        """
        :param v:元配列
        """
        size = len(v)
        self.n = 1
        while self.n < size:
            self.n *= 2
        # 木全体で必要なノード数は2n-1
        self.node = [0] * (2*self.n-1)
        # 最下段に値を代入
        for i, e in enumerate(v):
            self.node[i+self.n-1] = e
        # 上段は、下の段を利用する
        for i in range(self.n-2,-1,-1):
            self.node[i] = min(self.node[2*i+1], self.node[2*i+2])

    def update(self, x, val):
        """
        :param x: インデックス
        :param val: 更新する値
        """
        # 最下段にアクセス
        x += (self.n-1)
        # 上に登りながら更新していく
        self.node[x] = val
        while(x > 0):
            x = (x-1) // 2
            self.node[x] = min(self.node[2*x+1],self.node[2*x+2])
    
    def getmin(self, a, b, k=0, l=0, r=-1):
        """
        :param a: 要求区間の左 [
        :param b: 要求区間の右 )
        :param k: 現在のインデックス
        :param l: 対象区間の左
        :param r: 対象区間の右
        """
        INF = 2**31-1
        # 最初に呼び出されたとき、対象区間は[0,n)
        if (r < 0): r = self.n        
        # print("check",a,l,r,b)
        
        # 要求区間と対象区間が交わらない -> 適当に返す
        if (r<=a or b<=l): 
            return INF

        # 要求区間が対象区間を完全に被覆 -> 対象区間を答えの計算に使う
        if (a <= l and r <= b): 
            return self.node[k]

        # 要求区間が対象区間の一部を被覆 -> 子を探索
        # 左側をv1, 右側をv2
        vl = self.getmin(a, b, 2*k+1, l, (l+r)//2)
        vr = self.getmin(a, b, 2*k+2, (l+r)//2, r)
        return min(vl, vr)

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

Submission status: Accepted

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


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


def aoj():
    # https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_A
    N, Q = map(int, input().split())
    default = (1 << 31) - 1
    rmq = SegmentTree(N, min, default)
    for _ in range(Q):
        com, x, y = map(int, input().split())
        if com == 0:
            rmq.update(x, y)
        else:
            print(rmq.query(x, y+1))


if __name__ == '__main__':
    # yosupo()
    aoj()

Submission status: Accepted

Solution code:
import operator
import os
import sys
from functools import reduce

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

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


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

        # size 以上である最小の 2 冪を size とする
        n = 1
        while n < size:
            n *= 2
        self._size = n
        self._fn = fn

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

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

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

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

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

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

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

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

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


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

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

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

Submission status: Accepted

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

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


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


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

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

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

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, q = [int(s) for s in input().split()]
max_n = 2**31-1
m = 1
while m < n:#nが2の冪乗でないときに2の冪乗
    m *= 2

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

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

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

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

Submission status: Accepted

Solution code:
maximam = 2**31 - 1

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

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

segtre = Segment_Tree(N)

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

Submission status: Accepted

Solution code:

def make_ST(n,first): #firstで初期化された、葉がn要素を超えるように2のべき乗個用意されたリストを返す

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

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

        i += 1

    return ret

def RMQ_update_point(num,point,tree): #葉のindex(0-origin)がpointの要素をnumにする/treeはセグ木

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

    return

def RMQ_query(a,b,k,l,r,tree): #query区間左,右,注目ノード番号,担当範囲左,担当範囲右,木

    if r <= a or b <= l: #区間が完全にかぶらない場合inf
        return float("inf")
    
    if a <= l and r <= b: #区間が完全に含まれる場合自分
        return tree[k]

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

    return min(c1,c2)
        

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

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

for i in range(q):

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

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

Submission status: Accepted

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

class SegmentTree:
    def __init__(self, n): #a1, a2, ..., an
        n_ = 1
        while n_ < n:
            n_ *= 2

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

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

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

    def query(self, l, r):#[l,r)の値を返す
        L, R = l+self.n, r+self.n
        ide_ele = 2**31-1
         #ex) 最小値のセグ木 → +inf
         #　和のセグ木 → 0
         #　積のセグ木 → 1
         #  gcdのセグ木 → 0
        res = ide_ele
        while L < R:
            if R & 1:
                R -= 1
                res = func(res, self.arr[R-1])

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

            L >>= 1
            R >>= 1

        return res
#0-indexedな気がする
n,q=map(int,input().split())
sg=SegmentTree(n)
for _ in range(q):
    c,x,y=map(int,input().split())
    if c==0:
        sg.update(x,y)
    else:
        print(sg.query(x,y+1))