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:
#!/usr/bin/env python3

import sys


INIT_VAL = 2 ** 31 - 1
REC_LIMIT = 100000


class SegmentTree4RMQ(object):

    def __init__(self, num_elems, init_val=sys.maxsize):
        self.num_elems = 1
        while self.num_elems < num_elems:
            self.num_elems *= 2
        self.data = [init_val for _ in range(self.num_elems * 2 - 1)]

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

    def rec(self, start, end, k, left, right):
        if right <= start or end <= left:
            return sys.maxsize
        elif start <= left and right <= end:
            return self.data[k]
        else:
            vl = self.rec(start, end, k * 2 + 1, left, (left + right) // 2)
            vr = self.rec(start, end, k * 2 + 2, (left + right) // 2, right)
            return min(vl, vr)

    def query(self, start, end):
        return self.rec(start, end, 0, 0, self.num_elems)


def main():
    sys.setrecursionlimit(REC_LIMIT)
    n, q = map(int, input().split())
    st = SegmentTree4RMQ(n, INIT_VAL)
    for _ in range(q):
        c, x, y = map(int, input().split())
        if c == 0:
            st.update(x, y)
        elif c == 1:
            print(st.query(x, y + 1))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

def update(index,n):
    targ[index] = n
    index = (index - 1) // 2
    while True:
        targ[index] = min(targ[index * 2 + 1],targ[index * 2 + 2])
        if index <= 0:
            break
        index = (index - 1) // 2

def find(i,e,node,inode,enode):
    #print(i,e,node,inode,enode)
    if inode > e or enode < i:
        return float("inf")
    elif (i <= inode and enode <= e) or inode==enode:
        return targ[node]

    else:
        irange = find(i,e,2*node + 1,inode,(inode+enode)// 2 )
        erange = find(i,e,2*node + 2,(inode+enode)//2 + 1,enode)
        return min(irange,erange)

num,query = (int(n) for n in input().split(' '))
initial = 2147483647
ln = 2 ** math.ceil(math.log2(num)) - 1
if num == 1:
    tail = 2
else:
    tail = 2 ** math.ceil(math.log2(num)) - num
global targ
targ = [initial] * (ln + num + tail)

for q in range(query):
    #print(targ)
    temp = [int(n) for n in input().split(' ') ]
    if temp[0] == 0:
        update(temp[1] + ln,temp[2])
    else:
        print(find(temp[1],temp[2],0,0,ln))

Submission status: Accepted

Solution code:
import math
import sys
def update(index,n):
    targ[index] = n
    index = (index - 1) // 2
    while True:
        targ[index] = min(targ[index * 2 + 1],targ[index * 2 + 2])
        if index <= 0:
            break
        index = (index - 1) // 2

def find(i,e,node,inode,enode):
    #print(i,e,node,inode,enode)
    if inode > e or enode < i:
        return float("inf")
    elif (i <= inode and enode <= e) or inode==enode:
        return targ[node]

    else:
        irange = find(i,e,2*node + 1,inode,(inode+enode)// 2 )
        erange = find(i,e,2*node + 2,(inode+enode)//2 + 1,enode)
        return min(irange,erange)

f = sys.stdin
num,query = (int(n) for n in f.readline().split(' '))
initial = 2147483647
ln = 2 ** math.ceil(math.log2(num)) - 1
if num == 1:
    tail = 2
else:
    tail = 2 ** math.ceil(math.log2(num)) - num
global targ
targ = [initial] * (ln + num + tail)

for q in range(query):
    #print(targ)
    temp = [int(n) for n in f.readline().split(' ') ]
    if temp[0] == 0:
        update(temp[1] + ln,temp[2])
    else:
        print(find(temp[1],temp[2],0,0,ln))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
3 5
0 0 1
0 1 2
0 2 3
1 0 2
1 1 2

output:
1
2
"""

import sys
from math import ceil, log2, isinf


class SegmentTree(object):
    __slots__ = ('dat', 'tree_range')

    def __init__(self):
        """
        Init a SegmentTree with update and find for RMQ.
        """
        self.tree_range = end
        self.dat = [float('inf')] * (2 * self.tree_range - 1)

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

    def find(self, a, b, k=0, l=0, r=0):
        if r <= a or b <= l:
            return float('inf')

        if a <= l and r <= b:
            return self.dat[k]
        else:
            vl = self.find(a, b, k * 2 + 1, l, (l + r) // 2)
            vr = self.find(a, b, k * 2 + 2, (l + r) // 2, r)
            return min(vl, vr)


def action(cmd_list):
    for _, each in enumerate(cmd_list):
        cmd, ele_1, ele_2 = map(int, each)
        if cmd == 0:
            case.update(ele_1, ele_2)
        elif cmd == 1:
            res = case.find(a=ele_1, b=ele_2 + 1, r=end)
            if isinf(res):
                print(INIT_MAX)
            else:
                print(res)

    return case


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    n_num, q_num = map(int, _input[0].split())
    q_list = map(lambda x: x.split(), _input[1:])

    end = pow(2, ceil(log2(n_num)))
    INIT_MAX = pow(2, 31) - 1

    case = SegmentTree()

    ans = action(q_list)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
3 5
0 0 1
0 1 2
0 2 3
1 0 2
1 1 2

output:
1
2
"""

import sys
from math import ceil, log2, isinf


class SegmentTree(object):
    __slots__ = ('dat', 'tree_range')

    def __init__(self):
        """
        Init a SegmentTree with update and find for RMQ.
        """
        self.tree_range = end
        self.dat = [float('inf')] * (2 * self.tree_range - 1)

    # let A[k]=a
    def update(self, k, a):
        k += self.tree_range - 1
        self.dat[k] = a
        while k > 0:
            k = (k - 1) // 2
            self.dat[k] = min(self.dat[k * 2 + 1], self.dat[k * 2 + 2])

    # get min(A[s] A[s+1] ... A[t])
    def find(self, s, t, k=0, l=0, r=0):
        if r <= s or t <= l:
            return float('inf')

        if s <= l and r <= t:
            return self.dat[k]
        else:
            vl = self.find(s, t, k * 2 + 1, l, (l + r) // 2)
            vr = self.find(s, t, k * 2 + 2, (l + r) // 2, r)
            return min(vl, vr)


def action(cmd_list):
    for query in cmd_list:
        cmd, ele_1, ele_2 = map(int, query)
        if cmd == 0:
            case.update(ele_1, ele_2)
        elif cmd == 1:
            res = case.find(s=ele_1, t=ele_2 + 1, r=end)
            if isinf(res):
                print(INIT_MAX)
            else:
                print(res)

    return case


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    n_num, q_num = map(int, _input[0].split())
    q_list = map(lambda x: x.split(), _input[1:])

    end = pow(2, ceil(log2(n_num)))
    INIT_MAX = pow(2, 31) - 1

    case = SegmentTree()

    ans = action(q_list)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
3 5
0 0 1
0 1 2
0 2 3
1 0 2
1 1 2

output:
1
2
"""

import sys
from math import ceil, log2, isinf


class SegmentTree(object):
    __slots__ = ('dat', 'tree_range')

    def __init__(self):
        """
        Init a SegmentTree with update and find for RMQ.
        """
        self.tree_range = end
        self.dat = [float('inf')] * (2 * self.tree_range - 1)

    # let A[k]=a
    def update(self, k, a):
        k += self.tree_range - 1
        self.dat[k] = a
        while k > 0:
            k = (k - 1) // 2
            self.dat[k] = min(self.dat[k * 2 + 1], self.dat[k * 2 + 2])

    # get min(A[s] A[s+1] ... A[t])
    def find(self, s, t, k=0, l=0, r=0):
        if r <= s or t <= l:
            return float('inf')

        if s <= l <= r <= t:
            return self.dat[k]
        else:
            vl = self.find(s, t, k * 2 + 1, l, (l + r) // 2)
            vr = self.find(s, t, k * 2 + 2, (l + r) // 2, r)
            return min(vl, vr)


def action(cmd_list):
    for query in cmd_list:
        cmd, ele_1, ele_2 = map(int, query)
        if cmd == 0:
            case.update(ele_1, ele_2)
        elif cmd == 1:
            assert ele_1 <= ele_2
            res = case.find(s=ele_1, t=ele_2 + 1, r=end)
            if isinf(res):
                print(INIT_MAX)
            else:
                print(res)

    return case


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    n_num, q_num = map(int, _input[0].split())
    q_list = map(lambda x: x.split(), _input[1:])

    end = pow(2, ceil(log2(n_num)))
    INIT_MAX = pow(2, 31) - 1

    case = SegmentTree()

    ans = action(q_list)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
3 5
0 0 1
0 1 2
0 2 3
1 0 2
1 1 2

output:
1
2
"""

import sys
from math import ceil, log2, isinf


class SegmentTree(object):
    __slots__ = ('dat', 'tree_range')

    def __init__(self):
        """
        Init a SegmentTree with update and find for RMQ.
        """
        self.tree_range = end
        self.dat = [float('inf')] * (2 * self.tree_range - 1)

    # let A[k]=a
    def update(self, k, a):
        k += self.tree_range - 1
        self.dat[k] = a
        while k > 0:
            k = (k - 1) // 2
            self.dat[k] = min(self.dat[k * 2 + 1], self.dat[k * 2 + 2])

    # get min(A[s] A[s+1] ... A[t])
    def find(self, s, t, k=0, l=0, r=float('inf')):
        if r <= s or t <= l:
            return float('inf')

        if s <= l <= r <= t:
            return self.dat[k]
        else:
            vl = self.find(s, t, k * 2 + 1, l, (l + r) // 2)
            vr = self.find(s, t, k * 2 + 2, (l + r) // 2, r)
            return min(vl, vr)


def action(cmd_list):
    for query in cmd_list:
        cmd, ele_1, ele_2 = map(int, query)
        if cmd == 0:
            case.update(ele_1, ele_2)
        elif cmd == 1:
            assert ele_1 <= ele_2
            res = case.find(s=ele_1, t=ele_2 + 1, r=end)
            if isinf(res):
                print(INIT_MAX)
            else:
                print(res)

    return case


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    n_num, q_num = map(int, _input[0].split())
    q_list = map(lambda x: x.split(), _input[1:])

    end = pow(2, ceil(log2(n_num)))
    INIT_MAX = pow(2, 31) - 1

    case = SegmentTree()

    ans = action(q_list)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
3 5
0 0 1
0 1 2
0 2 3
1 0 2
1 1 2

output:
1
2
"""

import sys
from math import ceil, log2, isinf


class SegmentTree(object):
    __slots__ = ('dat', 'tree_range')

    def __init__(self):
        """
        Init a SegmentTree with update and find for RMQ.
        """
        self.tree_range = end
        self.dat = [float('inf')] * (2 * self.tree_range - 1)

    # let A[k]=a
    def update(self, k, a):
        k += self.tree_range - 1
        self.dat[k] = a
        while k > 0:
            k = (k - 1) // 2
            self.dat[k] = min(self.dat[k * 2 + 1], self.dat[k * 2 + 2])

    # get min(A[s] A[s+1] ... A[t])
    def find(self, s, t, k=0, l=0, r=float('inf')):
        if r <= s or t <= l:
            return float('inf')

        elif s <= l <= r <= t:
            return self.dat[k]
        else:
            vl = self.find(s, t, k * 2 + 1, l, (l + r) // 2)
            vr = self.find(s, t, k * 2 + 2, (l + r) // 2, r)
            return min(vl, vr)


def action(cmd_list):
    for query in cmd_list:
        cmd, ele_1, ele_2 = map(int, query)
        if cmd == 0:
            case.update(ele_1, ele_2)
        elif cmd == 1:
            assert ele_1 <= ele_2
            res = case.find(s=ele_1, t=ele_2 + 1, r=end)
            if isinf(res):
                print(INIT_MAX)
            else:
                print(res)

    return case


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    n_num, q_num = map(int, _input[0].split())
    q_list = map(lambda x: x.split(), _input[1:])

    end = pow(2, ceil(log2(n_num)))
    INIT_MAX = pow(2, 31) - 1

    case = SegmentTree()

    ans = action(q_list)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
3 5
0 0 1
0 1 2
0 2 3
1 0 2
1 1 2

output:
1
2
"""

import sys
from math import ceil, log2, isinf


class SegmentTree(object):
    __slots__ = ('dat', 'tree_range')

    def __init__(self):
        """
        Init a SegmentTree with update and find for RMQ.
        """
        self.tree_range = end
        self.dat = [float('inf')] * (2 * self.tree_range - 1)

    # let A[k]=a
    def update(self, k, a):
        k += self.tree_range - 1
        self.dat[k] = a
        while k > 0:
            k = (k - 1) // 2
            self.dat[k] = min(self.dat[k * 2 + 1], self.dat[k * 2 + 2])

    # get min(A[s] A[s+1] ... A[t])
    def find(self, s, t, k=0, l=0, r=float('inf')):
        if r <= s or t <= l:
            return float('inf')
        elif s <= l <= r <= t:
            return self.dat[k]
        else:
            vl = self.find(s, t, k * 2 + 1, l, (l + r) // 2)
            vr = self.find(s, t, k * 2 + 2, (l + r) // 2, r)
            return min(vl, vr)


def action(cmd_list):
    for query in cmd_list:
        cmd, ele_1, ele_2 = map(int, query)
        if cmd == 0:
            case.update(ele_1, ele_2)
        elif cmd == 1:
            assert ele_1 <= ele_2
            res = case.find(s=ele_1, t=ele_2 + 1, r=end)
            if isinf(res):
                print(INIT_MAX)
            else:
                print(res)

    return case


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    n_num, q_num = map(int, _input[0].split())
    q_list = map(lambda x: x.split(), _input[1:])

    end = pow(2, ceil(log2(n_num)))
    INIT_MAX = pow(2, 31) - 1

    case = SegmentTree()

    ans = action(q_list)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
3 5
0 0 1
0 1 2
0 2 3
1 0 2
1 1 2

output:
1
2
"""

import sys
from math import ceil, log2, isinf


class SegmentTree(object):
    __slots__ = ('dat', 'tree_range')

    def __init__(self):
        """
        Init a SegmentTree with update and find for RMQ.
        """
        self.tree_range = end
        self.dat = [float('inf')] * (2 * self.tree_range - 1)

    # let A[k]=a
    def update(self, k, a):
        k += self.tree_range - 1
        self.dat[k] = a
        while k > 0:
            k = (k - 1) // 2
            self.dat[k] = min(self.dat[k * 2 + 1], self.dat[k * 2 + 2])

    # get min(A[s] A[s+1] ... A[t])
    def find(self, s, t, k=0, l=0, r=float('inf')):
        if r <= s or t <= l:
            return float('inf')
        if s <= l <= r <= t:
            return self.dat[k]
        else:
            vl = self.find(s, t, k * 2 + 1, l, (l + r) // 2)
            vr = self.find(s, t, k * 2 + 2, (l + r) // 2, r)
            return min(vl, vr)


def action(cmd_list):
    for query in cmd_list:
        cmd, ele_1, ele_2 = map(int, query)
        if cmd == 0:
            case.update(ele_1, ele_2)
        elif cmd == 1:
            assert ele_1 <= ele_2
            res = case.find(s=ele_1, t=ele_2 + 1, r=end)
            if isinf(res):
                print(INIT_MAX)
            else:
                print(res)

    return case


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    n_num, q_num = map(int, _input[0].split())
    q_list = map(lambda x: x.split(), _input[1:])

    end = pow(2, ceil(log2(n_num)))
    INIT_MAX = pow(2, 31) - 1

    case = SegmentTree()

    ans = action(q_list)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
3 5
0 0 1
0 1 2
0 2 3
1 0 2
1 1 2

output:
1
2
"""

import sys
import math


class SegmentTree(object):
    __slots__ = ('dat', 'tree_range')

    def __init__(self, n):
        """
        Init a SegmentTree with update and find for range minimum queries.
        """
        self.tree_range = pow(2, math.ceil(math.log2(n)))
        self.dat = [float('inf')] * (2 * self.tree_range - 1)

    # let A[k]=a
    def update(self, k, a):
        k += self.tree_range - 1
        self.dat[k] = a
        while k > 0:
            k = (k - 1) // 2
            self.dat[k] = min(self.dat[k * 2 + 1], self.dat[k * 2 + 2])

    # get min(A[s] A[s+1] ... A[t])
    def find(self, s, t, k=0, l=0, r=float('inf')):
        if r <= s or t <= l:
            return float('inf')
        elif s <= l <= r <= t:
            return self.dat[k]
        else:
            vl = self.find(s, t, k * 2 + 1, l, (l + r) // 2)
            vr = self.find(s, t, k * 2 + 2, (l + r) // 2, r)
            return min(vl, vr)


def action(cmd_list):
    case = SegmentTree(n_num)
    end = pow(2, math.ceil(math.log2(n_num)))
    init_max = pow(2, 31) - 1

    for query in cmd_list:
        cmd, ele_1, ele_2 = map(int, query)
        if cmd == 0:
            case.update(ele_1, ele_2)
        elif cmd == 1:
            assert ele_1 <= ele_2
            res = case.find(s=ele_1, t=ele_2 + 1, r=end)
            if math.isinf(res):
                print(init_max)
            else:
                print(res)

    return case


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    n_num, q_num = map(int, _input[0].split())
    q_list = map(lambda x: x.split(), _input[1:])

    ans = action(q_list)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
3 5
0 0 1
0 1 2
0 2 3
1 0 2
1 1 2

output:
1
2
"""

import math
import sys


class SegmentTree(object):
    __slots__ = ('dat', 'tree_range')

    def __init__(self, n):
        """
        Init a SegmentTree with update and find for range minimum queries.
        """
        self.tree_range = pow(2, math.ceil(math.log2(n)))
        self.dat = [float('inf')] * (2 * self.tree_range - 1)

    # let A[k]=a
    def update(self, k, a):
        k += self.tree_range - 1
        self.dat[k] = a
        while k > 0:
            k = (k - 1) // 2
            self.dat[k] = min(self.dat[k * 2 + 1], self.dat[k * 2 + 2])

    # get min(A[s] A[s+1] ... A[t])
    def find(self, s, t, k=0, left=0, right=float('inf')):
        if right <= s or t <= left:
            return float('inf')
        elif s <= left <= right <= t:
            return self.dat[k]
        else:
            vl = self.find(s, t, k * 2 + 1, left, (left + right) // 2)
            vr = self.find(s, t, k * 2 + 2, (left + right) // 2, right)
            return min(vl, vr)


def action(cmd_list, n_num):
    case = SegmentTree(n_num)
    end = pow(2, math.ceil(math.log2(n_num)))
    init_max = pow(2, 31) - 1

    for query in cmd_list:
        cmd, ele_1, ele_2 = map(int, query)
        if cmd == 0:
            case.update(ele_1, ele_2)
        elif cmd == 1:
            assert ele_1 <= ele_2
            res = case.find(s=ele_1, t=ele_2 + 1, right=end)
            if math.isinf(res):
                print(init_max)
            else:
                print(res)

    return None


def solve():
    _input = sys.stdin.readlines()
    n_num, q_num = map(int, _input[0].split())
    q_list = map(lambda x: x.split(), _input[1:])

    action(q_list, n_num)
    return None


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
3 5
0 0 1
0 1 2
0 2 3
1 0 2
1 1 2

output:
1
2
"""

import math
import sys


class SegmentTree(object):
    __slots__ = ('dat', 'tree_range')

    def __init__(self, n):
        """
        Init a SegmentTree with update and find for range minimum queries.
        """
        self.tree_range = pow(2, math.ceil(math.log2(n)))
        self.dat = [float('inf')] * (2 * self.tree_range - 1)

    # let A[k]=a
    def update(self, k, a):
        k += self.tree_range - 1
        self.dat[k] = a
        while k > 0:
            k = (k - 1) // 2
            self.dat[k] = min(self.dat[k * 2 + 1], self.dat[k * 2 + 2])

    # get min(A[s] A[s+1] ... A[t])
    def find(self, s, t, k=0, left=0, right=float('inf')):
        if right <= s or t <= left:
            return float('inf')
        elif s <= left <= right <= t:
            return self.dat[k]
        else:
            vl = self.find(s, t, k * 2 + 1, left, (left + right) // 2)
            vr = self.find(s, t, k * 2 + 2, (left + right) // 2, right)
            return min(vl, vr)


def cmd_exec(cmd_list, n_num):
    case = SegmentTree(n_num)
    end = pow(2, math.ceil(math.log2(n_num)))
    init_max = pow(2, 31) - 1

    for query in cmd_list:
        cmd, ele_1, ele_2 = map(int, query)
        if cmd == 0:
            case.update(ele_1, ele_2)
        elif cmd == 1:
            assert ele_1 <= ele_2
            res = case.find(s=ele_1, t=ele_2 + 1, right=end)
            print(res) if not math.isinf(res) else print(init_max)

    return None


def solve():
    _input = sys.stdin.readlines()
    n_num, q_num = map(int, _input[0].split())
    q_list = map(lambda x: x.split(), _input[1:])

    cmd_exec(q_list, n_num)
    return None


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
3 5
0 0 1
0 1 2
0 2 3
1 0 2
1 1 2

output:
1
2
"""

import math
import sys

INIT_MAX = pow(2, 31) - 1


class SegmentTree(object):
    __slots__ = ('dat', 'tree_range')

    def __init__(self, n):
        """
        Init a SegmentTree with update and find for range minimum queries.
        """
        self.tree_range = pow(2, math.ceil(math.log2(n)))
        self.dat = [INIT_MAX] * (2 * self.tree_range - 1)

    # let A[k]=a
    def update(self, k, a):
        k += self.tree_range - 1
        self.dat[k] = a
        while k > 0:
            k = (k - 1) // 2
            self.dat[k] = min(self.dat[k * 2 + 1], self.dat[k * 2 + 2])

    # get min(A[s] A[s+1] ... A[t])
    def find(self, s, t, k=0, left=0, right=float('inf')):
        if right <= s or t <= left:
            return INIT_MAX
        elif s <= left <= right <= t:
            return self.dat[k]
        else:
            vl = self.find(s, t, k * 2 + 1, left, (left + right) // 2)
            vr = self.find(s, t, k * 2 + 2, (left + right) // 2, right)
            return min(vl, vr)


def cmd_exec(cmd_list, n_num):
    case = SegmentTree(n_num)
    end = pow(2, math.ceil(math.log2(n_num)))

    for query in cmd_list:
        cmd, ele_1, ele_2 = map(int, query)
        if cmd == 0:
            case.update(ele_1, ele_2)
        elif cmd == 1:
            assert ele_1 <= ele_2
            res = case.find(s=ele_1, t=ele_2 + 1, right=end)
            print(res)

    return None


def solve():
    _input = sys.stdin.readlines()
    n_num, q_num = map(int, _input[0].split())
    q_list = map(lambda x: x.split(), _input[1:])

    cmd_exec(q_list, n_num)
    return None


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

class Segtree():
    INT_MAX=2**31-1

    def __init__(self,size):
        self.size=1
        while self.size<size:
            self.size=self.size*2
        self.node=[self.INT_MAX]*(2*self.size-1)

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

    def get_min(self,queryL,queryR,k=0,nodeL=0,nodeR=-1):
        if nodeR==-1:nodeR=self.size
        if (nodeR<=queryL or queryR<=nodeL):return self.INT_MAX
        if (queryL<=nodeL and nodeR<=queryR):return self.node[k]
        else:
            nodeM=(nodeL+nodeR)/2
            vl=self.get_min(queryL,queryR,k*2+1,nodeL,nodeM)
            vr=self.get_min(queryL,queryR,2*k+2,nodeM,nodeR)
            return min(vl,vr)

n,q=map(int,raw_input().split())
st=Segtree(n)
for i in xrange(q):
    com,x,y=map(int,raw_input().split())
    if com==0:
        st.min_update(x,y)
    if com==1:
        print(st.get_min(x,y+1))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
3 5
0 0 1
0 1 2
0 2 3
1 0 2
1 1 2

output:
1
2
"""

import math
import sys

INIT_MAX = pow(2, 31) - 1


class SegmentTree(object):
    __slots__ = ('dat', 'ceil_n')

    def __init__(self, n):
        """
        Init a SegmentTree with update and find for range minimum queries.
        """
        self.ceil_n = pow(2, math.ceil(math.log2(n)))
        self.dat = [INIT_MAX] * (2 * self.ceil_n - 1)

    # let A[k]=a
    def update(self, k, a):
        k += self.ceil_n - 1
        self.dat[k] = a
        while k > 0:
            k = (k - 1) // 2
            self.dat[k] = min(self.dat[k * 2 + 1], self.dat[k * 2 + 2])

    # get min(A[s] A[s+1] ... A[t])
    def find(self, s, t, k=0, left=0, right=float('inf')):
        if right <= s or t <= left:
            return INIT_MAX
        elif s <= left <= right <= t:
            return self.dat[k]
        else:
            vl = self.find(s, t, k * 2 + 1, left, (left + right) // 2)
            vr = self.find(s, t, k * 2 + 2, (left + right) // 2, right)
            return min(vl, vr)


def cmd_exec(queries, n_num):
    case = SegmentTree(n_num)
    end = pow(2, math.ceil(math.log2(n_num)))

    for query in queries:
        cmd, ele_1, ele_2 = map(int, query)
        if cmd == 0:
            case.update(ele_1, ele_2)
        elif cmd == 1:
            # assert ele_1 <= ele_2
            res = case.find(s=ele_1, t=ele_2 + 1, right=end)
            print(res)

    return None


def solve():
    _input = sys.stdin.readlines()
    n_num, q_num = map(int, _input[0].split())
    queries = map(lambda x: x.split(), _input[1:])

    cmd_exec(queries, n_num)
    return None


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
3 5
0 0 1
0 1 2
0 2 3
1 0 2
1 1 2

output:
1
2
"""

import math
import sys

INIT_MAX = pow(2, 31) - 1


class SegmentTree(object):
    __slots__ = ('dat', 'ext_length')

    def __init__(self, orig_length):
        """
        Init a SegmentTree with update and find for range minimum queries.
        """
        self.ext_length = pow(2, math.ceil(math.log2(orig_length)))
        self.dat = [INIT_MAX] * (2 * self.ext_length - 1)

    # let A[k]=a
    def update(self, k, a):
        k += self.ext_length - 1
        self.dat[k] = a
        while k > 0:
            k = (k - 1) // 2
            self.dat[k] = min(self.dat[k * 2 + 1], self.dat[k * 2 + 2])

    # get min(A[s] A[s+1] ... A[t])
    def find(self, s, t, k=0, left=0, right=float('inf')):
        if right <= s or t <= left:
            return INIT_MAX
        elif s <= left <= right <= t:
            return self.dat[k]
        else:
            vl = self.find(s, t, k * 2 + 1, left, (left + right) // 2)
            vr = self.find(s, t, k * 2 + 2, (left + right) // 2, right)
            return min(vl, vr)


def cmd_exec(queries, n_num):
    case = SegmentTree(n_num)
    end = pow(2, math.ceil(math.log2(n_num)))

    for query in queries:
        cmd, ele_1, ele_2 = map(int, query)
        if cmd == 0:
            case.update(ele_1, ele_2)
        elif cmd == 1:
            # assert ele_1 <= ele_2
            res = case.find(s=ele_1, t=ele_2 + 1, right=end)
            print(res)

    return None


def solve():
    _input = sys.stdin.readlines()
    n_num, q_num = map(int, _input[0].split())
    queries = map(lambda x: x.split(), _input[1:])

    cmd_exec(queries, n_num)
    return None


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
3 5
0 0 1
0 1 2
0 2 3
1 0 2
1 1 2

output:
1
2
"""

import math
import sys

INIT_MAX = pow(2, 31) - 1


class RMQ(object):
    def __init__(self, in_data):
        """
        Init a SegmentTree with update and find for range minimum queries.
        """
        n_num, q_num = map(int, in_data[0].split())
        self.queries = map(lambda x: x.split(), in_data[1:])
        self.ext_heap_length = pow(2, math.ceil(math.log2(n_num)))
        self.dat = [INIT_MAX] * (2 * self.ext_heap_length - 1)

    # let A[k]=a
    def update(self, k, a):
        k += self.ext_heap_length - 1
        self.dat[k] = a
        while k > 0:
            k = (k - 1) // 2
            self.dat[k] = min(self.dat[k * 2 + 1], self.dat[k * 2 + 2])

    # get min(A[s] A[s+1] ... A[t])
    def find(self, s, t, k=0, left=0, right=float('inf')):
        if right <= s or t <= left:
            return INIT_MAX
        elif s <= left <= right <= t:
            return self.dat[k]
        else:
            vl = self.find(s, t, k * 2 + 1, left, (left + right) // 2)
            vr = self.find(s, t, k * 2 + 2, (left + right) // 2, right)
            return min(vl, vr)

    def cmd_exec(self):
        for query in self.queries:
            cmd, ele_1, ele_2 = map(int, query)
            if cmd == 0:
                self.update(ele_1, ele_2)
            elif cmd == 1:
                # assert ele_1 <= ele_2
                res = self.find(s=ele_1, t=ele_2 + 1, right=self.ext_heap_length)
                print(res)

        return None


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    case = RMQ(in_data=_input)
    case.cmd_exec()