使用稀疏表解决区间最大值查询问题

给定一个数组 arr[]，我们的任务是回答一系列查询，以找到索引范围 arr[L…R] 内所有元素的最大值。

示例：

**输入:** arr[] = {6, 7, 4, 5, 1, 3}, q[][] = {{0, 5}, {3, 5}, {2, 4}}
**输出:**
7
5
5

**输入:** arr[] = {3, 34, 1}, q[][] = {{1, 2}}
**输出:**
34

方法： 此前我们讨论过一个类似的问题，即回答区间最小值查询。我们可以采用相同的方法，稍作修改来回答区间最大值查询。以下是具体的修改思路：

// 单元素子数组的最大值就是该元素本身
lookup[i][0] = arr[i]

// 如果 lookup[0][2] ?  lookup[4][2], 
// 则 lookup[0][3] = lookup[0][2]
**如果** lookup[i][j-1] ? lookup[i+2^(j-1)-1][j-1]
   lookup[i][j] = lookup[i][j-1]

// 如果 lookup[0][2] <  lookup[4][2], 
// 则 lookup[0][3] = lookup[4][2]
**否则** 
   lookup[i][j] = lookup[i+2^(j-1)-1][j-1]

下面是上述方法的实现代码：

C++


CODEBLOCK_d6ba8248


Java

`

// Java implementation of the approach
import java.util.*;
class GFG {

    static final int MAX = 500;

    // lookup[i][j] 用于存储 arr[i..j] 的最大值。
    // 理想情况下，查找表的大小不应固定，而应根据 n Log n 确定。
    // 这里为了代码简洁，将其设为常数。
    static int lookup[][] = new int[MAX][MAX];

    // 以自底向上的方式填充查找数组 lookup[][]
    static void buildSparseTable(int arr[], int n)
    {
        // 初始化长度为 1 的区间的 M 值
        for (int i = 0; i < n; i++)
            lookup[i][0] = arr[i];

        // 从较小的区间计算到较大的区间
        for (int j = 1; (1 << j) <= n; j++) {

            // 计算所有大小为 2^j 的区间的最大值
            for (int i = 0; (i + (1 << j) - 1)  lookup[i + (1 << (j - 1))][j - 1])
                    lookup[i][j] = lookup[i][j - 1];
                else
                    lookup[i][j] = lookup[i + (1 <= lookup[R - (1 << j) + 1][j])
            return lookup[L][j];

        else
            return lookup[R - (1 << j) + 1][j];
    }

    // Driver program
    public static void main(String args[])
    {
        int a[] = { 7, 2, 3, 0, 5, 10, 3, 12, 18 };
        int n = a.length;

        buildSparseTable(a, n);

        System.out.println(query(0, 4));
        System.out.println(que