Skip to main content

BinaryTrie

competitive::data_structure

Struct BinaryTrie 

Source 
pub struct BinaryTrie<M>
where
    M: LazyMapMonoid,
{
    bit_len: usize,
    max_key: u64,
    len: usize,
    xor_mask: u64,
    nodes: Vec<Node<M>>,
}

Fields§

§bit_len: usize§max_key: u64§len: usize§xor_mask: u64§nodes: Vec<Node<M>>

Implementations§

Source§

impl<M> BinaryTrie<M>
where M: LazyMapMonoid,

Source

pub fn new(bit_len: usize) -> Self

Source

pub fn with_capacity(bit_len: usize, capacity: usize) -> Self

Examples found in repository?
crates/competitive/src/data_structure/binary_trie.rs (line 47)
46    pub fn new(bit_len: usize) -> Self {
47        Self::with_capacity(bit_len, 0)
48    }
Source

pub fn len(&self) -> usize

Examples found in repository?
crates/competitive/src/data_structure/binary_trie.rs (line 77)
76    pub fn is_empty(&self) -> bool {
77        self.len() == 0
78    }
Source

pub fn is_empty(&self) -> bool

Examples found in repository?
crates/competitive/src/data_structure/binary_trie.rs (line 94)
91    pub fn modify_or_insert(&mut self, key: u64, f: impl FnOnce(&mut M::Agg)) {
92        assert!(key <= self.max_key);
93        if self.bit_len == 0 {
94            if self.is_empty() {
95                self.len = 1;
96            }
97            f(&mut self.nodes[0].agg);
98            return;
99        }
100
101        let key = key ^ self.xor_mask;
102        let mut inserted = false;
103        let mut node = 0;
104        for d in (0..self.bit_len).rev() {
105            self.push_at(node, d + 1);
106            let bit = ((key >> d) & 1) as usize;
107            if self.nodes[node].child[bit] == usize::MAX {
108                inserted = true;
109                let next = self.nodes.len();
110                self.nodes[node].child[bit] = next;
111                self.nodes.push(Node::new(node));
112            }
113            node = self.nodes[node].child[bit];
114        }
115
116        if inserted {
117            self.len += 1;
118        }
119        self.nodes[node].lazy = M::act_unit();
120        f(&mut self.nodes[node].agg);
121        self.recalc_up(node);
122    }
123
124    pub fn get(&mut self, key: u64) -> Option<M::Agg> {
125        assert!(key <= self.max_key);
126        if self.is_empty() {
127            return None;
128        }
129        if self.bit_len == 0 {
130            return Some(self.nodes[0].agg.clone());
131        }
132
133        let key = key ^ self.xor_mask;
134        let mut node = 0;
135        for d in (0..self.bit_len).rev() {
136            let bit = ((key >> d) & 1) as usize;
137            let next = self.nodes[node].child[bit];
138            if next == usize::MAX {
139                return None;
140            }
141            self.push_at(node, d + 1);
142            node = next;
143        }
144        Some(self.nodes[node].agg.clone())
145    }
146
147    pub fn update<R>(&mut self, range: R, act: M::Act)
148    where
149        R: RangeBounds<u64>,
150    {
151        let Some(range) = self.range_to_bounds(range) else {
152            return;
153        };
154        if self.is_empty() {
155            return;
156        }
157
158        let (ql, qr) = range;
159        if ql == 0 && qr == self.max_key {
160            self.apply_at(0, self.bit_len, &act);
161            return;
162        }
163
164        let mut l = ql;
165        loop {
166            let depth = (l.trailing_zeros() as usize)
167                .min(self.bit_len)
168                .min(63 - (qr - l + 1).leading_zeros() as usize);
169            let r = l | ((1u64 << depth) - 1);
170
171            let mut node = 0;
172            for d in (depth..self.bit_len).rev() {
173                self.push_at(node, d + 1);
174                node = self.nodes[node].child[(((l ^ self.xor_mask) >> d) & 1) as usize];
175                if node == usize::MAX {
176                    break;
177                }
178            }
179            if node != usize::MAX {
180                self.apply_at(node, depth, &act);
181                self.recalc_up(node);
182            }
183            if r == qr {
184                break;
185            }
186            l = r + 1;
187        }
188    }
Source

pub fn clear(&mut self)

Source

pub fn set(&mut self, key: u64, value: M::Agg)

Source

pub fn modify_or_insert(&mut self, key: u64, f: impl FnOnce(&mut M::Agg))

Examples found in repository?
crates/competitive/src/data_structure/binary_trie.rs (line 88)
87    pub fn set(&mut self, key: u64, value: M::Agg) {
88        self.modify_or_insert(key, |x| *x = value);
89    }
Source

pub fn get(&mut self, key: u64) -> Option<M::Agg>

Source

pub fn update<R>(&mut self, range: R, act: M::Act)
where R: RangeBounds<u64>,

Source

pub fn fold<R>(&mut self, range: R) -> M::Agg
where R: RangeBounds<u64>,

Source

fn apply_at(&mut self, node: usize, depth: usize, act: &M::Act)

Examples found in repository?
crates/competitive/src/data_structure/binary_trie.rs (line 160)
147    pub fn update<R>(&mut self, range: R, act: M::Act)
148    where
149        R: RangeBounds<u64>,
150    {
151        let Some(range) = self.range_to_bounds(range) else {
152            return;
153        };
154        if self.is_empty() {
155            return;
156        }
157
158        let (ql, qr) = range;
159        if ql == 0 && qr == self.max_key {
160            self.apply_at(0, self.bit_len, &act);
161            return;
162        }
163
164        let mut l = ql;
165        loop {
166            let depth = (l.trailing_zeros() as usize)
167                .min(self.bit_len)
168                .min(63 - (qr - l + 1).leading_zeros() as usize);
169            let r = l | ((1u64 << depth) - 1);
170
171            let mut node = 0;
172            for d in (depth..self.bit_len).rev() {
173                self.push_at(node, d + 1);
174                node = self.nodes[node].child[(((l ^ self.xor_mask) >> d) & 1) as usize];
175                if node == usize::MAX {
176                    break;
177                }
178            }
179            if node != usize::MAX {
180                self.apply_at(node, depth, &act);
181                self.recalc_up(node);
182            }
183            if r == qr {
184                break;
185            }
186            l = r + 1;
187        }
188    }
189
190    pub fn fold<R>(&mut self, range: R) -> M::Agg
191    where
192        R: RangeBounds<u64>,
193    {
194        let Some(range) = self.range_to_bounds(range) else {
195            return M::agg_unit();
196        };
197
198        let (ql, qr) = range;
199        if ql == 0 && qr == self.max_key {
200            return self.nodes[0].agg.clone();
201        }
202
203        let mut res = M::agg_unit();
204        let mut l = ql;
205        loop {
206            let depth = (l.trailing_zeros() as usize)
207                .min(self.bit_len)
208                .min(63 - (qr - l + 1).leading_zeros() as usize);
209            let r = l | ((1u64 << depth) - 1);
210
211            let mut node = 0;
212            for d in (depth..self.bit_len).rev() {
213                self.push_at(node, d + 1);
214                node = self.nodes[node].child[(((l ^ self.xor_mask) >> d) & 1) as usize];
215                if node == usize::MAX {
216                    break;
217                }
218            }
219            if node != usize::MAX {
220                res = M::agg_operate(&res, &self.nodes[node].agg);
221            }
222            if r == qr {
223                break;
224            }
225            l = r + 1;
226        }
227        res
228    }
229
230    fn apply_at(&mut self, node: usize, depth: usize, act: &M::Act) {
231        if M::is_act_unit(act) {
232            return;
233        }
234        if let Some(agg) = M::act_agg(&self.nodes[node].agg, act) {
235            self.nodes[node].agg = agg;
236            if depth > 0 {
237                M::act_operate_assign(&mut self.nodes[node].lazy, act);
238            }
239        } else if depth == 0 {
240            panic!("act failed on leaf");
241        } else {
242            self.push_at(node, depth);
243            for child in self.nodes[node].child {
244                if child != usize::MAX {
245                    self.apply_at(child, depth - 1, act);
246                }
247            }
248            self.recalc_at(node);
249        }
250    }
251
252    fn push_at(&mut self, node: usize, depth: usize) {
253        let act = replace(&mut self.nodes[node].lazy, M::act_unit());
254        if M::is_act_unit(&act) {
255            return;
256        }
257        let child = self.nodes[node].child;
258        for child in child {
259            if child != usize::MAX {
260                self.apply_at(child, depth - 1, &act);
261            }
262        }
263    }
Source

fn push_at(&mut self, node: usize, depth: usize)

Examples found in repository?
crates/competitive/src/data_structure/binary_trie.rs (line 105)
91    pub fn modify_or_insert(&mut self, key: u64, f: impl FnOnce(&mut M::Agg)) {
92        assert!(key <= self.max_key);
93        if self.bit_len == 0 {
94            if self.is_empty() {
95                self.len = 1;
96            }
97            f(&mut self.nodes[0].agg);
98            return;
99        }
100
101        let key = key ^ self.xor_mask;
102        let mut inserted = false;
103        let mut node = 0;
104        for d in (0..self.bit_len).rev() {
105            self.push_at(node, d + 1);
106            let bit = ((key >> d) & 1) as usize;
107            if self.nodes[node].child[bit] == usize::MAX {
108                inserted = true;
109                let next = self.nodes.len();
110                self.nodes[node].child[bit] = next;
111                self.nodes.push(Node::new(node));
112            }
113            node = self.nodes[node].child[bit];
114        }
115
116        if inserted {
117            self.len += 1;
118        }
119        self.nodes[node].lazy = M::act_unit();
120        f(&mut self.nodes[node].agg);
121        self.recalc_up(node);
122    }
123
124    pub fn get(&mut self, key: u64) -> Option<M::Agg> {
125        assert!(key <= self.max_key);
126        if self.is_empty() {
127            return None;
128        }
129        if self.bit_len == 0 {
130            return Some(self.nodes[0].agg.clone());
131        }
132
133        let key = key ^ self.xor_mask;
134        let mut node = 0;
135        for d in (0..self.bit_len).rev() {
136            let bit = ((key >> d) & 1) as usize;
137            let next = self.nodes[node].child[bit];
138            if next == usize::MAX {
139                return None;
140            }
141            self.push_at(node, d + 1);
142            node = next;
143        }
144        Some(self.nodes[node].agg.clone())
145    }
146
147    pub fn update<R>(&mut self, range: R, act: M::Act)
148    where
149        R: RangeBounds<u64>,
150    {
151        let Some(range) = self.range_to_bounds(range) else {
152            return;
153        };
154        if self.is_empty() {
155            return;
156        }
157
158        let (ql, qr) = range;
159        if ql == 0 && qr == self.max_key {
160            self.apply_at(0, self.bit_len, &act);
161            return;
162        }
163
164        let mut l = ql;
165        loop {
166            let depth = (l.trailing_zeros() as usize)
167                .min(self.bit_len)
168                .min(63 - (qr - l + 1).leading_zeros() as usize);
169            let r = l | ((1u64 << depth) - 1);
170
171            let mut node = 0;
172            for d in (depth..self.bit_len).rev() {
173                self.push_at(node, d + 1);
174                node = self.nodes[node].child[(((l ^ self.xor_mask) >> d) & 1) as usize];
175                if node == usize::MAX {
176                    break;
177                }
178            }
179            if node != usize::MAX {
180                self.apply_at(node, depth, &act);
181                self.recalc_up(node);
182            }
183            if r == qr {
184                break;
185            }
186            l = r + 1;
187        }
188    }
189
190    pub fn fold<R>(&mut self, range: R) -> M::Agg
191    where
192        R: RangeBounds<u64>,
193    {
194        let Some(range) = self.range_to_bounds(range) else {
195            return M::agg_unit();
196        };
197
198        let (ql, qr) = range;
199        if ql == 0 && qr == self.max_key {
200            return self.nodes[0].agg.clone();
201        }
202
203        let mut res = M::agg_unit();
204        let mut l = ql;
205        loop {
206            let depth = (l.trailing_zeros() as usize)
207                .min(self.bit_len)
208                .min(63 - (qr - l + 1).leading_zeros() as usize);
209            let r = l | ((1u64 << depth) - 1);
210
211            let mut node = 0;
212            for d in (depth..self.bit_len).rev() {
213                self.push_at(node, d + 1);
214                node = self.nodes[node].child[(((l ^ self.xor_mask) >> d) & 1) as usize];
215                if node == usize::MAX {
216                    break;
217                }
218            }
219            if node != usize::MAX {
220                res = M::agg_operate(&res, &self.nodes[node].agg);
221            }
222            if r == qr {
223                break;
224            }
225            l = r + 1;
226        }
227        res
228    }
229
230    fn apply_at(&mut self, node: usize, depth: usize, act: &M::Act) {
231        if M::is_act_unit(act) {
232            return;
233        }
234        if let Some(agg) = M::act_agg(&self.nodes[node].agg, act) {
235            self.nodes[node].agg = agg;
236            if depth > 0 {
237                M::act_operate_assign(&mut self.nodes[node].lazy, act);
238            }
239        } else if depth == 0 {
240            panic!("act failed on leaf");
241        } else {
242            self.push_at(node, depth);
243            for child in self.nodes[node].child {
244                if child != usize::MAX {
245                    self.apply_at(child, depth - 1, act);
246                }
247            }
248            self.recalc_at(node);
249        }
250    }
Source

fn recalc_at(&mut self, node: usize)

Examples found in repository?
crates/competitive/src/data_structure/binary_trie.rs (line 248)
230    fn apply_at(&mut self, node: usize, depth: usize, act: &M::Act) {
231        if M::is_act_unit(act) {
232            return;
233        }
234        if let Some(agg) = M::act_agg(&self.nodes[node].agg, act) {
235            self.nodes[node].agg = agg;
236            if depth > 0 {
237                M::act_operate_assign(&mut self.nodes[node].lazy, act);
238            }
239        } else if depth == 0 {
240            panic!("act failed on leaf");
241        } else {
242            self.push_at(node, depth);
243            for child in self.nodes[node].child {
244                if child != usize::MAX {
245                    self.apply_at(child, depth - 1, act);
246                }
247            }
248            self.recalc_at(node);
249        }
250    }
251
252    fn push_at(&mut self, node: usize, depth: usize) {
253        let act = replace(&mut self.nodes[node].lazy, M::act_unit());
254        if M::is_act_unit(&act) {
255            return;
256        }
257        let child = self.nodes[node].child;
258        for child in child {
259            if child != usize::MAX {
260                self.apply_at(child, depth - 1, &act);
261            }
262        }
263    }
264
265    fn recalc_at(&mut self, node: usize) {
266        let mut agg = M::agg_unit();
267        for child in self.nodes[node].child {
268            if child != usize::MAX {
269                agg = M::agg_operate(&agg, &self.nodes[child].agg);
270            }
271        }
272        self.nodes[node].agg = agg;
273    }
274
275    fn recalc_up(&mut self, mut node: usize) {
276        while self.nodes[node].parent != usize::MAX {
277            node = self.nodes[node].parent;
278            self.recalc_at(node);
279        }
280    }
Source

fn recalc_up(&mut self, node: usize)

Examples found in repository?
crates/competitive/src/data_structure/binary_trie.rs (line 121)
91    pub fn modify_or_insert(&mut self, key: u64, f: impl FnOnce(&mut M::Agg)) {
92        assert!(key <= self.max_key);
93        if self.bit_len == 0 {
94            if self.is_empty() {
95                self.len = 1;
96            }
97            f(&mut self.nodes[0].agg);
98            return;
99        }
100
101        let key = key ^ self.xor_mask;
102        let mut inserted = false;
103        let mut node = 0;
104        for d in (0..self.bit_len).rev() {
105            self.push_at(node, d + 1);
106            let bit = ((key >> d) & 1) as usize;
107            if self.nodes[node].child[bit] == usize::MAX {
108                inserted = true;
109                let next = self.nodes.len();
110                self.nodes[node].child[bit] = next;
111                self.nodes.push(Node::new(node));
112            }
113            node = self.nodes[node].child[bit];
114        }
115
116        if inserted {
117            self.len += 1;
118        }
119        self.nodes[node].lazy = M::act_unit();
120        f(&mut self.nodes[node].agg);
121        self.recalc_up(node);
122    }
123
124    pub fn get(&mut self, key: u64) -> Option<M::Agg> {
125        assert!(key <= self.max_key);
126        if self.is_empty() {
127            return None;
128        }
129        if self.bit_len == 0 {
130            return Some(self.nodes[0].agg.clone());
131        }
132
133        let key = key ^ self.xor_mask;
134        let mut node = 0;
135        for d in (0..self.bit_len).rev() {
136            let bit = ((key >> d) & 1) as usize;
137            let next = self.nodes[node].child[bit];
138            if next == usize::MAX {
139                return None;
140            }
141            self.push_at(node, d + 1);
142            node = next;
143        }
144        Some(self.nodes[node].agg.clone())
145    }
146
147    pub fn update<R>(&mut self, range: R, act: M::Act)
148    where
149        R: RangeBounds<u64>,
150    {
151        let Some(range) = self.range_to_bounds(range) else {
152            return;
153        };
154        if self.is_empty() {
155            return;
156        }
157
158        let (ql, qr) = range;
159        if ql == 0 && qr == self.max_key {
160            self.apply_at(0, self.bit_len, &act);
161            return;
162        }
163
164        let mut l = ql;
165        loop {
166            let depth = (l.trailing_zeros() as usize)
167                .min(self.bit_len)
168                .min(63 - (qr - l + 1).leading_zeros() as usize);
169            let r = l | ((1u64 << depth) - 1);
170
171            let mut node = 0;
172            for d in (depth..self.bit_len).rev() {
173                self.push_at(node, d + 1);
174                node = self.nodes[node].child[(((l ^ self.xor_mask) >> d) & 1) as usize];
175                if node == usize::MAX {
176                    break;
177                }
178            }
179            if node != usize::MAX {
180                self.apply_at(node, depth, &act);
181                self.recalc_up(node);
182            }
183            if r == qr {
184                break;
185            }
186            l = r + 1;
187        }
188    }
Source

fn range_to_bounds<R>(&self, range: R) -> Option<(u64, u64)>
where R: RangeBounds<u64>,

Examples found in repository?
crates/competitive/src/data_structure/binary_trie.rs (line 151)
147    pub fn update<R>(&mut self, range: R, act: M::Act)
148    where
149        R: RangeBounds<u64>,
150    {
151        let Some(range) = self.range_to_bounds(range) else {
152            return;
153        };
154        if self.is_empty() {
155            return;
156        }
157
158        let (ql, qr) = range;
159        if ql == 0 && qr == self.max_key {
160            self.apply_at(0, self.bit_len, &act);
161            return;
162        }
163
164        let mut l = ql;
165        loop {
166            let depth = (l.trailing_zeros() as usize)
167                .min(self.bit_len)
168                .min(63 - (qr - l + 1).leading_zeros() as usize);
169            let r = l | ((1u64 << depth) - 1);
170
171            let mut node = 0;
172            for d in (depth..self.bit_len).rev() {
173                self.push_at(node, d + 1);
174                node = self.nodes[node].child[(((l ^ self.xor_mask) >> d) & 1) as usize];
175                if node == usize::MAX {
176                    break;
177                }
178            }
179            if node != usize::MAX {
180                self.apply_at(node, depth, &act);
181                self.recalc_up(node);
182            }
183            if r == qr {
184                break;
185            }
186            l = r + 1;
187        }
188    }
189
190    pub fn fold<R>(&mut self, range: R) -> M::Agg
191    where
192        R: RangeBounds<u64>,
193    {
194        let Some(range) = self.range_to_bounds(range) else {
195            return M::agg_unit();
196        };
197
198        let (ql, qr) = range;
199        if ql == 0 && qr == self.max_key {
200            return self.nodes[0].agg.clone();
201        }
202
203        let mut res = M::agg_unit();
204        let mut l = ql;
205        loop {
206            let depth = (l.trailing_zeros() as usize)
207                .min(self.bit_len)
208                .min(63 - (qr - l + 1).leading_zeros() as usize);
209            let r = l | ((1u64 << depth) - 1);
210
211            let mut node = 0;
212            for d in (depth..self.bit_len).rev() {
213                self.push_at(node, d + 1);
214                node = self.nodes[node].child[(((l ^ self.xor_mask) >> d) & 1) as usize];
215                if node == usize::MAX {
216                    break;
217                }
218            }
219            if node != usize::MAX {
220                res = M::agg_operate(&res, &self.nodes[node].agg);
221            }
222            if r == qr {
223                break;
224            }
225            l = r + 1;
226        }
227        res
228    }
Source§

impl<M> BinaryTrie<M>
where M: LazyMapMonoid, M::AggMonoid: AbelianMonoid,

Source

pub fn xor_all(&mut self, mask: u64)

Auto Trait Implementations§

§

impl<M> Freeze for BinaryTrie<M>
where Vec<Node<M>>: Freeze,

§

impl<M> RefUnwindSafe for BinaryTrie<M>
where Vec<Node<M>>: RefUnwindSafe,

§

impl<M> Send for BinaryTrie<M>
where Vec<Node<M>>: Send,

§

impl<M> Sync for BinaryTrie<M>
where Vec<Node<M>>: Sync,

§

impl<M> Unpin for BinaryTrie<M>
where Vec<Node<M>>: Unpin,

§

impl<M> UnsafeUnpin for BinaryTrie<M>
where Vec<Node<M>>: UnsafeUnpin,

§

impl<M> UnwindSafe for BinaryTrie<M>
where Vec<Node<M>>: UnwindSafe,

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> ToArrayVecScalar for T

Source§

fn to_array_vec_scalar(self) -> ArrayVecScalar<T>

Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = !

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, !>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.