Lazy Segment Tree
(data_structure/segtree/lazy_segtree.hpp)

View this file on GitHub
Last update: 2025-10-01 15:41:05+09:00
Include: #include "data_structure/segtree/lazy_segtree.hpp"
Link: View error logs on GitHub Actions

Overview

A lazy segment tree is an advanced data structure that extends the functionality of a regular segment tree. It supports both range queries and range updates in logarithmic time. This is achieved by “lazily” propagating updates down the tree, applying them only when necessary.

This implementation is generic and designed to be used with the acted_monoid structures available in the library, which define the data, the actions, and the mapping between them.

Methods

lazy_segment_tree()

Constructs an empty lazy segment tree.

Time complexity: $O(1)$.
explicit lazy_segment_tree(int n)

Constructs a lazy segment tree of size n, initialized with the identity element of the data monoid.

Time complexity: $O(N)$.
explicit lazy_segment_tree(const std::vector<S>& v)

Constructs a lazy segment tree from an initial vector v.

Time complexity: $O(N)$.
void set(int p, S x)

Sets the value at position p (0-indexed) to x.

Time complexity: $O(\log N)$.
S get(int p)

Returns the value at position p (0-indexed).

Time complexity: $O(\log N)$.
S prod(int l, int r)

Calculates the result of the data monoid operation on the range [l, r) (0-indexed, half-open interval).

Time complexity: $O(\log N)$.
S all_prod()

Calculates the result of the data monoid operation on the entire range [0, n).

Time complexity: $O(1)$.
void apply(int p, F f)

Applies the action f to the element at position p (0-indexed).

Time complexity: $O(\log N)$.
void apply(int l, int r, F f)

Applies the action f to all elements in the range [l, r) (0-indexed, half-open interval).

Time complexity: $O(\log N)$.
int max_right(int l, auto g)

Finds the largest r such that l <= r <= n and the predicate g(prod(l, r)) is true. g must be a function that takes a data monoid value and returns a boolean.

Time complexity: $O(\log N)$.
int min_left(int r, auto g)

Finds the smallest l such that 0 <= l <= r and the predicate g(prod(l, r)) is true. g must be a function that takes a data monoid value and returns a boolean.

Time complexity: $O(\log N)$.

Depends on

Verified with

verify/unit_test/lazy_segtree.test.cpp

Code

#ifndef M1UNE_LAZY_SEGTREE_HPP
#define M1UNE_LAZY_SEGTREE_HPP 1

#include <algorithm>
#include <functional>
#include <type_traits>
#include <vector>

#include "monoid/acted_monoid.hpp"
#include "utilities/bit_ceil.hpp"

namespace m1une {

template <ActedMonoid AM>
struct lazy_segment_tree {
    using S = typename AM::data_type;
    using F = typename AM::act_type;

   private:
    int _n;
    int _size;
    int _log;
    std::vector<S> _data;
    std::vector<F> _lazy;

    void update(int k) {
        _data[k] = AM::data_op(_data[2 * k], _data[2 * k + 1]);
    }

    void all_apply(int k, F f) {
        _data[k] = AM::apply(f, _data[k]);
        if (k < _size) {
            _lazy[k] = AM::act_op(_lazy[k], f);
        }
    }

    void push(int k) {
        all_apply(2 * k, _lazy[k]);
        all_apply(2 * k + 1, _lazy[k]);
        _lazy[k] = AM::act_id();
    }

   public:
    lazy_segment_tree() : lazy_segment_tree(0) {}
    explicit lazy_segment_tree(int n) : lazy_segment_tree(std::vector<S>(n, AM::data_id())) {}
    explicit lazy_segment_tree(const std::vector<S>& v) : _n(v.size()) {
        _size = bit_ceil((unsigned int)_n);
        _log = 0;
        while ((1U << _log) < (unsigned int)_size) _log++;
        _data.assign(2 * _size, AM::data_id());
        _lazy.assign(_size, AM::act_id());
        for (int i = 0; i < _n; i++) {
            _data[_size + i] = v[i];
        }
        for (int i = _size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) {
        p += _size;
        for (int i = _log; i >= 1; i--) push(p >> i);
        _data[p] = x;
        for (int i = 1; i <= _log; i++) update(p >> i);
    }

    S get(int p) {
        p += _size;
        for (int i = _log; i >= 1; i--) push(p >> i);
        return _data[p];
    }

    S prod(int l, int r) {
        if (l == r) return AM::data_id();

        l += _size;
        r += _size;

        for (int i = _log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        S sml = AM::data_id(), smr = AM::data_id();
        while (l < r) {
            if (l & 1) sml = AM::data_op(sml, _data[l++]);
            if (r & 1) smr = AM::data_op(_data[--r], smr);
            l >>= 1;
            r >>= 1;
        }

        return AM::data_op(sml, smr);
    }

    S all_prod() {
        return _data[1];
    }

    void apply(int p, F f) {
        p += _size;
        for (int i = _log; i >= 1; i--) push(p >> i);
        _data[p] = AM::apply(f, _data[p]);
        for (int i = 1; i <= _log; i++) update(p >> i);
    }

    void apply(int l, int r, F f) {
        if (l == r) return;

        l += _size;
        r += _size;

        for (int i = _log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        {
            int l2 = l, r2 = r;
            while (l < r) {
                if (l & 1) all_apply(l++, f);
                if (r & 1) all_apply(--r, f);
                l >>= 1;
                r >>= 1;
            }
            l = l2;
            r = r2;
        }

        for (int i = 1; i <= _log; i++) {
            if (((l >> i) << i) != l) update(l >> i);
            if (((r >> i) << i) != r) update((r - 1) >> i);
        }
    }

    int max_right(int l, auto g) {
        if (l == _n) return _n;
        l += _size;
        for (int i = _log; i >= 1; i--) push(l >> i);
        S sm = AM::data_id();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!g(AM::data_op(sm, _data[l]))) {
                while (l < _size) {
                    push(l);
                    l = (2 * l);
                    if (g(AM::data_op(sm, _data[l]))) {
                        sm = AM::data_op(sm, _data[l]);
                        l++;
                    }
                }
                return l - _size;
            }
            sm = AM::data_op(sm, _data[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    int min_left(int r, auto g) {
        if (r == 0) return 0;
        r += _size;
        for (int i = _log; i >= 1; i--) push((r - 1) >> i);
        S sm = AM::data_id();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!g(AM::data_op(_data[r], sm))) {
                while (r < _size) {
                    push(r);
                    r = (2 * r + 1);
                    if (g(AM::data_op(_data[r], sm))) {
                        sm = AM::data_op(_data[r], sm);
                        r--;
                    }
                }
                return r + 1 - _size;
            }
            sm = AM::data_op(_data[r], sm);
        } while ((r & -r) != r);
        return 0;
    }
};

}  // namespace m1une

#endif  // M1UNE_LAZY_SEGTREE_HPP

#line 1 "data_structure/segtree/lazy_segtree.hpp"



#include <algorithm>
#include <functional>
#include <type_traits>
#include <vector>

#line 1 "monoid/acted_monoid.hpp"



#include <concepts>
#line 7 "monoid/acted_monoid.hpp"

#line 1 "monoid/monoid.hpp"



#line 7 "monoid/monoid.hpp"

namespace m1une {

template <typename T, auto operation, auto identity, bool commutative>
struct monoid {
    static_assert(std::is_invocable_r_v<T, decltype(operation), T, T>, "operation must work as T(T, T)");
    static_assert(std::is_invocable_r_v<T, decltype(identity)>, "identity must work as T()");

    using value_type = T;
    static constexpr auto op = operation;
    static constexpr auto id = identity;
    static constexpr bool is_commutative = commutative;
};

template <typename T>
concept Monoid = requires(typename T::value_type v) {
    typename T::value_type;
    { T::op(v, v) } -> std::same_as<typename T::value_type>;
    { T::id() } -> std::same_as<typename T::value_type>;
    { T::is_commutative } -> std::convertible_to<bool>;
};

}  // namespace m1une


#line 9 "monoid/acted_monoid.hpp"

namespace m1une {

template <Monoid Data, Monoid Act, auto mapping>
struct acted_monoid {
    using data_monoid = Data;
    using act_monoid = Act;

    using data_type = typename Data::value_type;
    using act_type = typename Act::value_type;

    static_assert(std::is_invocable_r_v<data_type, decltype(mapping), act_type, data_type>,
                  "mapping must work as data_type(act_type, data_type)");

    static constexpr auto data_op = Data::op;
    static constexpr auto data_id = Data::id;
    static constexpr bool data_is_commutative = Data::is_commutative;
    static constexpr auto act_op = Act::op;
    static constexpr auto act_id = Act::id;
    static constexpr bool act_is_commutative = Act::is_commutative;
    static constexpr auto apply = mapping;
};

template <typename T>
concept ActedMonoid = requires(typename T::data_type d, typename T::act_type a) {
    typename T::data_monoid;
    typename T::act_monoid;
    typename T::data_type;
    typename T::act_type;
    requires Monoid<typename T::data_monoid>;
    requires Monoid<typename T::act_monoid>;
    { T::apply(a, d) } -> std::same_as<typename T::data_type>;
};

}  // namespace m1une


#line 1 "utilities/bit_ceil.hpp"



namespace m1une {
template <typename T>
constexpr T bit_ceil(T n) {
    if (n <= 1) return 1;
    T x = 1;
    while (x < n) x <<= 1;
    return x;
}
}  // namespace m1une


#line 11 "data_structure/segtree/lazy_segtree.hpp"

namespace m1une {

template <ActedMonoid AM>
struct lazy_segment_tree {
    using S = typename AM::data_type;
    using F = typename AM::act_type;

   private:
    int _n;
    int _size;
    int _log;
    std::vector<S> _data;
    std::vector<F> _lazy;

    void update(int k) {
        _data[k] = AM::data_op(_data[2 * k], _data[2 * k + 1]);
    }

    void all_apply(int k, F f) {
        _data[k] = AM::apply(f, _data[k]);
        if (k < _size) {
            _lazy[k] = AM::act_op(_lazy[k], f);
        }
    }

    void push(int k) {
        all_apply(2 * k, _lazy[k]);
        all_apply(2 * k + 1, _lazy[k]);
        _lazy[k] = AM::act_id();
    }

   public:
    lazy_segment_tree() : lazy_segment_tree(0) {}
    explicit lazy_segment_tree(int n) : lazy_segment_tree(std::vector<S>(n, AM::data_id())) {}
    explicit lazy_segment_tree(const std::vector<S>& v) : _n(v.size()) {
        _size = bit_ceil((unsigned int)_n);
        _log = 0;
        while ((1U << _log) < (unsigned int)_size) _log++;
        _data.assign(2 * _size, AM::data_id());
        _lazy.assign(_size, AM::act_id());
        for (int i = 0; i < _n; i++) {
            _data[_size + i] = v[i];
        }
        for (int i = _size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) {
        p += _size;
        for (int i = _log; i >= 1; i--) push(p >> i);
        _data[p] = x;
        for (int i = 1; i <= _log; i++) update(p >> i);
    }

    S get(int p) {
        p += _size;
        for (int i = _log; i >= 1; i--) push(p >> i);
        return _data[p];
    }

    S prod(int l, int r) {
        if (l == r) return AM::data_id();

        l += _size;
        r += _size;

        for (int i = _log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        S sml = AM::data_id(), smr = AM::data_id();
        while (l < r) {
            if (l & 1) sml = AM::data_op(sml, _data[l++]);
            if (r & 1) smr = AM::data_op(_data[--r], smr);
            l >>= 1;
            r >>= 1;
        }

        return AM::data_op(sml, smr);
    }

    S all_prod() {
        return _data[1];
    }

    void apply(int p, F f) {
        p += _size;
        for (int i = _log; i >= 1; i--) push(p >> i);
        _data[p] = AM::apply(f, _data[p]);
        for (int i = 1; i <= _log; i++) update(p >> i);
    }

    void apply(int l, int r, F f) {
        if (l == r) return;

        l += _size;
        r += _size;

        for (int i = _log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        {
            int l2 = l, r2 = r;
            while (l < r) {
                if (l & 1) all_apply(l++, f);
                if (r & 1) all_apply(--r, f);
                l >>= 1;
                r >>= 1;
            }
            l = l2;
            r = r2;
        }

        for (int i = 1; i <= _log; i++) {
            if (((l >> i) << i) != l) update(l >> i);
            if (((r >> i) << i) != r) update((r - 1) >> i);
        }
    }

    int max_right(int l, auto g) {
        if (l == _n) return _n;
        l += _size;
        for (int i = _log; i >= 1; i--) push(l >> i);
        S sm = AM::data_id();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!g(AM::data_op(sm, _data[l]))) {
                while (l < _size) {
                    push(l);
                    l = (2 * l);
                    if (g(AM::data_op(sm, _data[l]))) {
                        sm = AM::data_op(sm, _data[l]);
                        l++;
                    }
                }
                return l - _size;
            }
            sm = AM::data_op(sm, _data[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    int min_left(int r, auto g) {
        if (r == 0) return 0;
        r += _size;
        for (int i = _log; i >= 1; i--) push((r - 1) >> i);
        S sm = AM::data_id();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!g(AM::data_op(_data[r], sm))) {
                while (r < _size) {
                    push(r);
                    r = (2 * r + 1);
                    if (g(AM::data_op(_data[r], sm))) {
                        sm = AM::data_op(_data[r], sm);
                        r--;
                    }
                }
                return r + 1 - _size;
            }
            sm = AM::data_op(_data[r], sm);
        } while ((r & -r) != r);
        return 0;
    }
};

}  // namespace m1une

m1une's library

This documentation is automatically generated by online-judge-tools/verification-helper

Lazy Segment Tree
(data_structure/segtree/lazy_segtree.hpp)

Overview

Methods

Depends on

Verified with

Code

Lazy Segment Tree (data_structure/segtree/lazy_segtree.hpp)

Overview

Methods

Depends on

Verified with

Code

Lazy Segment Tree
(data_structure/segtree/lazy_segtree.hpp)