Range Minimum Query

Method 1 : DP (ST算法)

Sparse Table

O(nlogn) 预处理, O(1) 时间回答每个查询.

M[i][j]: from index i, length : 2 ^ j 子数组中的最小值.

当我们求解S[ i ] [ j ] ， 也就是求一个从index i的数组，长度为2 ^ j的子数组最小值， 可以把这个子数组再分成两半，每一半长度为2 ^ (j - 1), 于是前一半最小M[i][j - 1] 后一半 M[i + 2 ^ (j - 1)] [j - 1]

M[i][j] = M[i - 1][j] , M[i + 2 ^ (j - 1)][j - 1]

base case : 2 ^ 0 = 1.

如何加速查询?

assume we are searching from [u , v] ,

len = (u - v + 1). k = log 2(len).

then we could divide this array into

start from u, len = 2 ^ k.

ending with v, len = 2 ^ k. where start_Index = v - 2 ^ k + 1.

RMQ(u, v) = min (M[u][k], M[v - 2^k + 1][k])

Method 2: Interval Tree

public class RMQ {
    int[] M; //prefix sum
    public class Interval {
        int left;
        int right;
    }
    public class TreeNode {
        Interval inter;
        public TreeNode(Interval inter) {
            this.inter = inter;
        }
    }
    // i .. j is current interval of tree.
    // x... y is query interval
    public TreeNode query (TreeNode root, int i, int j, int x, int y) {
           if (x > j || y < i) {
                return null;
           }
           //if query interval covers current interval
           //return the current nodes minimum index.
           if (x <= i && y >= j) {
                return root;
           }
           int mid = i + (j - i) / 2;
           if (x > mid) {
               return query(root.right,mid + 1,j,x,y); 
           } else if (y <= mid) {
               return query(root.left,i, mid, x, y); 
           } else {
                TreeNode p1 = query(root.left,i, mid, x, y);
                TreeNode p2 = query(root.right,mid + 1, j, x, y);
                if (p1 != null && p2 != null) {
                    int min = Math.min(p1.sum, p2.sum);
                    return min == p1.sum ? p1 : p2;
                }
                return p1 == null ? p2 : p1;
           }
    }
}

Method 3: Range min query with Cartesian Tree

Definition of Cartesian Tree

root is smallest in tree and each path is ascending.

-> LCA(i, j) -> min(i,j)

How to construct ? from left to right insert to right subtree