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:
# -*- coding: utf-8 -*-

import sys

sys.setrecursionlimit(10 ** 9)
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()))
INF=2**31-1

class SegTree:
    """
    以下のクエリを処理する
    1.update:  i番目の値をxに更新する
    2.get_val: 区間[l, r)の値を得る
    """
 
    def __init__(self, n, func, init):
        """
        :param n: 要素数
        :param func: 値の操作に使う関数(min, maxなど)
        :param init: 要素の初期値
        """
        n += 1
        self.n = n
        self.func = func
        self.init = init
        # nより大きい2の冪数
        n2 = 1
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [self.init] * (n2 << 1)
 
    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.n2
        self.tree[i] = x
        while i > 1:
            self.tree[i >> 1] = x = self.func(x, self.tree[i ^ 1])
            i >>= 1
 
    def get_val(self, a, b):
        """
        [a, b)の値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        return self._get_val(a, b, 1, 0, self.n2)
 
    def _get_val(self, a, b, k, l, r):
        """
        [a, b)の値を得る内部関数
        :param k: 現在調べている区間のtree内index
        :param l, r: kが表す区間の左右端index [l, r)
        :return: kが表す区間と[a, b)の共通区間内での最小値。共通区間を持たない場合は初期値
        """
        # 範囲外なら初期値
        if r <= a or b <= l:
            return self.init
        # [a,b)が完全に[l,r)を包含するならtree[k]の値を採用
        if a <= l and r <= b:
            return self.tree[k]
        # 一部だけ範囲内なら2つに分けて再帰的に調査
        m = (l + r) // 2
        return self.func(
            self._get_val(a, b, k << 1, l, m),
            self._get_val(a, b, (k << 1) + 1, m, r)
        )

N,Q=MAP()
st=SegTree(N, min, INF)
for _ in range(Q):
    com,x,y=MAP()
    if com==0:
        st.update(x, y)
    else:
        print(st.get_val(x, y+1))

Submission status: Accepted

Solution code:
class SegmentTree:
    def __init__(self, n, cal, unit): #example (12, min, 2**31-1)
        for k in range(40):
            if 2**k > N:
                break
        self.powers = pow(2,k)
        self.segTree = [unit]*(2*self.powers)
        self.cal = cal
        self.unit = unit
    
    def update(self, i, x):#i番目(0-indexed)にx代入, segTree = [0,*,*,...], 1-indexed, N < k
        i += self.powers
        self.segTree[i] = x
        while i > 1:
            i //= 2
            self.segTree[i] = self.cal(self.segTree[i*2],self.segTree[i*2+1])

    def getCal(self, i, j, k=1, l=0, r=-1): #get self.cal of [i,j)!!!!!
        if r < 0: #initization, we want to r = self.powers as an initial value.
            r = self.powers
        if j <= l or r <= i:
            return self.unit
        if i <= l and r <= j:
            return self.segTree[k]
        return self.cal( self.getCal(i ,j, k*2, l, (l+r+1)//2) ,self.getCal(i ,j, k*2+1, (l+r+1)//2, r))

N, Q = map( int, input().split())
segmentTree = SegmentTree(N, min, 2**31-1)
for _ in range(Q):
    com, x, y = map( int, input().split())
    if com == 0:#0-indexed
        segmentTree.update(x,y)
    else:#""[x,y]"
        print(segmentTree.getCal(x,y+1)) #remark. we need "+1".

Submission status: Accepted

Solution code:
class SegTree:
    
    def __init__(self, A, intv, initialize = True):
        self.N = len(A)
        self.N0 = 2**(self.N-1).bit_length()
        self.intv = intv
        if initialize:
            self.data = [intv]*(self.N0-1) + A + [intv]*(self.N0 - self.N + 1)
            for i in range(self.N0-2, -1, -1):
                self.data[i] = min(self.data[2*i+1], self.data[2*i+2]) 
        else:
            self.data = [intv]*(2*self.N0)
    
    def segf(self, a, b):
        return min(a, b)
    
    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, R = l+self.N0, r+self.N0
        s = self.intv
        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

import sys
N, Q = map(int, input().split())
T = SegTree([0]*N, 2**31-1, False)
for _ in range(Q):
    qt, x, y = map(int, sys.stdin.readline().split())
    if qt:
        print(T.query(x, y+1))
    else:
        T.update(x, y)

Submission status: Accepted

Solution code:
class SegmentTree:
  def __init__(self, l, func=min, init_val=float("inf")):
    self.func = func
    self.init_val = init_val
    n = 1
    while n < len(l):
      n *= 2
    self.nodes = [init_val for _ in range(2*n-1)]
    self.n = n
    for i in range(len(l)):
      self.nodes[i+n-1] = l[i]
    for i in range(n-2, -1, -1):
      self.nodes[i] = self.func(self.nodes[2*i+1], self.nodes[2*i+2])

  def update(self, x, val):
    x += self.n - 1
    self.nodes[x] = val
    while x > 0:
      x = (x - 1) // 2
      self.nodes[x] = self.func(self.nodes[2*x+1], self.nodes[2*x+2])

  def get(self, a, b):
    return self._get(a, b)

  def _get(self, a, b, k=0, l=0, r=-1):
    if (r < 0):
      r = self.n
    if (r <= a or b <= l):
      return self.init_val
    if (a <= l and r <= b):
      return self.nodes[k]
    return self.func(
      self._get(a, b, 2*k+1, l, (l + r) // 2),
      self._get(a, b, 2*k+2, (l + r) // 2, r)
    )

n, q = map(int, input().split())
alist = [pow(2, 31)-1 for _ in range(n)]
minsegt = SegmentTree(alist, init_val=pow(2, 31)-1)
for _ in range(q):
  c, x, y = map(int, input().split())
  if c == 0:
    minsegt.update(x, y)
  else:
    print(minsegt.get(x, y+1))

Submission status: Accepted

Solution code:
class RMQ:
  def __init__(self,n,e):
    self.n = 2**((n-1).bit_length())
    self.e = e
    self.d = [e]*(self.n<<1)
  
  def update(self,k,x):
    k += self.n-1
    self.d[k] = x
    while k > 0:
      k = (k-1)>>1
      self.d[k] = min(self.d[(k<<1)+1],self.d[(k<<1)+2])
    
  def query(self,l,r):
    L = l+self.n; R = r+self.n
    s = self.e
    while L < R:
      if R & 1:
        R -= 1
        s = min(s,self.d[R-1])
      if L & 1:
        s = min(s,self.d[L-1])
        L += 1
      L >>= 1; R >>= 1
    return s

[n,q] = list(map(int,input().split()))
rmq = RMQ(n,(1<<31)-1)
for i in range(q):
	[com,x,y] = list(map(int,input().split()))
	if com == 0:
		rmq.update(x,y)
	else:
		print(rmq.query(x,y+1))

Submission status: Accepted

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

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

    # 区間[l, r)の最小値
    def query(self, l, r):
        L = l + self.N0; R = r + self.N0
        s = 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

# N: 処理する区間の長さ
N, Q = map(int, input().split())
segtree = SegmentTree(N)
segtree.data
#初期化:
"""
for i in range(1, N+1):
    update(i, a[i])
"""
for i in range(Q):
    q, l, r = map(int, input().split())
    if q == 1:
        print(segtree.query(l, r+1))
    else:
        segtree.update(l, r)

Submission status: Accepted

Solution code:
INF = 2**31-1
n, q = map(int, input().split())
size = 2**((n-1).bit_length())
seg_tree = [INF]*(size*2)

import sys
input = sys.stdin.readline

def update(i, x):
    ind = size+i
    seg_tree[ind] = x
    while ind>1:
        ind >>= 1
        left = seg_tree[ind*2]
        right = seg_tree[ind*2+1]
        seg_tree[ind] = min(left, right)
    
def find(s,t):
    L = s+size
    R = t+size
    ret = INF
    while L<R:
        if R&1:
            R-=1
            ret = min(ret, seg_tree[R])
        if L&1:
            ret = min(ret, seg_tree[L])
            L+=1
        L=L>>1
        R=R>>1
    return ret

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

Submission status: Accepted

Solution code:
# 一点更新区間min(1-indexed, 非再帰)
class RangeMinimumQuery:
    def __init__(self, n, inf=2 ** 31 - 1):
        self.n = 1 << (n - 1).bit_length()
        self.INF = inf
        self.segtree = [self.INF] * (2 * self.n)

    # i番目の値(0-indexed)をxに変更
    def update(self, i, x):
        i += self.n
        self.segtree[i] = x
        while i > 0:
            i //= 2
            self.segtree[i] = min(self.segtree[2 * i], self.segtree[2 * i + 1])

    # [l, r)のmin
    def query(self, l, r):
        L, R = l + self.n, r + self.n
        s = self.INF
        while L < R:
            if L & 1:
                s = min(s, self.segtree[L])
                L += 1

            if R & 1:
                s = min(s, self.segtree[R - 1])
                R -= 1

            L >>= 1
            R >>= 1

        return s


N, Q = map(int, input().split())
RMQ = RangeMinimumQuery(N)
for q in range(Q):
    cmd, x, y = map(int, input().split())
    if cmd == 0:
        RMQ.update(x, y)

    if cmd == 1:
        print(RMQ.query(x, y + 1))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000)

INF = 2147483647


# initiate the RMQ tree
def initRMQ(n, D):
    n_ = 1
    # search the power of n
    while n_ < n:
        n_ *= 2
    # set a big number to all leaves
    for i in range(2*n_ - 1):
        D.append(INF)

    return n_


def update(k, a):
    k += n_ - 1  # convert array index to tree index
    D[k] = a
    while k != 0:
        k = int((k - 1) / 2)
        D[k] = min(D[k*2 + 1], D[k*2 + 2])


def findMin(qlow, qhigh):
    return query(qlow, qhigh + 1, 0, 0, n_)


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

    if qlow <= l and r <= qhigh:
        return D[k]

    mid = (l + r) // 2
    vl = query(qlow, qhigh, k*2 + 1, l, mid)
    vr = query(qlow, qhigh, k*2 + 2, mid, 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:
answer=[]
D=[]
def initRMQ(nn):
    global n
    n = 1
    while n < nn:
        n*=2
    for i in range(2*n-1):
        D.append(2147483647)

def update(k,a):
    k += n-1
    D[k] = a
    while k>0:
        k = (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):
    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, (l+r)//2)
    vr = query(a, b, (k*2)+2, (l+r)//2, r)
    return min(vl,vr)


inn,q = map(int,input().split())
initRMQ(inn)
while True:
    try:
        o,x,y = map(int,input().split())
    except:
        break
    else:
        if o == 0:
            update(x,y)
        else:
            answer.append(findMin(x,y))
            
for i in range(len(answer)):
    print(answer[i])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
INF = 2**31 -1
n, p = list(map(int, input().split()))

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

lis = [INF for i in range(2*temp-1)]

def updata(x, y):
  x += temp - 1
  lis[x] = y
  while x > 0:
    x = (x-1) // 2
    #print(x*2+2)
    lis[x] = min(lis[x*2+1], lis[x*2+2])

def findmin(x, y):
  return query(x, y+1, 0, 0, temp)

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

  if a <= l and r <= b:
    return lis[k]
  
  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 i in range(p):
  oper, x, y = list(map(int, input().split()))
  
  if oper == 0:
    updata(x, y)
  else: 
    print(findmin(x, y))

Submission status: Accepted

Solution code:
import math


def update(numlist,i):
  if i<0:
    return
  if i==0:
    numlist[i]=min(numlist[2*i+1],numlist[2*i+2])
    return
  numlist[i]=min(numlist[2*i+1],numlist[2*i+2])
  update(numlist,(i-1)//2)
  return

def find(numlist,x,y,k,minimum,maximum,MAX):
  if x>=maximum or y<minimum:
    return MAX
  if x<=minimum and maximum-1<=y:
    return numlist[k]
  else:
    L=find(numlist,x,y,k*2+1,minimum,(maximum+minimum)//2,MAX)
    R=find(numlist,x,y,k*2+2,(maximum+minimum)//2,maximum,MAX)
    return (min(L,R))
    
  

n,q=map(int,input().split())
L2n=math.ceil(math.log2(n))
zero=2**(L2n)-1
MAX=2**31-1
numlist=[MAX]*(2**(L2n+1)-1)
resultlist=[]

for _ in range(0,q):
  com,x,y=map(int,input().split())
  if com:
    resultlist.append(find(numlist,x,y,0,0,2**L2n,MAX))
  else:
    numlist[zero+x]=y
    update(numlist,(zero+x-1)//2)

for x in resultlist:
  print (x)

Submission status: Accepted

Solution code:
# coding:utf-8

import sys

INF = 2 ** 31 - 1
MOD = 10 ** 9 + 7

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


class SegmentTree:
    __slots__ = ['node', 'size']

    def __init__(self, n_):
        self.size = 2 ** n_.bit_length()
        self.node = [INF] * (2 * self.size)

    # k番目の値をaに変更
    def update(self, k, a):
        k += self.size - 1
        self.node[k] = a
        # 登りながら更新
        while k >= 0:
            k = (k - 1) // 2
            self.node[k] = min(self.node[k * 2 + 1], self.node[k * 2 + 2])

    # [a, b)の最小値を求める
    def query(self, a, b):
        l, r = a + self.size, b + self.size
        res = INF
        while l < r:
            if r & 1:
                r -= 1
                res = min(res, self.node[r - 1])

            if l & 1:
                res = min(res, self.node[l - 1])
                l += 1

            l >>= 1
            r >>= 1
        return res


n, q = LI()
sgt = SegmentTree(n)

for _ in range(q):
    c, x, y = LI()

    if c == 0:
        sgt.update(x, y)
    else:
        print(sgt.query(x, y + 1))

Submission status: Accepted

Solution code:
oldn,q = map(int , input().split())
INF = 2147483647
n = 1

while(n < oldn) :
    n *= 2
dat = []
for i in range(2*n-1):
    dat.append(INF)

def updata(k , a): #k番目(0-indexed)をaに変更
    k += (n-1)
    dat[k] = a
    while (k > 0):
        k = (k-1) // 2 #親の番号
        dat[k] = min(dat[2*k+1],dat[2*k+2])

#[a,b)のminを求める
#k:節点の番号[l,r)その節点の対応する区間
def query(a,b,k,l,r):
    if(r <= a) or (b <= l) : return INF
    if(a <=l) and (r <= b) : return dat[k]
    v1 = query(a,b,2*k+1,l,(l+r)/2)
    v2 = query(a,b,2*k+2,(l+r)/2,r)
    return min(v1,v2)

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

Submission status: Accepted

Solution code:
# coding: utf-8
class seg_tree:
    def __init__(self,n,minimum=True):
        self.inf = 2**31-1
        self.size = 2**(len(bin(n-1))-2)*2-1
        self.minimum = minimum
        if self.minimum:
            self.tree = [self.inf for i in range(self.size)]
        else:
            self.tree = [-1 for i in range(self.size)]
     
    def data(self):
        return self.tree[self.size//2:]
 
    def update(self,i,x):
        i=self.size//2+i
        self.tree[i]=x
        if self.minimum:
            while 1:
                i=(i-1)//2
                self.tree[i]=min(self.tree[i*2+1],self.tree[i*2+2])
                if i<=0:
                    break
        else:
            while 1:
                i=(i-1)//2
                self.tree[i]=max(self.tree[i*2+1],self.tree[i*2+2])
                if i<=0:
                    break
 
    def _mincheck(self,s,t,l,r,_p=0):
        if s<=l and r<=t:
            return self.tree[_p]
        elif r<s or t<l:
            return self.inf
        else:
            return min(self._mincheck(s,t,l,l+(r-l)//2,_p*2+1),self._mincheck(s,t,l+(r-l)//2+1,r,_p*2+2))
     
    def _maxcheck(self,s,t,l,r,_p=0):
        if s<=l and r<=t:
            return self.tree[_p]
        elif r<s or t<l:
            return -1
        else:
            return max(self._maxcheck(s,t,l,l+(r-l)//2,_p*2+1),self._maxcheck(s,t,l+(r-l)//2+1,r,_p*2+2))
 
    def find(self,s,t):
        if self.minimum:
            return self._mincheck(s,t,0,self.size//2)
        else:
            return self._maxcheck(s,t,0,self.size//2)
 
n,q=map(int,input().split())
st=seg_tree(n)
ans=[]
for i in range(q):
    c,x,y=map(int,input().split())
    if c:
        ans.append(st.find(x,y))
    else:
        st.update(x,y)
print(*ans,sep='\n')

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
Q=[list(map(int,input().split())) for i in range(q)]

#Segment tree（区間の最小値を求めるバージョン）
for i in range(30):#要素数以上の2のベキを見つける
    if n<=1<<i:
        seg_el=1<<i#Segment treeの台の要素数
        break

SEG=[(1<<31)-1]*(2*seg_el-1)#Segment treeを一次元リストとして作る

def update(n,x,seg_el):#A[n]=xに更新（反映）
    i=n+seg_el-1
    SEG[i]=x
    i=(i-1)//2
    
    while i>=0:
        SEG[i]=min(SEG[i*2+1],SEG[i*2+2])
        i=(i-1)//2
        

def getvalues(a,b,k,l,r):#区間[a,b)での,SEG[k],つまり区間[l,r)に関する最小値を調べる
    if r<=a or b<=l:#区間[a,b)が対象区間の外にあれば,infを出力
        return (1<<31)-1
    if a<=l and r<=b:#区間[a,b)が対象区間の中にあればSEG[k]を出力
        return SEG[k]
    vl=getvalues(a,b,k*2+1,l,(l+r)//2)#それ以外のときは,SEG[k*2+1]とSEG[k*2+2]で場合分け（木の子ノード二つを見る）
    vr=getvalues(a,b,k*2+2,(l+r)//2,r)
    return min(vl,vr)

for com,x,y in Q:
    if com==0:
        update(x,y,seg_el)
    else:
        print(getvalues(x,y+1,0,0,seg_el))

Submission status: Accepted

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


class SegmentTree(object):
    INT_MAX = (1 << 31) - 1

    def __init__(self, n_):
        n = 1
        while n < n_:
            n *= 2
        self._tree = [self.INT_MAX] * (n * 2 - 1)
        self.num_elems = n


    def update(self, k, a):
        # accessing the index corresponding to the leaf
        k += self.num_elems - 1
        self._tree[k] = a

        # climbing up
        while k > 0:
            k = (k - 1) // 2
            self._tree[k] = min(self._tree[k * 2 + 1], self._tree[k * 2 + 2])
        # print(self._tree)

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

n, q = [int(elem) for elem in fin().split()]
segtree = SegmentTree(n)

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

queries = tuple(tuple(int(elem) for elem in fin().split()) for _ in range(q))

for c, x, y in queries:
    if c == 0:
        segtree.update(x, y)
    else:
        print(segtree.query(x, y + 1, 0, 0, ceil_exp_2))

Submission status: Accepted

Solution code:
class RMQ:
    INF = int((1<<31)-1)
    
    def __init__(self, n_:int):
        """param: n_(int) 葉の要素数"""
        # 葉の要素数を2のべき乗に
        n = 1
        while n<n_: n*=2
        self.n = n
        # 木全体では n + n/2 + ... = 2n-1
        self.dat = [self.INF]*(2*n-1)
    
    def update(self, k:int, a:int):
        k += self.n - 1
        self.dat[k] = a
        
        while k>0:
            k = (k-1)//2
            self.dat[k] = min(self.dat[2*k+1], self.dat[2*k+2])
            
    def dfs(self, a:int, b:int, k:int, l:int, r:int):
        """
        param a,b(int): 区間[a,b)
        param k(int):   節点の番号
        param l,r(int): 節点kが区間[l,r)に対応"""
        if r<=a or b<=l: return self.INF
        
        if a<=l and r<=b: 
            return self.dat[k]
        else:
            vl = self.dfs(a, b, 2*k+1, l, (l+r)//2)
            vr = self.dfs(a, b, 2*k+2, (l+r)//2, r)
            return min(vl, vr)
    
    def query(self, a:int, b:int):
        return self.dfs(a, b, 0, 0, self.n)
    
####
n,q = map(int, input().split())
rmq = RMQ(n)
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:
class RmQ_segment_tree:
    """0 indexed"""

    def __init__(self, init_num, n):
        # represent tree as array
        # parent of k : (k - 1) // 2
        # children of k : 2 * k + 1 and 2 * k + 2
        self.ex = 0
        while(2 ** self.ex < n):
            self.ex += 1
        self.bottom = 2 ** self.ex - 1
        self.tree = [init_num for _ in range(2 ** (self.ex + 1) - 1)]

    def __str__(self):
        tmp = "tree structure\n"
        tree = str(self.tree)
        return tmp + tree + "\n"

    def update(self, position, new):
        # chi : child
        # par : parent
        chi = self.bottom + position
        self.tree[chi] = new
        for _ in range(self.ex):
            par = (chi - 1) // 2
            ano_chi = [chi + 1, chi - 1][chi % 2 == 0]
            self.tree[par] = min(self.tree[chi], self.tree[ano_chi])
            chi = par
        return True

    def find(self, left, right):
        left = self.bottom + left
        right = self.bottom + right
        ret = min(self.tree[left], self.tree[right])
        while(left != right):
            if left % 2 == 0:
                ret = min(self.tree[left], ret)
                left += 1
                continue
            if right % 2 == 1:
                ret = min(self.tree[right], ret)
                right -= 1
                continue

            left = (left - 1) // 2
            right = (right - 1) // 2
        ret = min(ret, self.tree[left])
        return ret


init_num = 2 ** 31 - 1
n, q = map(int, input().split())
RmQ = RmQ_segment_tree(init_num, n)

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

    if com == 0:
        RmQ.update(x, y)
        # print(RmQ)
    else:
        print(RmQ.find(x, y))

Submission status: Accepted

Solution code:
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop

#BIG_NUM = 2000000000
BIG_NUM = 2147483647
HUGE_NUM = 9999999999999999
MOD = 1000000007
EPS = 0.000000001


global N
global table

def MIN(A,B):
    if A <= B:
        return A
    else:
        return B


def init(first_N):
    global N
    while N < first_N:
        N *= 2

def update(loc,value):
    global N
    loc += N-1

    table[loc] = value

    if N == 1:
        return

    parent = (loc-1)//2

    while True:
        table[parent] = MIN(table[2*parent+1],table[2*parent+2])

        if parent == 0:
            break

        parent = (parent-1)//2


def query(search_left,search_right,node_id,node_left,node_right):

    if search_right < node_left or search_left > node_right:
        return BIG_NUM
    if search_left <= node_left and search_right >= node_right:
        return table[node_id]
    else:
        left_min = query(search_left,search_right,2*node_id+1,node_left,(node_left+node_right)//2)
        right_min = query(search_left,search_right,2*node_id+2,(node_left+node_right)//2+1,node_right)
        return MIN(left_min,right_min)



first_N,num_query = map(int,input().split())
N = 1
init(first_N)

table = [None]*(2*N-1)

for i in range(2*N-1):
    table[i] = BIG_NUM


for loop in range(num_query):
    command,left,right = map(int,input().split())

    if command == 0:

        update(left,right)

    else:
        print("%d"%(query(left,right,0,0,N-1)))

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

class SegTree():
    def __init__(self, node:int):
        self.n = node
        self.bit = len(bin(self.n-1)) - 2
        self.bottom = 2**self.bit
        
        if self.n == 1:
            self.bottom = 1
            
        self.segtree = [0]*(2*self.bottom-1)
        
        
    def fill(self, n:int):
        self.segtree = [n]*(2*self.bottom-1)
        
    def update(self, idx:int, x:int):
        idx += (self.bottom-1)
        self.segtree[idx] = x
        while idx > 0:
            k = (idx-1) >> 1
            self.segtree[k] = min(self.segtree[2*k+1],
                                  self.segtree[2*k+2])
            idx = k
            
            
    def find(self, left:int, right:int, idx:int, l:int, r:int):
        if left <= l and r <= right:
            return self.segtree[idx]

        elif l >= right or r <= left:
            return 10**10
        
        else:
            return min(self.find(left, right, 2*idx+1, l, (l+r)//2),
                       self.find(left, right, 2*idx+2, (l+r)//2, r))
        
            
n,q = li()
com = []
xy = []
for _ in range(q):
    c,x,y = li()
    com.append(c)
    xy.append((x, y))
    
segtree = SegTree(n)
segtree.fill(2**31-1)
    
for c, (x,y) in zip(com, xy):
    if c == 0:
        segtree.update(x, y)
        
    else:
        print(segtree.find(x, y+1, 0, 0, segtree.bottom))

Submission status: Output Limit Exceeded

Solution code:
n,q = map(int,raw_input().split())
A = [2**31-1]*n
B = [2**31-1]*317
for i in range(q):
    comi,xi,yi = map(int,raw_input().split())
    if comi and yi<316:
        print min(A[xi:yi+1])
    elif comi and yi >= 316:
        print min(A[xi:(xi/316 + 1)*316],B[xi/316+1:yi/316],A[(yi/316)*316:yi+1])
    else:
        A[xi]=yi
        B[xi/316] = min(B[xi/316],yi)

Submission status: Output Limit Exceeded

Solution code:
# Range Minimum Query
# sqrt(100000) = 316.227...

n,q = map(int,raw_input().split())
A = [2**31-1]*n
B = [2**31-1]*317
for i in range(q):
    comi,xi,yi = map(int,raw_input().split())
    if comi and yi<316:
        print min(A[xi:yi+1])
    elif comi and yi >= 316:
        print min(A[xi:(xi/316 + 1)*316],B[xi/316+1:yi/316],A[(yi/316)*316:yi+1])
    else:
        A[xi]=yi
        B[xi/316] = min(B[xi/316],yi)

Submission status: Output Limit Exceeded

Solution code:
n,q = map(int,raw_input().split())
A = [2**31-1 for i in range(n)]
B = [2**31-1]*317
for i in range(q):
    comi,xi,yi = map(int,raw_input().split())
    if comi and yi<316:
        print min(A[xi:yi+1])
    elif comi and yi >= 316:
        print min(A[xi:(xi/316 + 1)*316],B[xi/316+1:yi/316],A[(yi/316)*316:yi+1])
    else:
        A[xi]=yi
        B[xi/316] = min(B[xi/316],yi)

Submission status: Runtime Error

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

answer = []
# create segtree
size = 2

while size < n :
    size *= 2
    
size = size * 2 - 1
segtree = [2**31 - 1 for x in range(size)]

# update query
def update(i, x) :
    ind = size // 2 + i
    segtree[ind] = x
    
    while ind :
        ind = (ind - 1) // 2 # parent
        ch1 = segtree[ind * 2 + 1]
        ch2 = segtree[ind * 2 + 2]
        segtree[ind] = min(ch1, ch2)
    
def query(s, t, l, r, p) :
    if s > r or t < l :
        return 2**31 - 1
    if s <= l and t >= l :
        return segtree[p]
    else :
        vl = query(s, t, l, (l + r) // 2, p * 2 + 1)
        vr = query(s, t, (l + r) // 2, r, p * 2 + 2)
        
        return min(vl, vr)
    
for i in range(q) :
    com, x, y = map(int, input().split())
     
    if com == 0 :
        update(x, y)
    else :
        answer.append(query(x, y, 0, size // 2, 0))

# print(answer)

for a in answer :
    print(a)

Submission status: Runtime Error

Solution code:
#単体変更, 区間取得

class RMQ:
    #INF = int(1e18)
    INF = int((1<<31)-1)
    n = 0
    n_ = 0
    val = []
    def __init__(self, n_):
        n = 1
        while n < n_:
            n = n * 2
        self.n = n
        self.n_ = n_
        self.val = [self.INF] * (2 * n - 1)

    @staticmethod
    def merge(a, b):
        return min(a, b)
        
    def update(self,k, x):
        k = k + self.n - 1
        self.val[k] = x
        while k:
            k = k//2
            self.val[k] = self.merge(self.val[k*2+1], self.val[k*2+2])

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

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

    
n, q = list(map(int, input().split()))
rmq = RMQ(n)

while q:
    q = q - 1
    com, x, y = list(map(int, input().split()))
    if com == 0:
        rmq.update(x, y)
    else:
        print (rmq.query(x, y + 1))