2022-07-05: given an array, you want to query the maximum value in any range at any time. If it is only established according to the initial array and has not been modified in the future, the RMQ meth

2022-07-05： Given an array , Want to query the maximum value in any range at any time .
If it's just based on the initial array 、 And it has not been modified in the future ,
that RMQ Method is better than line segment tree method , Time complexity O(NlogN), Extra space complexity O(NlogN).
From little red book .3.13 written examination .

answer 2022-07-05：

RMQ Range maximum and minimum query , Update not supported .
Spatial complexity ：O(N*logN).
Query complexity ：O(1).

The code to use rust To write . The code is as follows ：

use rand::Rng;
fn main() {
    
    let nn: i32 = 150;
    let vv = 200;
    let test_time_out = 20000;
    let test_time_in = 200;
    println!(" Beginning of the test ");
    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!(" Something went wrong !{}", i);
                println!("ans1 = {}", ans1);
                println!("ans2 = {}", ans2);
                break;
            }
        }
    }
    println!(" End of test ");
}

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

impl RMQ {
    
    //  Subscript must be from 1 Start , There's no reason ！ It's a convention ！
    pub fn new(arr: &mut Vec<i32>) -> Self {
    
        //  length ！
        let n = arr.len() as i32;
        let mut ans: RMQ = RMQ {
     max: vec![] };
        // 2 Several power , You can take 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： From the subscript i Start , Continuous downward 2 Of 0 The number of power , in , Maximum 
            // 1...1 individual 
            // 2...1 individual 
            // 3...1 individual 
            max[i as usize][0] = arr[(i - 1) as usize];
        }
        ans.max = max;
        let mut j = 1;
        while (1 << j) <= n {
    
            // i... Successive 、2 Of 1 The number of power , This range , Maximum 
            // i... Successive 、2 Of 2 The number of power , This range , Maximum 
            // i... Successive 、2 Of 3 The number of power , This range , Maximum 
            let mut i = 1;
            while i + (1 << j) - 1 <= n {
    
                // max[10][3]
                //  Subscript 10 Start , Successive 8 Number , What is the maximum 
                // 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 Which power of is closest to it ！
        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;
    }
}

//  In order to test 
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
    }
}

//  In order to test 
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;
}

The results are as follows ：

---

Zuo Shen java Code