fn fold_slice<S>(data: &[S::T], l: usize, r: usize) -> S::Twhere
S: SemiGroup,Examples found in repository?
crates/competitive/src/data_structure/static_range_product.rs (line 95)
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 }