1#[derive(Debug, Clone, PartialEq, Eq)]
17pub struct WidePrefixSums {
18 tree: Vec<u64>,
20}
21
22impl WidePrefixSums {
23 pub fn try_new(len: usize) -> Result<Self, WidePrefixError> {
28 let slots = len
29 .checked_add(1)
30 .ok_or(WidePrefixError::CapacityOverflow { len })?;
31 let mut tree = Vec::new();
32 tree.try_reserve_exact(slots)
33 .map_err(|_| WidePrefixError::AllocationFailed { len })?;
34 tree.resize(slots, 0);
35 Ok(Self { tree })
36 }
37
38 pub fn try_from_values(values: &[u64]) -> Result<Self, WidePrefixError> {
43 let mut total = 0_u64;
48 for (index, &value) in values.iter().enumerate() {
49 total = total
50 .checked_add(value)
51 .ok_or(WidePrefixError::SumOverflow { index })?;
52 }
53 let mut result = Self::try_new(values.len())?;
54 for (index, &value) in values.iter().enumerate() {
55 result.tree[index + 1] = value;
56 }
57 for index in 1..=values.len() {
58 let Some(parent) = index.checked_add(lowbit(index)) else {
59 continue;
60 };
61 if parent <= values.len() {
62 result.tree[parent] += result.tree[index];
63 }
64 }
65 Ok(result)
66 }
67
68 #[must_use]
70 pub fn len(&self) -> usize {
71 self.tree.len() - 1
72 }
73
74 #[must_use]
76 pub fn is_empty(&self) -> bool {
77 self.len() == 0
78 }
79
80 pub fn value(&self, index: usize) -> Result<u64, WidePrefixError> {
82 self.check_index(index)?;
83 let end = self.prefix_before(index + 1)?;
84 let start = self.prefix_before(index)?;
85 end.checked_sub(start)
86 .ok_or(WidePrefixError::InvariantViolation { index })
87 }
88
89 pub fn prefix_before(&self, end: usize) -> Result<u64, WidePrefixError> {
93 if end > self.len() {
94 return Err(WidePrefixError::EndOutOfBounds {
95 end,
96 len: self.len(),
97 });
98 }
99 let mut index = end;
100 let mut sum = 0_u64;
101 while index != 0 {
102 sum = sum
103 .checked_add(self.tree[index])
104 .ok_or(WidePrefixError::SumOverflow { index: index - 1 })?;
105 index -= lowbit(index);
106 }
107 Ok(sum)
108 }
109
110 pub fn prefix_inclusive(&self, index: usize) -> Result<u64, WidePrefixError> {
112 self.check_index(index)?;
113 self.prefix_before(index + 1)
114 }
115
116 pub fn range(&self, start: usize, end: usize) -> Result<u64, WidePrefixError> {
118 if start > end || end > self.len() {
119 return Err(WidePrefixError::InvalidRange {
120 start,
121 end,
122 len: self.len(),
123 });
124 }
125 let before_start = self.prefix_before(start)?;
126 let before_end = self.prefix_before(end)?;
127 before_end
128 .checked_sub(before_start)
129 .ok_or(WidePrefixError::InvariantViolation { index: start })
130 }
131
132 pub fn total(&self) -> Result<u64, WidePrefixError> {
134 self.prefix_before(self.len())
135 }
136
137 pub fn add(&mut self, index: usize, delta: i64) -> Result<(), WidePrefixError> {
143 self.check_index(index)?;
144 if delta >= 0 {
145 self.apply_unsigned_delta(index, delta as u64, true)
146 } else {
147 self.apply_unsigned_delta(index, delta.unsigned_abs(), false)
148 }
149 }
150
151 pub fn set(&mut self, index: usize, value: u64) -> Result<(), WidePrefixError> {
153 let current = self.value(index)?;
154 if value >= current {
155 self.apply_unsigned_delta(index, value - current, true)
156 } else {
157 self.apply_unsigned_delta(index, current - value, false)
158 }
159 }
160
161 pub fn rebuild(&mut self, values: &[u64]) -> Result<(), WidePrefixError> {
164 let replacement = Self::try_from_values(values)?;
165 *self = replacement;
166 Ok(())
167 }
168
169 pub fn insert(&mut self, index: usize, value: u64) -> Result<(), WidePrefixError> {
175 let new_len = self
176 .len()
177 .checked_add(1)
178 .ok_or(WidePrefixError::CapacityOverflow { len: self.len() })?;
179 if index > self.len() {
180 return Err(WidePrefixError::IndexOutOfBounds {
181 index,
182 len: self.len(),
183 });
184 }
185 let mut values = self.snapshot_values()?;
186 values
187 .try_reserve_exact(1)
188 .map_err(|_| WidePrefixError::AllocationFailed { len: new_len })?;
189 values.insert(index, value);
190 let replacement = Self::try_from_values(&values)?;
191 *self = replacement;
192 Ok(())
193 }
194
195 pub fn remove(&mut self, index: usize) -> Result<u64, WidePrefixError> {
197 self.check_index(index)?;
198 let mut values = self.snapshot_values()?;
199 let removed = values.remove(index);
200 let replacement = Self::try_from_values(&values)?;
201 *self = replacement;
202 Ok(removed)
203 }
204
205 #[must_use]
212 pub fn partition_point(&self, offset: u64) -> usize {
213 let mut position = 0_usize;
214 let mut consumed = 0_u64;
215 let mut bit = highest_power_of_two(self.len());
216 while bit != 0 {
217 let Some(next) = position.checked_add(bit) else {
218 bit >>= 1;
219 continue;
220 };
221 if next <= self.len()
222 && let Some(candidate) = consumed.checked_add(self.tree[next])
223 && candidate <= offset
224 {
225 position = next;
226 consumed = candidate;
227 }
228 bit >>= 1;
229 }
230 position
231 }
232
233 fn check_index(&self, index: usize) -> Result<(), WidePrefixError> {
234 if index >= self.len() {
235 return Err(WidePrefixError::IndexOutOfBounds {
236 index,
237 len: self.len(),
238 });
239 }
240 Ok(())
241 }
242
243 fn snapshot_values(&self) -> Result<Vec<u64>, WidePrefixError> {
244 let mut values = Vec::new();
245 values
246 .try_reserve_exact(self.len())
247 .map_err(|_| WidePrefixError::AllocationFailed { len: self.len() })?;
248 for index in 0..self.len() {
249 values.push(self.value(index)?);
250 }
251 Ok(values)
252 }
253
254 fn apply_unsigned_delta(
255 &mut self,
256 index: usize,
257 delta: u64,
258 increasing: bool,
259 ) -> Result<(), WidePrefixError> {
260 if increasing {
268 self.total()?
269 .checked_add(delta)
270 .ok_or(WidePrefixError::SumOverflow { index })?;
271 } else if self.value(index)? < delta {
272 return Err(WidePrefixError::SumUnderflow { index });
273 }
274
275 let mut cursor = index + 1;
276 while cursor <= self.len() {
277 self.tree[cursor] = if increasing {
278 self.tree[cursor] + delta
279 } else {
280 self.tree[cursor] - delta
281 };
282 let Some(next) = cursor.checked_add(lowbit(cursor)) else {
285 break;
286 };
287 cursor = next;
288 }
289 Ok(())
290 }
291}
292
293#[derive(Debug, Clone, Copy, PartialEq, Eq)]
295pub enum WidePrefixError {
296 CapacityOverflow { len: usize },
298 AllocationFailed { len: usize },
300 IndexOutOfBounds { index: usize, len: usize },
302 InvalidRange {
304 start: usize,
305 end: usize,
306 len: usize,
307 },
308 EndOutOfBounds { end: usize, len: usize },
310 SumOverflow { index: usize },
312 SumUnderflow { index: usize },
314 InvariantViolation { index: usize },
316}
317
318impl std::fmt::Display for WidePrefixError {
319 fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
320 match self {
321 Self::CapacityOverflow { len } => {
322 write!(formatter, "wide-prefix length overflow: {len}")
323 }
324 Self::AllocationFailed { len } => {
325 write!(formatter, "wide-prefix allocation failed: {len}")
326 }
327 Self::IndexOutOfBounds { index, len } => {
328 write!(
329 formatter,
330 "wide-prefix index {index} out of bounds (len={len})"
331 )
332 }
333 Self::InvalidRange { start, end, len } => {
334 write!(
335 formatter,
336 "wide-prefix range [{start}, {end}) invalid (len={len})"
337 )
338 }
339 Self::EndOutOfBounds { end, len } => {
340 write!(formatter, "wide-prefix end {end} out of bounds (len={len})")
341 }
342 Self::SumOverflow { index } => write!(formatter, "wide-prefix sum overflow at {index}"),
343 Self::SumUnderflow { index } => {
344 write!(formatter, "wide-prefix sum underflow at {index}")
345 }
346 Self::InvariantViolation { index } => {
347 write!(formatter, "wide-prefix invariant violation at {index}")
348 }
349 }
350 }
351}
352
353impl std::error::Error for WidePrefixError {}
354
355#[inline]
356fn lowbit(value: usize) -> usize {
357 value.isolate_lowest_one()
358}
359
360#[inline]
361fn highest_power_of_two(value: usize) -> usize {
362 if value == 0 {
363 0
364 } else {
365 1 << (usize::BITS - 1 - value.leading_zeros())
366 }
367}
368
369#[cfg(test)]
370mod tests {
371 use super::{WidePrefixError, WidePrefixSums};
372
373 #[test]
374 fn supports_totals_above_u32() {
375 let sums = WidePrefixSums::try_from_values(&[u32::MAX as u64, 7]).unwrap();
376 assert_eq!(sums.prefix_before(1).unwrap(), u32::MAX as u64);
377 assert_eq!(sums.total().unwrap(), u64::from(u32::MAX) + 7);
378 assert_eq!(sums.range(1, 2).unwrap(), 7);
379 }
380
381 #[test]
382 fn partition_point_is_half_open_and_includes_zero_height_entries() {
383 let sums = WidePrefixSums::try_from_values(&[0, 3, 0, 4]).unwrap();
384 assert_eq!(sums.partition_point(0), 1);
385 assert_eq!(sums.partition_point(3), 3);
386 assert_eq!(sums.partition_point(6), 3);
387 assert_eq!(sums.partition_point(7), 4);
388 }
389
390 #[test]
391 fn failed_update_is_atomic() {
392 let mut sums = WidePrefixSums::try_from_values(&[u64::MAX]).unwrap();
393 assert_eq!(
394 sums.add(0, 1),
395 Err(WidePrefixError::SumOverflow { index: 0 })
396 );
397 assert_eq!(sums.value(0).unwrap(), u64::MAX);
398 }
399
400 #[test]
401 fn construction_rejects_total_overflow() {
402 assert_eq!(
403 WidePrefixSums::try_from_values(&[u64::MAX, 1]),
404 Err(WidePrefixError::SumOverflow { index: 1 })
405 );
406 }
407
408 #[test]
409 fn negative_adjustment_checks_the_entry_not_just_its_nodes() {
410 let mut sums = WidePrefixSums::try_from_values(&[5, 5]).unwrap();
412 assert_eq!(
413 sums.add(1, -7),
414 Err(WidePrefixError::SumUnderflow { index: 1 })
415 );
416 assert_eq!(sums.value(1).unwrap(), 5);
417 assert_eq!(sums.total().unwrap(), 10);
418 }
419
420 #[test]
421 fn total_overflow_is_rejected_when_no_node_overflows() {
422 assert_eq!(
425 WidePrefixSums::try_from_values(&[u64::MAX, 0, 1]),
426 Err(WidePrefixError::SumOverflow { index: 2 })
427 );
428 let mut sums = WidePrefixSums::try_from_values(&[u64::MAX, 0, 0]).unwrap();
429 assert_eq!(
430 sums.add(2, 1),
431 Err(WidePrefixError::SumOverflow { index: 2 })
432 );
433 assert_eq!(sums.value(2).unwrap(), 0);
434 assert_eq!(sums.total().unwrap(), u64::MAX);
435 }
436
437 #[test]
438 fn updates_match_a_plain_vector_model() {
439 let mut state = 0x2545_f491_4f6c_dd1d_u64;
441 let mut next = move || {
442 state ^= state << 13;
443 state ^= state >> 7;
444 state ^= state << 17;
445 state
446 };
447 let fits = |model: &[u64], index: usize, value: u64| {
450 model
451 .iter()
452 .enumerate()
453 .filter(|&(i, _)| i != index)
454 .try_fold(value, |sum, (_, &v)| sum.checked_add(v))
455 .is_some()
456 };
457 let mut model = vec![0_u64; 9];
458 let mut sums = WidePrefixSums::try_from_values(&model).unwrap();
459 for _ in 0..20_000 {
460 let index = (next() % 9) as usize;
461 let magnitude = next() >> (next() % 64);
462 let target = if next() % 2 == 0 {
463 let delta = (magnitude >> 1) as i64 * if next() % 2 == 0 { 1 } else { -1 };
464 let entry = if delta >= 0 {
465 model[index].checked_add(delta.unsigned_abs())
466 } else {
467 model[index].checked_sub(delta.unsigned_abs())
468 }
469 .filter(|&entry| fits(&model, index, entry));
470 assert_eq!(sums.add(index, delta).is_ok(), entry.is_some());
471 entry
472 } else {
473 let entry = Some(magnitude).filter(|&entry| fits(&model, index, entry));
474 assert_eq!(sums.set(index, magnitude).is_ok(), entry.is_some());
475 entry
476 };
477 if let Some(entry) = target {
478 model[index] = entry;
479 }
480 for (i, &value) in model.iter().enumerate() {
481 assert_eq!(sums.value(i), Ok(value));
482 }
483 }
484 }
485
486 #[test]
487 fn negative_adjustment_rejects_underflow() {
488 let mut sums = WidePrefixSums::try_from_values(&[2, 4]).unwrap();
489 assert_eq!(
490 sums.add(0, -3),
491 Err(WidePrefixError::SumUnderflow { index: 0 })
492 );
493 assert_eq!(sums.total().unwrap(), 6);
494 }
495
496 #[test]
497 fn constructor_and_queries_validate_boundaries() {
498 assert_eq!(
499 WidePrefixSums::try_new(usize::MAX),
500 Err(WidePrefixError::CapacityOverflow { len: usize::MAX })
501 );
502 let sums = WidePrefixSums::try_new(2).unwrap();
503 assert_eq!(
504 sums.value(2),
505 Err(WidePrefixError::IndexOutOfBounds { index: 2, len: 2 })
506 );
507 assert_eq!(
508 sums.range(2, 1),
509 Err(WidePrefixError::InvalidRange {
510 start: 2,
511 end: 1,
512 len: 2
513 })
514 );
515 }
516
517 #[test]
518 fn set_and_rebuild_preserve_checked_semantics() {
519 let mut sums = WidePrefixSums::try_from_values(&[1, 2, 3]).unwrap();
520 sums.set(1, u64::from(u32::MAX) + 1).unwrap();
521 assert_eq!(sums.value(1).unwrap(), u64::from(u32::MAX) + 1);
522 sums.rebuild(&[5, 8]).unwrap();
523 assert_eq!(sums.total().unwrap(), 13);
524 assert_eq!(sums.len(), 2);
525 }
526
527 #[test]
528 fn structural_edits_are_bounded_and_checked() {
529 let mut sums = WidePrefixSums::try_from_values(&[2, 4]).unwrap();
530 sums.insert(1, 3).unwrap();
531 assert_eq!(sums.total().unwrap(), 9);
532 assert_eq!(sums.value(1).unwrap(), 3);
533 assert_eq!(sums.remove(0).unwrap(), 2);
534 assert_eq!(sums.range(0, 2).unwrap(), 7);
535 assert_eq!(
536 sums.insert(usize::MAX, 1),
537 Err(WidePrefixError::IndexOutOfBounds {
538 index: usize::MAX,
539 len: 2
540 })
541 );
542 }
543
544 #[test]
545 fn structural_overflow_preserves_existing_tree() {
546 let mut sums = WidePrefixSums::try_from_values(&[u64::MAX]).unwrap();
547 assert_eq!(
548 sums.insert(1, 1),
549 Err(WidePrefixError::SumOverflow { index: 1 })
550 );
551 assert_eq!(sums.len(), 1);
552 assert_eq!(sums.value(0).unwrap(), u64::MAX);
553 }
554}