Instead of divide and conquer, you can keep a sorted vector of pairs {block index, minimum in block} which you can update naively after each query with a binary search.