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

haar_lib/ds/
segtree_bidir.rs
