范围最值查询 (Range Minimum Query)

问题

在数组 [l, r] 中查找最值

思路

1. 在数组 [l, r] 中的最值等于
   （[l, (l+r)/2] 中的最值 + [(l+r)/2 + 1, r] 中的最值）的最值
2. 直到子问题中数组小于等于 2, 即可简单求解
3. 合并子问题的解，得到最终解

代码

(define (rmq vec l r m)
  (if (< (- r l) 2)
      (m (vector-ref vec l) (vector-ref vec r))
      (m (rmq vec
              l
              (quotient (+ l r) 2)
              m)
         (rmq vec
              (+ (quotient (+ l r) 2) 1)
              r
              m))))

(rmq v
     0
     (- (vector-length v) 1)
     (lambda (a b)
       (if (< a b)
           a
           b)))