competitive::data_structure::static_range_product

Enum FixedRangeProduct

enum FixedRangeProduct<S>where
    S: SemiGroup,{
    Direct {
        data: Vec<S::T>,
    },
    Disjoint {
        table: DisjointSparseTable<S>,
    },
    Recursive {
        data: Vec<S::T>,
        block_shift: usize,
        prefix: Vec<S::T>,
        suffix: Vec<S::T>,
        between: Box<FixedRangeProduct<S>>,
    },
}

Variants§

§

Direct

Fields

§data: Vec<S::T>

§

Disjoint

Fields

§table: DisjointSparseTable<S>

§

Recursive

Fields

§data: Vec<S::T>

§block_shift: usize

§prefix: Vec<S::T>

§suffix: Vec<S::T>

§between: Box<FixedRangeProduct<S>>

Implementations§

Source §

impl<S> FixedRangeProduct<S>
where S: SemiGroup,

Source

fn new(data: Vec<S::T>, level: usize) -> Self

Examples found in repository ?

crates/competitive/src/data_structure/static_range_product.rs (line 60)

44    pub fn new(data: Vec<S::T>) -> Self {
45        let n = data.len();
46        if n == 0 {
47            return Self {
48                data,
49                block_shift: 0,
50                prefix: Vec::new(),
51                suffix: Vec::new(),
52                between: None,
53            };
54        }
55        let block_shift = scaled_block_shift(inverse_ackermann(n));
56        let block_size = 1usize << block_shift;
57        let blocks = block_products::<S>(&data, block_size);
58        let between = if blocks.products.len() > 2 {
59            let level = inverse_ackermann(blocks.products.len()).max(1);
60            Some(FixedRangeProduct::new(blocks.products, level))
61        } else {
62            None
63        };
64        Self {
65            data,
66            block_shift,
67            prefix: blocks.prefix,
68            suffix: blocks.suffix,
69            between,
70        }
71    }
72
73    #[inline]
74    pub fn len(&self) -> usize {
75        self.data.len()
76    }
77
78    #[inline]
79    pub fn is_empty(&self) -> bool {
80        self.data.is_empty()
81    }
82
83    #[inline]
84    pub fn get(&self, index: usize) -> &S::T {
85        &self.data[index]
86    }
87
88    #[inline]
89    pub fn fold(&self, l: usize, r: usize) -> S::T {
90        assert!(l < r);
91        assert!(r <= self.data.len());
92        let bl = l >> self.block_shift;
93        let br = (r - 1) >> self.block_shift;
94        if bl == br {
95            return fold_slice::<S>(&self.data, l, r);
96        }
97        let mut res = self.suffix[l].clone();
98        if bl + 1 < br {
99            let mid = self
100                .between
101                .as_ref()
102                .expect("middle block product is not built")
103                .fold(bl + 1, br);
104            res = S::operate(&res, &mid);
105        }
106        S::operate(&res, &self.prefix[r - 1])
107    }
108}
109
110#[derive(Clone)]
111enum FixedRangeProduct<S>
112where
113    S: SemiGroup,
114{
115    Direct {
116        data: Vec<S::T>,
117    },
118    Disjoint {
119        table: DisjointSparseTable<S>,
120    },
121    Recursive {
122        data: Vec<S::T>,
123        block_shift: usize,
124        prefix: Vec<S::T>,
125        suffix: Vec<S::T>,
126        between: Box<FixedRangeProduct<S>>,
127    },
128}
129
130impl<S> Debug for FixedRangeProduct<S>
131where
132    S: SemiGroup<T: Debug>,
133{
134    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
135        match self {
136            Self::Direct { data } => f.debug_struct("Direct").field("data", data).finish(),
137            Self::Disjoint { table } => f.debug_struct("Disjoint").field("table", table).finish(),
138            Self::Recursive {
139                data,
140                block_shift,
141                prefix,
142                suffix,
143                between,
144            } => f
145                .debug_struct("Recursive")
146                .field("data", data)
147                .field("block_size", &(1usize << block_shift))
148                .field("prefix", prefix)
149                .field("suffix", suffix)
150                .field("between", between)
151                .finish(),
152        }
153    }
154}
155
156impl<S> FixedRangeProduct<S>
157where
158    S: SemiGroup,
159{
160    fn new(data: Vec<S::T>, level: usize) -> Self {
161        let n = data.len();
162        if n <= DIRECT_SIZE || level == 0 {
163            return Self::Direct { data };
164        }
165        if level == 1 {
166            return Self::Disjoint {
167                table: DisjointSparseTable::new(data),
168            };
169        }
170        let block_shift = scaled_block_shift(alpha_k(level - 1, n));
171        let block_size = 1usize << block_shift;
172        if block_size <= 1 || block_size >= n {
173            return Self::Direct { data };
174        }
175        let blocks = block_products::<S>(&data, block_size);
176        let between = Box::new(Self::new(blocks.products, level - 1));
177        Self::Recursive {
178            data,
179            block_shift,
180            prefix: blocks.prefix,
181            suffix: blocks.suffix,
182            between,
183        }
184    }

Source

fn fold(&self, l: usize, r: usize) -> S::T

Examples found in repository ?

crates/competitive/src/data_structure/static_range_product.rs (line 103)

89    pub fn fold(&self, l: usize, r: usize) -> S::T {
90        assert!(l < r);
91        assert!(r <= self.data.len());
92        let bl = l >> self.block_shift;
93        let br = (r - 1) >> self.block_shift;
94        if bl == br {
95            return fold_slice::<S>(&self.data, l, r);
96        }
97        let mut res = self.suffix[l].clone();
98        if bl + 1 < br {
99            let mid = self
100                .between
101                .as_ref()
102                .expect("middle block product is not built")
103                .fold(bl + 1, br);
104            res = S::operate(&res, &mid);
105        }
106        S::operate(&res, &self.prefix[r - 1])
107    }
108}
109
110#[derive(Clone)]
111enum FixedRangeProduct<S>
112where
113    S: SemiGroup,
114{
115    Direct {
116        data: Vec<S::T>,
117    },
118    Disjoint {
119        table: DisjointSparseTable<S>,
120    },
121    Recursive {
122        data: Vec<S::T>,
123        block_shift: usize,
124        prefix: Vec<S::T>,
125        suffix: Vec<S::T>,
126        between: Box<FixedRangeProduct<S>>,
127    },
128}
129
130impl<S> Debug for FixedRangeProduct<S>
131where
132    S: SemiGroup<T: Debug>,
133{
134    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
135        match self {
136            Self::Direct { data } => f.debug_struct("Direct").field("data", data).finish(),
137            Self::Disjoint { table } => f.debug_struct("Disjoint").field("table", table).finish(),
138            Self::Recursive {
139                data,
140                block_shift,
141                prefix,
142                suffix,
143                between,
144            } => f
145                .debug_struct("Recursive")
146                .field("data", data)
147                .field("block_size", &(1usize << block_shift))
148                .field("prefix", prefix)
149                .field("suffix", suffix)
150                .field("between", between)
151                .finish(),
152        }
153    }
154}
155
156impl<S> FixedRangeProduct<S>
157where
158    S: SemiGroup,
159{
160    fn new(data: Vec<S::T>, level: usize) -> Self {
161        let n = data.len();
162        if n <= DIRECT_SIZE || level == 0 {
163            return Self::Direct { data };
164        }
165        if level == 1 {
166            return Self::Disjoint {
167                table: DisjointSparseTable::new(data),
168            };
169        }
170        let block_shift = scaled_block_shift(alpha_k(level - 1, n));
171        let block_size = 1usize << block_shift;
172        if block_size <= 1 || block_size >= n {
173            return Self::Direct { data };
174        }
175        let blocks = block_products::<S>(&data, block_size);
176        let between = Box::new(Self::new(blocks.products, level - 1));
177        Self::Recursive {
178            data,
179            block_shift,
180            prefix: blocks.prefix,
181            suffix: blocks.suffix,
182            between,
183        }
184    }
185
186    #[inline]
187    fn fold(&self, l: usize, r: usize) -> S::T {
188        match self {
189            Self::Direct { data } => fold_slice::<S>(data, l, r),
190            Self::Disjoint { table } => table.fold(l, r),
191            Self::Recursive {
192                data,
193                block_shift,
194                prefix,
195                suffix,
196                between,
197            } => {
198                let block_shift = *block_shift;
199                let bl = l >> block_shift;
200                let br = (r - 1) >> block_shift;
201                if bl == br {
202                    return fold_slice::<S>(data, l, r);
203                }
204                let mut res = suffix[l].clone();
205                if bl + 1 < br {
206                    let mid = between.fold(bl + 1, br);
207                    res = S::operate(&res, &mid);
208                }
209                S::operate(&res, &prefix[r - 1])
210            }
211        }
212    }