haar_lib/ds/
segtree_bidir.rs

1//! 非可換なモノイドを双方向から計算するセグメント木
2use std::ops::RangeBounds;
3
4use crate::{algebra::traits::Monoid, misc::range::range_bounds_to_range};
5
6/// 非可換なモノイドを双方向から計算するセグメント木
7pub struct SegtreeBidir<M: Monoid> {
8    original_size: usize,
9    size: usize,
10    data_l: Vec<M>,
11    data_r: Vec<M>,
12}
13
14impl<M: Monoid + Clone> SegtreeBidir<M> {
15    /// **Time complexity** $O(n)$
16    pub fn new(n: usize) -> Self {
17        let size = n.next_power_of_two() * 2;
18        Self {
19            original_size: n,
20            size,
21            data_l: vec![M::id(); size],
22            data_r: vec![M::id(); size],
23        }
24    }
25
26    /// モノイド列から`SegtreeBidir`を構築する。
27    ///
28    /// **Time complexity** $O(|s|)$
29    pub fn from_vec(s: Vec<M>) -> Self {
30        let mut this = Self::new(s.len());
31
32        for (i, x) in s.into_iter().enumerate() {
33            this.data_l[i + this.size / 2] = x.clone();
34            this.data_r[i + this.size / 2] = x;
35        }
36
37        for i in (1..this.size / 2).rev() {
38            this.data_l[i] = M::op(
39                this.data_l[i << 1].clone(),
40                this.data_l[(i << 1) | 1].clone(),
41            );
42            this.data_r[i] = M::op(
43                this.data_r[(i << 1) | 1].clone(),
44                this.data_r[i << 1].clone(),
45            );
46        }
47
48        this
49    }
50
51    /// **Time complexity** $O(\log n)$
52    pub fn fold_left<R: RangeBounds<usize>>(&self, range: R) -> M {
53        let (l, r) = range_bounds_to_range(range, 0, self.original_size);
54
55        let mut ret_l = M::id();
56        let mut ret_r = M::id();
57
58        let mut l = l + self.size / 2;
59        let mut r = r + self.size / 2;
60
61        while l < r {
62            if r & 1 == 1 {
63                r -= 1;
64                ret_r = M::op(self.data_l[r].clone(), ret_r);
65            }
66            if l & 1 == 1 {
67                ret_l = M::op(ret_l, self.data_l[l].clone());
68                l += 1;
69            }
70            r >>= 1;
71            l >>= 1;
72        }
73
74        M::op(ret_l, ret_r)
75    }
76
77    /// **Time complexity** $O(\log n)$
78    pub fn fold_right<R: RangeBounds<usize>>(&self, range: R) -> M {
79        let (l, r) = range_bounds_to_range(range, 0, self.original_size);
80
81        let mut ret_l = M::id();
82        let mut ret_r = M::id();
83
84        let mut l = l + self.size / 2;
85        let mut r = r + self.size / 2;
86
87        while l < r {
88            if r & 1 == 1 {
89                r -= 1;
90                ret_r = M::op(ret_r, self.data_r[r].clone());
91            }
92            if l & 1 == 1 {
93                ret_l = M::op(self.data_r[l].clone(), ret_l);
94                l += 1;
95            }
96            r >>= 1;
97            l >>= 1;
98        }
99
100        M::op(ret_r, ret_l)
101    }
102
103    /// **Time complexity** $O(\log n)$
104    pub fn assign(&mut self, i: usize, value: M) {
105        let mut i = i + self.size / 2;
106        self.data_l[i] = value.clone();
107        self.data_r[i] = value;
108
109        while i > 1 {
110            i >>= 1;
111            self.data_l[i] = M::op(
112                self.data_l[i << 1].clone(),
113                self.data_l[(i << 1) | 1].clone(),
114            );
115            self.data_r[i] = M::op(
116                self.data_r[(i << 1) | 1].clone(),
117                self.data_r[i << 1].clone(),
118            );
119        }
120    }
121}
haar_lib/ds/segtree_bidir.rs

haar_lib/ds/
segtree_bidir.rs
