Python range minimum query

gistfile1.py

import sys
import itertools

class RMQ:
    def __init__(self, n):
        self.sz = 1
        self.inf = (1 << 31) - 1
        while self.sz <= n: self.sz = self.sz << 1
        self.dat = [self.inf] * (2 * self.sz - 1)
    
    def update(self, idx, x):
        idx += self.sz - 1
        self.dat[idx] = x
        while idx > 0:
            idx = (idx - 1) >> 1
            self.dat[idx] = min(self.dat[idx * 2 + 1], self.dat[idx * 2 + 2])
            
    def query(self, a, b):
        return self.query_help(a, b, 0, 0, self.sz)
            
    def query_help(self, a, b, k, l, r):
        if r <= a or b <= l:
            return sys.maxint
        elif a <= l and r <= b:
            return self.dat[k]
        else:
            return min(self.query_help(a, b, 2 * k + 1, l, (l + r)>>1),
                        self.query_help(a, b, 2 * k + 2, (l + r) >> 1, r))
    
    
if __name__ == '__main__':
    line = sys.stdin.readline()
    n, q = line.split()
    n, q = int(n), int(q)
    rmq = RMQ(n)
    
    for i in range(q):
        line = sys.stdin.readline()
        op, a, b = line.split()
        op, a, b = int(op), int(a), int(b)
        if op == 0: 
            rmq.update(a, b)
        else: 
            sys.stdout.write(str(rmq.query(a, b + 1)) + '\n')
    

@Vimos

Hmm, seems the stack for python recursion is really shallow. And when all the number are the same, the recursive call solve_l_r become a list call for each element(since all element are the same, so the recursive call depth problem is not from the RMQ query), and it seems on codeforce, they don't allow python to do recursive call to go deep. But for C/C++, it is easy to do a recursive call for that depth.

https://codeforces.com/blog/entry/16905

IMO, the recursion limit(level of thousands) of python is really small compare to language like C/C++ on codeforces. But one way to handle this is to handle the call stack manually instead of letting the python to handle the call stack. Like the following accept program, so the allocation will happen on heap space instead of stack space. And since the RMQ structure is a complete binary tree, so the upper boundary of recursive call is bounded to O(logN).

import sys
import itertools
from random import randint
# sys.setrecursionlimit(10**6) 


class RMQ:
    def __init__(self, n):
        self.sz = 1
        self.inf = (1 << 31) - 1

        while self.sz <= n:
            self.sz = self.sz << 1
        self.dat = [[None, self.inf] for i in range(2 * self.sz - 1)]

    def update(self, idx, x):
        old_idx = idx
        idx += self.sz - 1
        self.dat[idx] = [old_idx, x]
        while idx > 0:
            idx = (idx - 1) >> 1
            self.dat[idx] = min(self.dat[idx * 2 + 1],
                                self.dat[idx * 2 + 2],
                                key=lambda x: x[1])

    def query(self, a, b):
        return self.query_help(a, b, 0, 0, self.sz)

    def query_help(self, a, b, k, l, r):
        if r <= a or b <= l:
            return (0, sys.maxsize)
        elif a <= l and r <= b:
            return self.dat[k]
        else:
            return min(self.query_help(a, b, 2 * k + 1, l, (l + r) >> 1),
                       self.query_help(a, b, 2 * k + 2, (l + r) >> 1, r),
                       key=lambda x: x[1])


def solve_l_r(left, right, height):
    if left > right:
        return 0

    min_right, min_height = rmq.query(left, right + 1)

    res = min(right - left + 1,
              min_height - height + \
                      solve_l_r(left, min_right - 1, min_height) + \
                      solve_l_r(min_right + 1, right, min_height))
    return res


def painting_fences():
    for i, j in enumerate(case_n):
        rmq.update(i, j)

    answer = {}
    stack  = [{"left": 0, "right": len(case_n) - 1, "height": 0, "recursive": True, "calc": False}]

    while stack:
        elem = stack.pop()
        left, right, isRecursive, height, isCalc = elem["left"], elem["right"], elem["recursive"], elem["height"], elem["calc"]
        if (left > right):
            answer[(left, right)] = 0
        else:
            min_right, min_height = rmq.query(left, right + 1)
            if isCalc:
                answer[(left, right)] = min(right - left + 1,
                                        min_height - height + answer[(left, min_right -1)] + answer[(min_right + 1, right)])
            elif isRecursive:
                stack.append({"left": left, "right": right, "height": height, "recursive": False, "calc": True})
                stack.append({"left": left, "right": min_right - 1, "height": min_height, "recursive": True, "calc": False})
                stack.append({"left": min_right + 1, "right": right, "height": min_height, "recursive": True, "calc": False})
    
            

    return answer[(0, len(case_n) - 1)]



if __name__ == '__main__':
    num = int(sys.stdin.readline())
    case_n = list(map(int, sys.stdin.readline().split()))

    # num = 5000
    # case_n = [10000 for i in range(num)]
    rmq = RMQ(num)

    assert len(case_n) == num

    print(painting_fences())

https://codeforces.com/contest/448/submission/70366562

Thank you! Nice coding!

I tried to use generator to resolve the problem but failed. It's not working as explained on stackoverflow.

Hi,

I don't suppose you have some example data that this works with, I would like to use it for a project but am unsure how to run it. Is it possible to get it to take in a normal array without reading from a file?

Any help would be greatly appreciated :)

Hi,

I don't suppose you have some example data that this works with, I would like to use it for a project but am unsure how to run it. Is it possible to get it to take in a normal array without reading from a file?

Any help would be greatly appreciated :)

Hi Joshua,

Both the original code and the snippe for the codeforce example I pasted in comment use standard input(so when you run the program, you can enter the input from the console). Or you can use something like tho following to initialize the RMQ structure from a array.

if __name__ == '__main__':
    rmq = RMQ(10)
    data = [1, 2, 5, 3, 4, 2, 1, 5, 3, 2]
    for idx, value in enumerate(data):
        rmq.update(idx, value)

Great code, I am usually needing one RMQ implementation for some leetcode problems. I just used it for this problem btw (which is not the fastest for that problem, but I was curious in solving it with RMQ):

https://leetcode.com/problems/jump-game-ii/discuss/1047061/Python3%3A-backwards-DP-%2B-RMQ-O(n-log-n)