2022-07-05：给定一个数组，想随时查询任何范围上的最大值。 如果只是根据初始数组建立、并且以后没有修改

2022-07-05：给定一个数组，想随时查询任何范围上的最大值。 如果只是根据初始数组建立、并且以后没有修改， 那么RMQ方法比线段树方法好实现，时间复杂度O(NlogN)，额外空间复杂度O(NlogN)。 来自小红书。3.13笔试。

答案2022-07-05：

RMQ范围最大值和最小值查询，不支持更新。 空间复杂度：O(N*logN)。 查询复杂度：O(1)。

代码用rust编写。代码如下：

use rand::Rng;
fn main() {
    let nn: i32 = 150;
    let vv = 200;
    let test_time_out = 20000;
    let test_time_in = 200;
    println!("测试开始");
    for i in 0..test_time_out {
        let n = rand::thread_rng().gen_range(0, nn) + 1;
        let mut arr = random_array(n, vv);
        let mut arr2=arr.clone();
        let m = arr.len() as i32;
        let mut rmq = RMQ::new(&mut arr);
        let mut right = Right::new(&mut arr2);
        for _ in 0..test_time_in {
            let a = rand::thread_rng().gen_range(0, m) + 1;
            let b = rand::thread_rng().gen_range(0, m) + 1;
            let l = get_min(a, b);
            let r = get_max(a, b);
            let ans1 = rmq.max(l, r);
            let ans2 = right.max(l, r);
            if ans1 != ans2 {
                println!("出错了!{}", i);
                println!("ans1 = {}", ans1);
                println!("ans2 = {}", ans2);
                break;
            }
        }
    }
    println!("测试结束");
}

pub struct RMQ {
    pub max: Vec<Vec<i32>>,
}

impl RMQ {
    // 下标一定要从1开始，没有道理！就是约定俗成！
    pub fn new(arr: &mut Vec<i32>) -> Self {
        // 长度！
        let n = arr.len() as i32;
        let mut ans: RMQ = RMQ { max: vec![] };
        // 2的几次方，可以拿下n
        let k = ans.power2(n);
        // n*logn
        let mut max: Vec<Vec<i32>> = vec![];
        for i in 0..n + 1 {
            max.push(vec![]);
            for _ in 0..k + 1 {
                max[i as usize].push(0);
            }
        }
        for i in 1..=n {
            // i 0：从下标i开始，往下连续的2的0次方个数，中，最大值
            // 1...1个
            // 2...1个
            // 3...1个
            max[i as usize][0] = arr[(i - 1) as usize];
        }
        ans.max = max;
        let mut j = 1;
        while (1 << j) <= n {
            // i...连续的、2的1次方个数，这个范围，最大值
            // i...连续的、2的2次方个数，这个范围，最大值
            // i...连续的、2的3次方个数，这个范围，最大值
            let mut i = 1;
            while i + (1 << j) - 1 <= n {
                // max[10][3]
                // 下标10开始，连续的8个数，最大值是多少
                // 1) max[10][2]
                // 2) max[14][2]
                ans.max[i as usize][j as usize] = get_max(
                    ans.max[i as usize][(j - 1) as usize],
                    ans.max[(i + (1 << (j - 1))) as usize][(j - 1) as usize],
                );
                i += 1;
            }
            j += 1;
        }
        return ans;
    }

    pub fn max(&mut self, l: i32, r: i32) -> i32 {
        // l...r -> r - l + 1 -> 2的哪个次方最接近它！
        let k = self.power2(r - l + 1);
        return get_max(
            self.max[l as usize][k as usize],
            self.max[(r - (1 << k) + 1) as usize][k as usize],
        );
    }

    fn power2(&mut self, m: i32) -> i32 {
        let mut ans = 0;
        while (1 << ans) <= (m >> 1) {
            ans += 1;
        }
        return ans;
    }
}

// 为了测试
pub struct Right {
    pub max: Vec<Vec<i32>>,
}

impl Right {
    pub fn new(arr: &mut Vec<i32>) -> Self {
        let n = arr.len() as i32;
        let mut max: Vec<Vec<i32>> = vec![];
        for i in 0..n + 1 {
            max.push(vec![]);
            for _ in 0..n + 1 {
                max[i as usize].push(0);
            }
        }

        for l in 1..=n {
            max[l as usize][l as usize] = arr[(l - 1) as usize];
            for r in l + 1..=n {
                max[l as usize][r as usize] =
                    get_max(max[l as usize][(r - 1) as usize], arr[(r - 1) as usize]);
            }
        }

        Self { max }
    }

    pub fn max(&mut self, l: i32, r: i32) -> i32 {
        self.max[l as usize][r as usize]
    }
}

fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
    if a > b {
        a
    } else {
        b
    }
}

fn get_min<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
    if a < b {
        a
    } else {
        b
    }
}

// 为了测试
fn random_array(n: i32, v: i32) -> Vec<i32> {
    let mut arr: Vec<i32> = vec![];
    for _i in 0..n {
        arr.push(rand::thread_rng().gen_range(0, v));
    }
    return arr;
}

执行结果如下：

********