<commit_before>//! Associative Range Query Tree based on [Al.Cash's compact representation]
//! (http://codeforces.com/blog/entry/18051).

/// Colloquially known as a "segtree" in the sport programming literature, it
/// represents a sequence of elements a_i (0 <= i < size) from a monoid (M, +)
/// on which we want to support fast range operations:
///
/// - modify(l, r, f) replaces a_i (l <= i <= r) by f(a_i) for an endomorphism f
/// - query(l, r) returns the aggregate a_l + a_{l+1} + ... + a_r
pub struct ArqTree<T: ArqSpec> {
    d: Vec<Option<T::F>>,
    t: Vec<T::M>,
}

impl<T: ArqSpec> ArqTree<T>
where
    T::F: Clone,
{
    /// Initializes a static balanced tree on top of the given sequence.
    pub fn new(mut init: Vec<T::M>) -> Self {
        let size = init.len();
        let mut t = (0..size).map(|_| T::identity()).collect::<Vec<_>>();
        t.append(&mut init);
        for i in (0..size).rev() {
            t[i] = T::op(&t[i << 1], &t[i << 1 | 1]);
        }
        Self {
            d: vec![None; size],
            t: t,
        }
    }

    fn apply(&mut self, p: usize, f: &T::F) {
        self.t[p] = T::apply(f, &self.t[p]);
        if p < self.d.len() {
            let h = match self.d[p] {
                Some(ref g) => T::compose(f, g),
                None => f.clone(),
            };
            self.d[p] = Some(h);
        }
    }

    fn push(&mut self, p: usize) {
        for s in (1..32).rev() {
            let i = p >> s;
            if let Some(ref f) = self.d[i].take() {
                self.apply(i << 1, f);
                self.apply(i << 1 | 1, f);
            }
        }
    }

    fn pull(&mut self, mut p: usize) {
        while p > 1 {
            p >>= 1;
            if self.d[p].is_none() {
                self.t[p] = T::op(&self.t[p << 1], &self.t[p << 1 | 1]);
            }
        }
    }

    /// Applies the endomorphism f to all entries from l to r, inclusive.
    pub fn modify(&mut self, mut l: usize, mut r: usize, f: &T::F) {
        l += self.d.len();
        r += self.d.len();
        let (l0, r0) = (l, r);
        self.push(l0);
        self.push(r0);
        while l <= r {
            if l & 1 == 1 {
                self.apply(l, f);
                l += 1;
            }
            if r & 1 == 0 {
                self.apply(r, f);
                r -= 1;
            }
            l >>= 1;
            r >>= 1;
        }
        self.pull(l0);
        self.pull(r0);
    }

    /// Returns the aggregate range query on all entries from l to r, inclusive.
    pub fn query(&mut self, mut l: usize, mut r: usize) -> T::M {
        l += self.d.len();
        r += self.d.len();
        self.push(l);
        self.push(r);
        let (mut l_agg, mut r_agg) = (T::identity(), T::identity());
        while l <= r {
            if l & 1 == 1 {
                l_agg = T::op(&l_agg, &self.t[l]);
                l += 1;
            }
            if r & 1 == 0 {
                r_agg = T::op(&self.t[r], &r_agg);
                r -= 1;
            }
            l >>= 1;
            r >>= 1;
        }
        T::op(&l_agg, &r_agg)
    }
}

pub trait ArqSpec {
    type F;
    type M;
    /// Require for all f,g,a: apply(compose(f, g), a) = apply(f, apply(g, a))
    fn compose(f: &Self::F, g: &Self::F) -> Self::F;
    /// Require for all f,a,b: apply(f, op(a, b)) = op(apply(f, a), apply(f, b))
    fn apply(f: &Self::F, a: &Self::M) -> Self::M;
    /// Require for all a,b,c: op(a, op(b, c)) = op(op(a, b), c)<commit_msg>ArqTree panic documentation<commit_after>//! Associative Range Query Tree based on [Al.Cash's compact representation]
//! (http://codeforces.com/blog/entry/18051).

/// Colloquially known as a "segtree" in the sport programming literature, it
/// represents a sequence of elements a_i (0 <= i < size) from a monoid (M, +)
/// on which we want to support fast range operations:
///
/// - modify(l, r, f) replaces a_i (l <= i <= r) by f(a_i) for an endomorphism f
/// - query(l, r) returns the aggregate a_l + a_{l+1} + ... + a_r
pub struct ArqTree<T: ArqSpec> {
    d: Vec<Option<T::F>>,
    t: Vec<T::M>,
}

impl<T: ArqSpec> ArqTree<T>
where
    T::F: Clone,
{
    /// Initializes a static balanced tree on top of the given sequence.
    pub fn new(mut init: Vec<T::M>) -> Self {
        let size = init.len();
        let mut t = (0..size).map(|_| T::identity()).collect::<Vec<_>>();
        t.append(&mut init);
        for i in (0..size).rev() {
            t[i] = T::op(&t[i << 1], &t[i << 1 | 1]);
        }
        Self {
            d: vec![None; size],
            t: t,
        }
    }

    fn apply(&mut self, p: usize, f: &T::F) {
        self.t[p] = T::apply(f, &self.t[p]);
        if p < self.d.len() {
            let h = match self.d[p] {
                Some(ref g) => T::compose(f, g),
                None => f.clone(),
            };
            self.d[p] = Some(h);
        }
    }

    fn push(&mut self, p: usize) {
        for s in (1..32).rev() {
            let i = p >> s;
            if let Some(ref f) = self.d[i].take() {
                self.apply(i << 1, f);
                self.apply(i << 1 | 1, f);
            }
        }
    }

    fn pull(&mut self, mut p: usize) {
        while p > 1 {
            p >>= 1;
            if self.d[p].is_none() {
                self.t[p] = T::op(&self.t[p << 1], &self.t[p << 1 | 1]);
            }
        }
    }

    /// Applies the endomorphism f to all entries from l to r, inclusive.
    ///
    /// # Panics
    ///
    /// Panics if l or r is out of range.
    pub fn modify(&mut self, mut l: usize, mut r: usize, f: &T::F) {
        l += self.d.len();
        r += self.d.len();
        let (l0, r0) = (l, r);
        self.push(l0);
        self.push(r0);
        while l <= r {
            if l & 1 == 1 {
                self.apply(l, f);
                l += 1;
            }
            if r & 1 == 0 {
                self.apply(r, f);
                r -= 1;
            }
            l >>= 1;
            r >>= 1;
        }
        self.pull(l0);
        self.pull(r0);
    }

    /// Returns the aggregate range query on all entries from l to r, inclusive.
    ///
    /// # Panics
    ///
    /// Panics if l or r is out of range.
    pub fn query(&mut self, mut l: usize, mut r: usize) -> T::M {
        l += self.d.len();
        r += self.d.len();
        self.push(l);
        self.push(r);
        let (mut l_agg, mut r_agg) = (T::identity(), T::identity());
        while l <= r {
            if l & 1 == 1 {
                l_agg = T::op(&l_agg, &self.t[l]);
                l += 1;
            }
            if r & 1 == 0 {
                r_agg = T::op(&self.t[r], &r_agg);
                r -= 1;
            }
            l >>= 1;
            r >>= 1;
        }
        T::op(&l_agg, &r_agg)
    }
}

pub trait ArqSpec {
    type F;
    type M;
    /// Require for all f,g,a: apply(compose(f, g), a) = apply(f, apply(g, a))
    fn compose(f: &Self::F, g: &Self::F) -> Self::F;
    /// Require for all f,a,b: apply(f, op(a, b)) = op(apply(f, a), apply(f, b))
    fn apply(f: &Self::F, a: &Self::M) -> Self::M;
    /// Require for all a,b,c: op(a, op(b, c)) = op(op(a, b), c)
{'fraction_non_alphanumeric': 0.18680400890868598, 'fraction_numerical': 0.01252783964365256, 'mean_word_length': 1.4006014032743068, 'pattern_counts': {'":': 0, '<': 59, '<?xml version=': 0, '>': 59, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4177421', 'n_tokens_mistral': 2695, 'n_tokens_neox': 2595, 'n_words': 753}