fn scaled_block_shift(alpha: usize) -> usizeExamples found in repository?
crates/competitive/src/data_structure/static_range_product.rs (line 55)
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 }