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

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)