haar_lib/algo/
static_range_freq_query.rs

1//! 配列に対する範囲頻度取得クエリ
2
3use crate::algo::bsearch_slice::BinarySearch;
4use std::collections::HashMap;
5use std::hash::Hash;
6use std::ops::Range;
7
8/// 配列に対する範囲頻度取得クエリを処理する。
9pub struct StaticRangeFreqQuery<T> {
10    map: HashMap<T, Vec<usize>>,
11}
12
13impl<T: Hash + Eq> StaticRangeFreqQuery<T> {
14    /// **Time complexity** $O(|a|)$
15    pub fn new(a: Vec<T>) -> Self {
16        let mut map = HashMap::new();
17
18        for (i, x) in a.into_iter().enumerate() {
19            map.entry(x).or_insert_with(Vec::new).push(i);
20        }
21
22        Self { map }
23    }
24
25    /// **Time complexity** $O(\log |a|)$
26    pub fn query(&self, Range { start, end }: Range<usize>, value: &T) -> usize {
27        if let Some(a) = self.map.get(value) {
28            let lower = a.lower_bound(&start);
29            let upper = a.lower_bound(&end);
30
31            upper - lower
32        } else {
33            0
34        }
35    }
36}
37
38#[cfg(test)]
39mod tests {
40    use super::*;
41    use my_testtools::*;
42    use rand::Rng;
43
44    #[test]
45    fn test() {
46        let mut rng = rand::thread_rng();
47
48        let m = 100;
49        let n = 1000;
50        let q = 100;
51
52        let a = (0..n).map(|_| rng.gen_range(0..m)).collect::<Vec<_>>();
53        let sfq = StaticRangeFreqQuery::new(a.clone());
54
55        for _ in 0..q {
56            let lr = rand_range(&mut rng, 0..n);
57            let x: u32 = rng.gen_range(0..m);
58
59            assert_eq!(
60                sfq.query(lr.clone(), &x),
61                a[lr].iter().filter(|&&y| y == x).count()
62            );
63        }
64    }
65}
haar_lib/algo/static_range_freq_query.rs

haar_lib/algo/
static_range_freq_query.rs
