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
sys.setrecursionlimit(10000)


def initRMQ(n, D):
    n_ = 1

    while n_ < n:
        n_ *= 2

    for i in range(2*n_ - 1):
        D.append(2147483647)

    return n_


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


def findMin(a, b):
    return query(a, b + 1, 0, 0, n_)


def query(a, b, k, l, r):
    #print('q', a, b, k, l, r)
    if r <= a or b <= l:
        return 2147483647

    if a <= l and r <= b:
        return D[k]

    vl = query(a, b, k*2 + 1, l, int((l + r)/2))
    vr = query(a, b, k*2 + 2, int((l + r)/2), r)

    return min(vl, vr)


if __name__ == '__main__':
    n, q = map(int, input().split())

    D = []
    n_ = initRMQ(n, D)

    for _ in range(q):
        #print(D)
        c, x, y = map(int, input().split())

        if c == 0:
            update(x, y)

        else :
            print(findMin(x, y))

Submission status: Accepted

Solution code:
# coding: utf-8

inf = 2**31-1

class SegTree:
  size = 0
  node = []

  def __init__(self, n):
    self.size = 1
    while self.size < n:
      self.size *= 2
    self.node = [inf]*(2*self.size-1)
  
  def update(self, k, x):
    k += self.size-1
    self.node[k] = x
    while k > 0:
      k = (k-1)//2
      self.node[k] = min(self.node[k*2+1], self.node[k*2+2])
  
  def query(self, l, r, k=0, a=0, b=None):
    if b == None:
      k = 0
      a = 0
      b = self.size
    if b <= l or r <= a:
      return inf
    if(l <= a and b <= r):
      return self.node[k]
    
    return min(self.query(l, r, k*2+1, a, (a+b)//2), self.query(l, r, k*2+2, (a+b)//2, b))
  
  def debug(self):
    for i in range(self.size):
      print(self.node[i+self.size-1], end=' ')
    print()

n, q = map(int, input().split(' '))
sg = SegTree(n)
for i in range(q):
  tp, a, b = map(int, input().split(' '))
  if tp == 0:
    sg.update(a, b)
  else:
    b += 1
    print(sg.query(a, b))

Submission status: Accepted

Solution code:
import math

class SegmentTree:
    def __init__(self, n, max=float('inf')):
        self.N = 1 << math.ceil(math.log(n, 2))
        self.MAX_VAL = max
        self.tree = [self.MAX_VAL] * (self.N << 1)

    def update(self, idx, val):
        idx += self.N
        self.tree[idx] = val
        while idx > 1:
            self.tree[idx >> 1] = val = min(val, self.tree[idx ^ 1])
            idx >>= 1

    def find_min(self, frm, to, k=0, left=0, right=0):
        if right <= frm or to <= left:
            return self.MAX_VAL
        if frm <= left and right <= to:
            return self.tree[k]
        mid = (left + right) / 2
        return min(self.find_min(frm, to, k*2, left, mid),
                   self.find_min(frm, to, k*2+1, mid, right))

n, q = map(int, input().split())
st = SegmentTree(n, (1 << 31) - 1)
for _ in range(q):
    com, n1, n2 = map(int, input().split())
    if com == 0:
        st.update(n1, n2)
    else:
        print(st.find_min(n1, n2+1, 1, 0, st.N))

Submission status: Accepted

Solution code:
class SegmentTree:
    def __init__(self, N_, element, function_=(lambda l, r: l + r)):
        """
        :param N_: セグ木のサイズ
        :param element: 単位元
        :param function: 子の要素に対して行われる計算,デフォルトだと加算
        """
        self.N = 1
        while self.N < N_:
            self.N *= 2

        self.element = element
        self.dat = [element for _ in range(self.N * 2)]
        self.function = function_

    def update(self, k, a):
        """k番目の値(0-indexed)をaに変更"""
        k += self.N - 1
        self.dat[k] = a

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

    def query(self, begin, end, k=None, l=None, r=None):
        if k is None: return self.query(begin, end, 0, 0, self.N)

        if r <= begin or end <= l: return self.element
        if begin <= l and r <= end: return self.dat[k]

        vl = self.query(begin, end, k * 2 + 1, l, (l + r) // 2)
        vr = self.query(begin, end, k * 2 + 2, (l + r) // 2, r)
        return self.function(vl, vr)


n, q = map(int, input().split())
n += 1
treeone = SegmentTree(n, 2147483647, (lambda l, r: min(l, r)))

while q > 0:
    q -= 1
    tmp = list(map(int, input().split()))
    if tmp[0] is 0:
        treeone.update(tmp[1], tmp[2])
    else:
        print(treeone.query(tmp[1], tmp[2] + 1))

Submission status: Accepted

Solution code:
INF = 10 ** 20

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

size = 1
while size < n:
  size *= 2
size = size * 2 - 1

seg_tree = [2 ** 31 - 1 for _ in range(size)]

def update(i, x):
  ind = size // 2 + i 
  seg_tree[ind] = x
  while ind:
    ind = (ind - 1) // 2
    ch1 = seg_tree[ind * 2 + 1]
    ch2 = seg_tree[ind * 2 + 2]
    seg_tree[ind] = min(ch1, ch2)

def _find(s, t, k, l, r):
  if r < s or t < l: return INF
  if s <= l and r <= t:
    return seg_tree[k]
  else:
    vl = _find(s, t, k * 2 + 1, l, (l + r) // 2)
    vr = _find(s, t, k * 2 + 2, (l + r) // 2 + 1, r)
    return min(vl, vr)

def find(s, t):
  return _find(s, t, 0, 0, size // 2)

for _ in range(q):
  com, x, y = map(int, input().split())
  if not com:
    update(x, y)
  else:
    print(find(x, y))

Submission status: Accepted

Solution code:
import math

INIT_VAL = pow(2, 31)-1

class SegmentTree():
    def __init__(self, n):
        self.n = n
        self.height = math.ceil(math.log2(n))
        self.nodes = [INIT_VAL for i in range(pow(2, self.height+1)-1)]
        self.leaf_start = pow(2, self.height)-1

    def update(self, i, x):
        pntr = self.leaf_start + i
        self.nodes[pntr] = x
        while True:
            pntr = (pntr-1)//2
            if pntr == -1: break
            l, r = pntr*2 + 1, pntr*2 + 2
            self.nodes[pntr] = min(self.nodes[l], self.nodes[r])

    def __query(self, s, t, k, l, r):
        if t - s <= 0: return INIT_VAL
        if r <= s or t <= l: return INIT_VAL
        if l == s and t == r: return self.nodes[k]
        else:
            m = (l+r)//2
            if t <= m:
                return self.__query(s, t, k*2+1, l, m)
            elif m <= s:
                return self.__query(s, t, k*2+2, m, r)
            else:
                vl = self.__query(s, m, k*2+1, l, m)
                vr = self.__query(m, t, k*2+2, m, r)
                return min(vl, vr)

    def find(self, s, t):
        return self.__query(s, t+1, 0, 0, pow(2, self.height))

n, q = list(map(int, input().split(' ')))
st = SegmentTree(n)
for i in range(q):
    com, x, y = list(map(int, input().split(' ')))
    if com == 0:
        st.update(x, y)
    elif com == 1:
        print(st.find(x, y))

Submission status: Accepted

Solution code:
import bisect
import collections
import heapq
import itertools
import operator
import sys


def main():
    int_max = 2 ** 31 - 1
    n, q = map(int, sys.stdin.readline().split())
    n = 1 << (n - 1).bit_length()
    dat = [int_max] * 131072 * 2

    def update(i, x):
        i += n - 1
        dat[i] = x
        while i > 0:
            i = (i - 1) // 2
            dat[i] = min(dat[i * 2 + 1], dat[i * 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)

    for _ in range(q):
        com, x, y = map(int, sys.stdin.readline().split())
        if com == 0:
            update(x, y)
        elif com == 1:
            print(query(x, y + 1, 0, 0, n))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

class RangeMinimumQuery:
    nmemb = 1
    size  = 1
    data  = []
    def __init__(self, n):
        self.nmemb = n
        while self.size < n: self.size *= 2
        self.data = [0] * (self.size * 2)
        
    def __find(self, start, end, id, left, right):
        if end <= left or right <= start:
            return 2 ** 31 - 1
        elif start <= left and right <= end:
            return self.data[id]
        else:
            mid = (left + right) / 2
            vl = self.__find(start, end, id * 2 + 1, left, mid)
            vr = self.__find(start, end, id * 2 + 2, mid, right)
            return min(vl, vr)
            
    def find(self, start, end):
        return self.__find(start, end, 0, 0, self.size)
        
    def update(self, pos, value):
        pos += self.size - 1
        self.data[pos] = value
        
        while(pos > 0):
            pos = (pos - 1) / 2
            vl = self.data[pos * 2 + 1]
            vr = self.data[pos * 2 + 2]
            self.data[pos] = min(vl, vr)
            
if __name__ == "__main__":
    n, q = map(int, raw_input().split())
    rmq = RangeMinimumQuery(n)

    for i in range(n):
        rmq.update(i, 2 ** 31 - 1)
        assert(rmq.find(i, i + 1) == 2 ** 31 - 1)
        
    for i in range(q):
        com, x, y = map(int, raw_input().split())
        if com == 0:
            rmq.update(x, y)
        else:
            print(rmq.find(x, y + 1))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin


def main(init=int(2**31-1), readline=stdin.readline):
    n, q = (int(s) for s in readline().split())

    a = [init] * n
    b = [init] * ((n // 100) + 1)

    for _ in range(q):
        com, x, y = (int(s) for s in readline().split())
        if com:
            bx = x - (x % 100) + 100
            by = y - (y % 100)
            if bx < by:
                m = min(min(a[x:bx]), min(b[bx//100:by//100]),
                        min(a[by:y+1]))
            else:
                m = min(a[x:y+1])
            print(m)
        else:
            a[x] = y
            bx = x - (x % 100)
            b[x//100] = min(a[bx:bx+100])


main()

Submission status: Accepted

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

class SegTree:
    def __init__(self, size, f, I):
        n = 1
        while n < size:
            n <<= 1
        self.size = n
        self.f = f
        self.I = I
        self.node = [I] * (2*n)

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

    def query(self, a, b):
        L = R = self.I
        a += self.size
        b += self.size
        while a < b:
            if a & 1:
                L = self.f(L, self.node[a])
                a += 1
            if b & 1:
                b -= 1
                R = self.f(self.node[b], R)
            a //= 2
            b //= 2
        return self.f(L, R)

n, q = map(int, input().split())
rmq = SegTree(n, lambda x, y: min(x, y), (1 << 31) - 1)
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))

Submission status: Accepted

Solution code:
import sys

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    n,q = LI()

    n0 = 2**((n-1).bit_length())
    st = [2**31-1] * (n0*2)

    def find(s,t):
        s += n0; t += n0
        ret = 2**31 - 1
        while s < t:
            if s % 2:
                ret = min(ret,st[s-1])
                s += 1
            if t % 2:
                t -= 1
                ret = min(ret,st[t-1])
            s >>= 1; t >>= 1
        return ret

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

    for _ in range(q):
        c,x,y = LI()
        if c == 0:
            update(x,y)
        else:
            print(find(x,y+1))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class SEGTree:
    def __init__(self,n,fanction,unit):
        self.Unit=unit
        i=1<<(n.bit_length()-1)
        if i!=n:
            i*=2
        self.Fanction=fanction
        self.SEG=[self.Unit]*(2*i-1)
        self.d=i
    def update(self,i,x):
        i+=self.d-1
        self.SEG[i]=x
        while i>0:
            i=(i-1)//2
            self.SEG[i]=self.Fanction(self.SEG[i*2+1],self.SEG[i*2+2])
    def find(self,a,b,k,l,r):
        if r<=a or b<=l:
            return self.Unit
        if a<=l and r<=b:
            return self.SEG[k]
        else:
            c1=self.find(a,b,2*k+1,l,(l+r)//2)
            c2=self.find(a,b,2*k+2,(l+r)//2,r)
            return self.Fanction(c1,c2)
    def get(self,a,b):
        return self.find(a,b,0,0,self.d)

n,q=map(int,input().split())
SEG=SEGTree(n,min,2**31-1)
for _ in range(q):
    com,x,y=map(int,input().split())
    if com==0:
        SEG.update(x,y)
    else:
        print(SEG.get(x,y+1))

Submission status: Accepted

Solution code:
n,q=map(int,input().split())

class RMQ:
    def __init__(self, N,INF=2**31-1):
        self.N0 = 2**(N-1).bit_length()
        self.INF=INF
        self.data = [INF]*(2*self.N0)

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

    def query(self, l, r):
        L = l + self.N0; R = r + self.N0
        s = self.INF
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, self.data[R-1])

            if L & 1:
                s = min(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

rmq = RMQ(n+1)

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

Submission status: Accepted

Solution code:
#####segfunc#####
def segfunc(x, y):
    return min(x, y)
#################


#####ide_ele#####
ide_ele = pow(2, 31) - 1
#################


class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """

    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res


# a = [14, 5, 9, 13, 7, 12, 11, 1, 7, 8]
# seg = SegTree(a, segfunc, ide_ele)
# # [0, 8)の最小値を表示
# print(seg.query(0, 8))  # 1

# # 5番目を0に変更
# seg.update(5, 0)

# # [0, 8)の最小値を表示
# print(seg.query(0, 8))  # 0
n, q = map(int, input().split())
a = [pow(2, 31) - 1] * n
seg = SegTree(a, segfunc, ide_ele)
for _ in range(q):
    com, *xy = map(int, input().split())
    if com == 0:
        # print(xy[0], xy[1])
        seg.update(xy[0], xy[1])
    else:
        v = seg.query(xy[0], xy[1] + 1)
        print(v)

Submission status: Accepted

Solution code:
# N: 処理する区間の長さ
N, Q = map(int, input().split())
N0 = 1<<(N.bit_length())
INF = (1<<31)-1
data = [INF]*(2*N0)
# a_k の値を x に更新
def update(k, x):
  k += N0-1
  data[k] = x
  while k >= 0:
    k = (k - 1) // 2
    data[k] = min(data[2*k+1], data[2*k+2])
# 区間[l, r)の最小値
def query(l, r):
  L = l + N0-1; R = r + N0-1
  s = INF
  while L < R:
    if R%2==0:
      R -= 1
      s = min(s, data[R])
    if L%2==0:
      s = min(s, data[L])
      L += 1
    L //= 2; R //= 2
  return s

ans = []
for i in range(Q):
  com,x,y = map(int, input().split())
  if com==0:
    update(x,y)
  else:
    ans.append(query(x,y+1))
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
from collections import deque

def pow_two_more_than(a):
    # print(a, a & (a - 1), bin(a), 1 << (len(bin(a))-2))
    if (a & (a - 1)) == 0:
        return a
    # print(1 << (len(bin(a))-2))
    return 1 << (len(bin(a))-2)

class SegmentTree:
    def __init__(self, n, l):
        self.n = pow_two_more_than(n)
        self.tree = [2**31-1]*self.n + l + [2**31-1]*(self.n-len(l))
        for i in reversed(range(1, self.n)):
            self.update_one_node(i)

    def update(self, index, m):
        x = self.n+index
        self.tree[x] = m
        while x >= 1:
            x //= 2
            self.update_one_node(x)
        # print(self.tree)
    
    def find(self, rl, rr):
        # print(f"find: [{rl}, {rr})")
        # print(self.tree[self.n:])
        min_num = 2**31-1
        q = deque([1])
        c = 0
        while q:
            # print(q)
            t = q.popleft()
            # print(t)
            height = len(bin(t)) - 3
            x = t ^ (1<<height)
            w = (self.n>>height)
            l, r = w*x, w*(x+1)
            # print((l, r), height, end=" ")
            if rl <= l and r <= rr:
                # print("complatly in")
                min_num = min(min_num, self.tree[t])
            elif r <= rl or rr <= l:
                pass
                # print("out")
            else:
                # print((l, r), (rl, rr))
                # print("overlap")
                for c in self.get_childs(t):
                    if c < self.n*2:
                        q.append(c)
            c += 1
        # print(c)
        return min_num

    def update_one_node(self, m):
        self.tree[m] = min(self.tree[c] for c in self.get_childs(m))

    # def update(self)

    def get_childs(self, m):
        return [2*m, 2*m+1]

N, Q = map(int, input().split())
CXY = [list(map(int, input().split())) for _ in range(Q)]
# N, Q = 10**5, 10**5
# CXY = [[0, i, i] for i in range(Q//2)] + [[1, 0, 0] for i in range(Q-Q//2)]

segtree = SegmentTree(N, [2**31-1]*N)

for c, x, y in CXY:
    if c == 0:
        segtree.update(x, y)
    else:
        x, y = x, y+1
        r = segtree.find(x, y)
        print(r)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


class SegmentTree:
    def __init__(self, N, X, func, init_v):
        self.N = N
        self.func = func
        self.init_v = init_v
        self.__build(X)

    def __build(self, X):
        self.node = [self.init_v] * (2 * self.N)  # 1-based index
        for i, x in enumerate(X, self.N):
            self.node[i] = x
        for i in range(self.N - 1, 0, -1):
            self.node[i] = self.func(self.node[i << 1], self.node[i << 1 | 1])

    def update(self, i, x):
        i += self.N - 1
        self.node[i] = x
        while i > 1:
            i >>= 1
            self.node[i] = self.func(self.node[i << 1], self.node[i << 1 | 1])

    def query(self, l, r):
        dst_l = self.init_v
        dst_r = self.init_v
        l += self.N - 1
        r += self.N - 1
        while l < r:
            if l & 1:
                dst_l = self.func(dst_l, self.node[l])
                l += 1
            if r & 1:
                r -= 1
                dst_r = self.func(self.node[r], dst_r)
            l >>= 1
            r >>= 1
        return self.func(dst_l, dst_r)


def main():
    N, Q = map(int, input().split())
    a = [2 ** 31 - 1] * N

    st = SegmentTree(N, a, func=min, init_v=float("inf"))

    ans = []
    for _ in range(Q):
        com, x, y = map(int, input().split())
        if com == 0:
            # update
            x += 1  # For AOJ input type (0-based index)
            st.update(x, y)
        else:
            # find
            x += 1  # For AOJ input type (0-based index)
            y += 1  # For AOJ input type (0-based index)
            ans.append(st.query(x, y + 1))

    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

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:
class SegTree:
    """
    内部実装1-indexed．
    set_valやfoldには0-indexedでアクセス．
    2べきに直さなくてよい．
    Range Minimum Query．
    X_unit 大きい数 X_f min
    """
    X_unit = 2147483647  # (1 << 31) - 1
    X_f = min

    def __init__(self, N):
        self.N = N
        self.X = [self.X_unit] * (N + N)

    def build(self, seq):
        for i, x in enumerate(seq, self.N):
            self.X[i] = x
        for i in range(self.N - 1, 0, -1):
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def set_val(self, i, x):
        i += self.N
        self.X[i] = x
        while i > 1:
            i >>= 1
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def fold(self, L, R):
        L += self.N
        R += self.N
        vL = self.X_unit
        vR = self.X_unit
        while L < R:
            if L & 1:
                vL = self.X_f(vL, self.X[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.X_f(self.X[R], vR)
            L >>= 1
            R >>= 1
        return self.X_f(vL, vR)


def main():
    N, Q = (int(i) for i in input().split())
    seg = SegTree(N)
    for _ in range(Q):
        com, x, y = (int(i) for i in input().split())
        if com == 0:
            seg.set_val(x, y)
        else:
            print(seg.fold(x, y+1))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

INF = 2**31 - 1

SGM = []
n = 0


def init(_n):

    global SGM, n

    n = 1
    while _n > n:
        n *= 2

    SGM = [INF] * (n * 2)


def update(k, x):

    global SGM, n

    k += n - 1  # セグメント木の index に直す
    SGM[k] = x  # i を更新

    # 先祖を更新
    while k > 0:
        k = (k - 1) // 2
        SGM[k] = min(SGM[k * 2 + 1], SGM[k * 2 + 2])


def find(a, b, k, l, r):
    # 節点k がカバーする左側 : l
    # 節点k がカバーする右側 +1 : r

    # 節点 k のエリア [l, r) が、 [a, b) と交差しない場合
    if r <= a or b <= l:
        return INF

    # [a, b) が k -> [l, r) を完全に含む場合
    if a <= l and r <= b:
        return SGM[k]

    # [l, r) に含まれている場合、一段下を捜索
    vl = find(a, b, k * 2 + 1, l, (l + r) // 2)
    vr = find(a, b, k * 2 + 2, (l + r) // 2, r)
    v = min(vl, vr)

    return v


def main():

    global SGM, n
    n, q = map(int, sys.stdin.readline().rstrip().split())

    init(n)

    for i in range(q):
        com, x, y = map(int, sys.stdin.readline().rstrip().split())

        if com == 0:
            update(x, y)
            # print(SGM[n - 1:-1])
        else:
            v = find(x, y + 1, 0, 0, n)  # 区間のとり方の都合上、 y+1 にする
            # print(SGM[n - 1:-1])
            # print(f"find : [{x},{y}]: {v}")
            print(v)


main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

#from collections import defaultdict
#from heapq import heappush, heappop
#import numpy as np
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 2 ** 31 - 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7

debug_indent = 0


def debug(*x):
    global debug_indent
    x = list(x)
    indent = 0
    if x[0].startswith("enter") or x[0][0] == ">":
        indent = 1
    if x[0].startswith("leave") or x[0][0] == "<":
        debug_indent -= 1
    x[0] = "  " * debug_indent + x[0]
    print(*x, file=sys.stderr)
    debug_indent += indent


def set_depth(depth):
    global N, SEGTREE_SIZE, NONLEAF_SIZE
    N = depth
    SEGTREE_SIZE = 1 << N
    NONLEAF_SIZE = 1 << (N - 1)


def point_set(table, pos, value, binop):
    pos = pos + NONLEAF_SIZE
    table[pos] = value
    while pos > 1:
        pos >>= 1
        table[pos] = binop(
            table[pos * 2],
            table[pos * 2 + 1],
        )


def range_reduce(table, left, right, binop, unity):
    ret_left = unity
    ret_right = unity
    left += SEGTREE_SIZE // 2
    right += SEGTREE_SIZE // 2
    while left < right:
        if left & 1:
            ret_left = binop(ret_left, table[left])
            left += 1
        if right & 1:
            right -= 1
            ret_right = binop(table[right], ret_right)

        left //= 2
        right //= 2
    return binop(ret_left, ret_right)


def main():
    # parse input
    N, Q = map(int, input().split())
    depth = N.bit_length() + 1
    set_depth(depth)
    table = [INF] * SEGTREE_SIZE

    for _q in range(Q):
        q, x, y = map(int, input().split())
        if q == 0:
            # update
            point_set(table, x, y, min)
        else:
            # find
            print(range_reduce(table, x, y + 1, min, INF))


# tests
T1 = """
3 5
0 0 1
0 1 2
0 2 3
1 0 2
1 1 2
"""


def test_T1():
    """
    >>> as_input(T1)
    >>> main()
    1
    2
    """
# add tests above


def _test():
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())

    def input():
        return bytes(f.readline(), "ascii")

    def read():
        return bytes(f.read(), "ascii")


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        print("testing")
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Accepted

Solution code:
MAXN = 2 ** 17

ide_ele = 2 ** 31 - 1

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

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

def init(init_val):
    for i in range(n):
        seg[i+num-1] = init_val[i]
    for i in range(num-2 ,-1, -1) :
        seg[i] = segfunc(seg[2*i+1],seg[2*i+2])
        
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = min(seg[k*2+1] , seg[k*2+2])
        
def query(p,q):
    p += num
    q += num
    res = ide_ele
    
    while q-p > 0:
        if p&1 == 1:
            res = min(res,seg[p-1])
            p += 1
            
        if q&1 == 1:
            q -= 1
            res = min(res,seg[q-1])
            
        p >>= 1
        q >>= 1
    return res

for i in range(q):
    com = input().split()
    if com[0] == "0":
        x,y = int(com[1]),int(com[2])
        update(x,y)
    else:
        x,y = int(com[1]),int(com[2])+1
        print(query(x,y))

Submission status: Accepted

Solution code:
from copy import *

def init(N,node,unit,func):
  n=1
  while n<N:
    n<<=1
  for i in range(n*2-1):
    if len(node)<=i:
      node.append(deepcopy(unit))
    else:
      node[i]=deepcopy(unit)
  node.append(func)
  node.append(unit)

def upd(node,x,a):
  y=(len(node)>>1)+x-1
  node[y]=a
  while y:
    y=(y-1)>>1
    node[y]=node[-2](node[(y<<1)+1],node[(y+1)<<1])

def query(node,l_q,r_q,k,l_m,r_m):
  if r_q<=l_m or r_m<=l_q:
    return node[-1]
  if l_q<=l_m and r_m<=r_q:
    return node[k]
  l_a=query(node,l_q,r_q,2*k+1,l_m,(l_m+r_m)//2)
  r_a=query(node,l_q,r_q,2*k+2,(l_m+r_m)//2,r_m)
  return node[-2](l_a,r_a)

N,Q=map(int,input().split())
node=[]
init(N,node,(1<<31)-1,lambda x,y:min(x,y))
c,x,y=0,0,0
for i in range(Q):
  c,x,y=map(int,input().split())
  if c:
    print(query(node,x,y+1,0,0,len(node)>>1))
  else:
    upd(node,x,y)

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
class segTree:
    def __init__(self,n,identity):
        if bin(n).count("1") == 1:
            self.depth = n.bit_length()
        else:
            self.depth = n.bit_length()+1
        self.leaves = 2**(self.depth-1)
        self.identity = identity
        self.tree = [self.identity] * (2**self.depth)
    
    def merge(self,x,y):
        return min(x,y)
    
    def update(self,i,x):
        i += self.leaves
        self.tree[i] = x
        target = i//2
        while target > 0:
            self.tree[target] = min(self.tree[target*2],self.tree[target*2+1])
            target //= 2
    
    def find(self,l,r):
        ret = self.identity
        l += self.leaves
        r += self.leaves
        while r > l:
            if l&1:
                ret = min(ret,self.tree[l])
                l += 1
            if r&1:
                r -= 1
                ret = min(ret,self.tree[r])
            l //= 2
            r //= 2
        return ret

seg = segTree(N,2**31-1)
for _ in range(Q):
    com,x,y = map(int,input().split())
    if com:
        print(seg.find(x,y+1))
    else:
        seg.update(x,y)