pub trait Magma {
type T: Clone;
// Required method
fn operate(x: &Self::T, y: &Self::T) -> Self::T;
// Provided methods
fn reverse_operate(x: &Self::T, y: &Self::T) -> Self::T { ... }
fn operate_assign(x: &mut Self::T, y: &Self::T) { ... }
}Expand description
binary operaion: $T \circ T \to T$
Required Associated Types§
Required Methods§
Provided Methods§
fn reverse_operate(x: &Self::T, y: &Self::T) -> Self::T
Sourcefn operate_assign(x: &mut Self::T, y: &Self::T)
fn operate_assign(x: &mut Self::T, y: &Self::T)
Examples found in repository?
More examples
crates/competitive/src/data_structure/wavelet_matrix.rs (lines 1506-1509)
1502 pub fn fold_lessthan(&self, value: T, range: Range<usize>) -> M::T {
1503 let mut result = M::unit();
1504 self.wavelet_matrix
1505 .query_less_than(value, range, |d, range| {
1506 M::operate_assign(
1507 &mut result,
1508 &self.bits[self.wavelet_matrix.level(d)].fold_abelian(range.start, range.end),
1509 );
1510 });
1511 result
1512 }
1513
1514 pub fn fold_range(&self, values: Range<T>, range: Range<usize>) -> M::T {
1515 let lower = self
1516 .wavelet_matrix
1517 .compress
1518 .index_lower_bound(&values.start);
1519 let upper = self.wavelet_matrix.compress.index_lower_bound(&values.end);
1520 if lower >= upper {
1521 return M::unit();
1522 }
1523 let mut range = range;
1524 for d in (0..self.wavelet_matrix.bit_length).rev() {
1525 let level = self.wavelet_matrix.level(d);
1526 let start1 = self.wavelet_matrix.bit_vectors[level].rank1(range.start);
1527 let end1 = self.wavelet_matrix.bit_vectors[level].rank1(range.end);
1528 let start0 = range.start - start1;
1529 let end0 = range.end - end1;
1530 if ((lower >> d) & 1) == ((upper >> d) & 1) {
1531 if ((lower >> d) & 1) == 0 {
1532 range = start0..end0;
1533 } else {
1534 range = self.wavelet_matrix.zeros[level] + start1
1535 ..self.wavelet_matrix.zeros[level] + end1;
1536 }
1537 continue;
1538 }
1539 let zero_range = start0..end0;
1540 let one_range =
1541 self.wavelet_matrix.zeros[level] + start1..self.wavelet_matrix.zeros[level] + end1;
1542 let lower_sum = self.fold_lessthan_index(lower, zero_range.clone(), d);
1543 let upper_sum = self.fold_lessthan_index(upper, one_range, d);
1544 let zero_sum = self.bits[level].fold_abelian(zero_range.start, zero_range.end);
1545 let mut result = M::rinv_operate(&zero_sum, &lower_sum);
1546 M::operate_assign(&mut result, &upper_sum);
1547 return result;
1548 }
1549 M::unit()
1550 }
1551
1552 fn fold_lessthan_index(&self, idx: usize, mut range: Range<usize>, bits: usize) -> M::T {
1553 let mut result = M::unit();
1554 for d in (idx.trailing_zeros() as usize..bits).rev() {
1555 let level = self.wavelet_matrix.level(d);
1556 let start1 = self.wavelet_matrix.bit_vectors[level].rank1(range.start);
1557 let end1 = self.wavelet_matrix.bit_vectors[level].rank1(range.end);
1558 let start0 = range.start - start1;
1559 let end0 = range.end - end1;
1560 if ((idx >> d) & 1) != 0 {
1561 M::operate_assign(&mut result, &self.bits[level].fold_abelian(start0, end0));
1562 range.start = self.wavelet_matrix.zeros[level] + start1;
1563 range.end = self.wavelet_matrix.zeros[level] + end1;
1564 } else {
1565 range.start = start0;
1566 range.end = end0;
1567 }
1568 }
1569 result
1570 }
1571}
1572
1573#[derive(Debug, Clone)]
1574pub struct WaveletMatrixFold<'a, T, M>
1575where
1576 T: Ord + Clone,
1577 M: AbelianGroup,
1578{
1579 wavelet_matrix: &'a WaveletMatrix<T>,
1580 prefix: Vec<M::T>,
1581 offsets: Vec<usize>,
1582}
1583
1584impl<'a, T, M> WaveletMatrixFold<'a, T, M>
1585where
1586 T: Ord + Clone,
1587 M: AbelianGroup,
1588{
1589 pub fn fold_lessthan(&self, val: T, range: Range<usize>) -> M::T {
1590 self.fold_lessthan_with_count(val, range).1
1591 }
1592
1593 pub fn fold_lessthan_with_count(&self, val: T, range: Range<usize>) -> (usize, M::T) {
1594 debug_assert!(range.end <= self.wavelet_matrix.len);
1595 let [result] = self.fold_lessthan_indices_with_count(
1596 [self.wavelet_matrix.compress.index_lower_bound(&val)],
1597 [range],
1598 self.wavelet_matrix.bit_length,
1599 );
1600 result
1601 }
1602
1603 pub fn fold_range(&self, valrange: Range<T>, range: Range<usize>) -> M::T {
1604 self.fold_range_with_count(valrange, range).1
1605 }
1606
1607 pub fn fold_range_with_count(
1608 &self,
1609 valrange: Range<T>,
1610 mut range: Range<usize>,
1611 ) -> (usize, M::T) {
1612 debug_assert!(range.end <= self.wavelet_matrix.len);
1613 let lower = self
1614 .wavelet_matrix
1615 .compress
1616 .index_lower_bound(&valrange.start);
1617 let upper = self
1618 .wavelet_matrix
1619 .compress
1620 .index_lower_bound(&valrange.end);
1621 if lower >= upper {
1622 return (0, M::unit());
1623 }
1624 for d in (0..self.wavelet_matrix.bit_length).rev() {
1625 let level = self.wavelet_matrix.level(d);
1626 let start1 = self.wavelet_matrix.bit_vectors[level].rank1(range.start);
1627 let end1 = self.wavelet_matrix.bit_vectors[level].rank1(range.end);
1628 let start0 = range.start - start1;
1629 let end0 = range.end - end1;
1630 if ((lower >> d) & 1) == ((upper >> d) & 1) {
1631 if ((lower >> d) & 1) == 0 {
1632 range = start0..end0;
1633 } else {
1634 range = self.wavelet_matrix.zeros[level] + start1
1635 ..self.wavelet_matrix.zeros[level] + end1;
1636 }
1637 continue;
1638 }
1639 let zero_range = start0..end0;
1640 let one_range =
1641 self.wavelet_matrix.zeros[level] + start1..self.wavelet_matrix.zeros[level] + end1;
1642 let [(lower_count, lower_sum), (upper_count, upper_sum)] = self
1643 .fold_lessthan_indices_with_count(
1644 [lower, upper],
1645 [zero_range.clone(), one_range],
1646 d,
1647 );
1648 let zero_sum = self.range_sum(level, zero_range.clone());
1649 return (
1650 zero_range.len() - lower_count + upper_count,
1651 M::operate(&M::rinv_operate(&zero_sum, &lower_sum), &upper_sum),
1652 );
1653 }
1654 (0, M::unit())
1655 }
1656
1657 #[inline]
1658 fn range_sum(&self, level: usize, range: Range<usize>) -> M::T {
1659 let offset = self.offsets[level];
1660 M::rinv_operate(
1661 &self.prefix[offset + range.end],
1662 &self.prefix[offset + range.start],
1663 )
1664 }
1665
1666 fn fold_lessthan_indices_with_count<const N: usize>(
1667 &self,
1668 indices: [usize; N],
1669 mut ranges: [Range<usize>; N],
1670 bits: usize,
1671 ) -> [(usize, M::T); N] {
1672 let mut results = std::array::from_fn(|_| (0, M::unit()));
1673 let last = indices
1674 .iter()
1675 .map(|index| index.trailing_zeros() as usize)
1676 .min()
1677 .unwrap_or(bits);
1678 for d in (last..bits).rev() {
1679 let level = self.wavelet_matrix.level(d);
1680 for ((&index, range), (count, sum)) in indices.iter().zip(&mut ranges).zip(&mut results)
1681 {
1682 let start1 = self.wavelet_matrix.bit_vectors[level].rank1(range.start);
1683 let end1 = self.wavelet_matrix.bit_vectors[level].rank1(range.end);
1684 let start0 = range.start - start1;
1685 let end0 = range.end - end1;
1686 if ((index >> d) & 1) != 0 {
1687 *count += end0 - start0;
1688 M::operate_assign(sum, &self.range_sum(level, start0..end0));
1689 range.start = self.wavelet_matrix.zeros[level] + start1;
1690 range.end = self.wavelet_matrix.zeros[level] + end1;
1691 } else {
1692 range.start = start0;
1693 range.end = end0;
1694 }
1695 }
1696 }
1697 results
1698 }crates/competitive/src/data_structure/binary_indexed_tree.rs (line 51)
46 pub fn from_slice(slice: &[M::T]) -> Self {
47 let n = slice.len();
48 let mut bit = vec![M::unit(); n + 1];
49 for (i, x) in slice.iter().enumerate() {
50 let k = i + 1;
51 M::operate_assign(&mut bit[k], x);
52 let j = k + (k & (!k + 1));
53 if j <= n {
54 bit[j] = M::operate(&bit[j], &bit[k]);
55 }
56 }
57 Self { n, bit }
58 }
59 #[inline]
60 /// fold [0, k)
61 pub fn accumulate0(&self, mut k: usize) -> M::T {
62 debug_assert!(k <= self.n);
63 let mut res = M::unit();
64 while k > 0 {
65 res = M::operate(&res, &self.bit[k]);
66 k -= k & (!k + 1);
67 }
68 res
69 }
70 #[inline]
71 /// fold [0, k]
72 pub fn accumulate(&self, k: usize) -> M::T {
73 self.accumulate0(k + 1)
74 }
75 #[inline]
76 pub fn update(&mut self, k: usize, x: M::T) {
77 debug_assert!(k < self.n);
78 let mut k = k + 1;
79 while k <= self.n {
80 self.bit[k] = M::operate(&self.bit[k], &x);
81 k += k & (!k + 1);
82 }
83 }
84 #[inline]
85 pub fn partition_point_acc<P>(&self, mut pred: P) -> usize
86 where
87 P: FnMut(&M::T) -> bool,
88 {
89 let n = self.n;
90 let mut acc = M::unit();
91 let mut pos = 0;
92 let mut k = n.next_power_of_two();
93 while k > 0 {
94 if k + pos <= n {
95 let nacc = M::operate(&acc, &self.bit[k + pos]);
96 if pred(&nacc) {
97 pos += k;
98 acc = nacc;
99 }
100 }
101 k >>= 1;
102 }
103 pos
104 }
105}
106
107impl<G: Group> BinaryIndexedTree<G> {
108 #[inline]
109 pub fn fold(&self, l: usize, r: usize) -> G::T {
110 debug_assert!(l <= self.n && r <= self.n);
111 G::operate(&G::inverse(&self.accumulate0(l)), &self.accumulate0(r))
112 }
113 #[inline]
114 pub fn fold_abelian(&self, mut l: usize, mut r: usize) -> G::T
115 where
116 G: AbelianGroup,
117 {
118 debug_assert!(l <= self.n && r <= self.n);
119 if l == r {
120 return G::unit();
121 }
122 // The prefix above the highest differing bit cancels in an Abelian group.
123 let common = l & !(usize::MAX >> (l ^ r).leading_zeros());
124 let mut left = G::unit();
125 let mut right = G::unit();
126 while l != common {
127 G::operate_assign(&mut left, &self.bit[l]);
128 l &= l - 1;
129 }
130 while r != common {
131 G::operate_assign(&mut right, &self.bit[r]);
132 r &= r - 1;
133 }
134 G::rinv_operate(&right, &left)
135 }crates/competitive/src/math/bitwiseand_convolve.rs (line 98)
89 pub fn push(&mut self, x: M::T) {
90 let i = self.data.len();
91 self.data.push(x);
92 let mut k = 0;
93 while i >> k & 1 == 1 {
94 let size = 1 << k;
95 let chunk = &mut self.data[i - (size * 2 - 1)..];
96 let (x, y) = chunk.split_at_mut(size);
97 for (x, y) in x.iter_mut().zip(y.iter()) {
98 M::operate_assign(x, y);
99 }
100 k += 1;
101 }
102 }crates/competitive/src/algorithm/doubling.rs (line 155)
148 pub fn find_first(
149 &self,
150 pos: usize,
151 mut pred: impl FnMut(usize, &M::T) -> bool,
152 ) -> Option<(usize, (usize, M::T))> {
153 let (mut k, (mut pos, mut x)) = self.find_last(pos, |k, x| !pred(k, x));
154 k += 1;
155 M::operate_assign(&mut x, &self.table[pos].1);
156 pos = self.table[pos].0;
157 if pred(pos, &x) {
158 Some((k, (pos, x)))
159 } else {
160 None
161 }
162 }Dyn Compatibility§
This trait is not dyn compatible.
In older versions of Rust, dyn compatibility was called "object safety".