Lazy Segment Tree - 遅延評価セグメント木
(Library/DataStructure/LazySegmentTree.hpp)

• View this file on GitHub
• Last update: 2026-02-12 01:36:24+09:00
• Include: #include "Library/DataStructure/LazySegmentTree.hpp"

Lazy Segment Tree - 遅延評価セグメント木

長さ $N$ の列 $A = (A_1, \dots, A_N)$ に対し、区間更新・区間取得クエリを効率的に行うことができるデータ構造です。

数列 $A$ の要素はモノイド $M$ である必要があり、更新操作もモノイド $O$ である必要があります。以下、モノイドの単位元を $e_M$、操作モノイドの単位元を $e_O$ とします。

Function

Constructor

LazySegmentTree(
    vector<Monoid> &A,
    F merge,
    G mapping,
    H composite,
    const Monoid &e_m,
    const OperatorMonoid &e_o,
    bool zero_index = false
)

• セグメント木を配列 $A$ で初期化します。以降、セグメント木の長さを $N = \lvert A \rvert$ で表します。
• merge には $2$ つのモノイドに対する二項演算 $\oplus : M \times M \rightarrow M$ を渡します。
  • 本ドキュメントでは merge の計算量を定数時間としています。
• mapping には遅延評価を適用する二項演算 $\otimes : M \times O \rightarrow M$ を渡します。
  • 本ドキュメントでは mapping の計算量を定数時間としています。
• composite には遅延評価を合成する二項演算 $\odot : O \times O \rightarrow O$ を渡します。
  • 本ドキュメントでは composite の計算量を定数時間としています。
• e_m にはモノイド $M$ の単位元 $e_M$ を渡します。
• e_o には操作モノイド $O$ の単位元 $e_O$ を渡します。
• zero_index に true を指定すると、セグメント木にアクセスする添え字を 0-index でアクセスすることができます。デフォルトでは 1-index です。
  • 本ドキュメントでは添え字に関する制約は 1-index で示します。

制約

• $1 \le N \le 10^6$
• $A_i \in M$
• merge は二項演算 $\oplus : M \times M \rightarrow M$ を行う関数
• mapping は二項演算 $\otimes : M \times O \rightarrow M$ を行う関数
• composite は二項演算 $\odot : O \times O \rightarrow O$ を行う関数
• $e_M$ は $M$ の単位元
• $e_O$ は $O$ の単位元

計算量

• $\textrm{O}(N)$

---

Apply

void Apply(int l, int r, OperatorMonoid x)

• 半開区間 $[l, r)$ に対して区間更新クエリを実行します。
• すなわち、$l \le i \lt r$ について $A_i \leftarrow A_i \otimes x$ を行います。

制約

• $1 \le l \le N$
• $l \le r \le N + 1$
• $x \in O$

計算量

• $\textrm{O}(\log N)$

---

Fold

Monoid Fold(int l, int r)

• 半開区間 $[l, r)$ に対して区間取得クエリを実行します。
• すなわち、$A_l \oplus A_{l+1} \oplus \dots \oplus A_{r - 1}$ を計算した結果を返します。

制約

• $1 \le l \le N$
• $l \le r \le N + 1$

計算量

• $\textrm{O}(\log N)$

---

operator[]

Monoid operator[](const int &k)

• $A_k$ を取得します。

制約

• $1 \le k \le N$

計算量

• $\textrm{O}(\log N)$

---

Depends on

• Library/Common.hpp

Verified with

• verify/AOJ-DSL-2-G.test.cpp
• verify/LC-RangeAddRangeMin.test.cpp
• verify/LC-RangeAffineRangeSum.test.cpp

Code

#include "../Common.hpp"

template<typename Monoid, typename OperatorMonoid = Monoid>
class LazySegmentTree{
    public:
    using F = function<Monoid(Monoid, Monoid)>;
    using G = function<Monoid(Monoid, OperatorMonoid)>;
    using H = function<OperatorMonoid(OperatorMonoid, OperatorMonoid)>;

    LazySegmentTree(
        vector<Monoid> &A,
        F merge,
        G mapping,
        H composite,
        const Monoid &e_m,
        const OperatorMonoid &e_o,
        bool zero_index = false
    ) : f(merge), g(mapping), h(composite), m1_(e_m), om1_(e_o), zero_index_(zero_index){
        size_ = 1;
        while(size_ < (int)A.size()) size_ <<= 1;
        offset_ = size_ - 1;
        data_.resize(2 * size_, m1_);
        lazy_.resize(2 * size_, om1_);
        is_identity_.resize(2 * size_, true);
        for(int i = 0; i < (int)A.size(); ++i){
            data_[size_ + i] = A[i];
        }
        for(int i = offset_; i >= 1; --i){
            data_[i] = f(data_[i * 2 + 0], data_[i * 2 + 1]);
        }
    }

    void Apply(int l, int r, OperatorMonoid x){
        Validate(l + zero_index_);
        Validate(r + zero_index_ - 1);
        RecursiveApply(l + zero_index_, r + zero_index_, x, 1, size_ + 1, 1);
    }

    Monoid Fold(int l, int r){
        Validate(l + zero_index_);
        Validate(r + zero_index_ - 1);
        return RecursiveFold(l + zero_index_, r + zero_index_, 1, size_ + 1, 1);
    }

    Monoid operator[](const int &k){
        Validate(k + zero_index_);
        return Fold(k, k + 1);
    }

    private:
    int size_, offset_, zero_index_;
    vector<Monoid> data_;
    vector<OperatorMonoid> lazy_;
    vector<bool> is_identity_;
    const F f;
    const G g;
    const H h;
    const Monoid m1_;
    const OperatorMonoid om1_;

    inline void Validate(int x){
        assert(1 <= x && x <= size_);
    }

    void Evaluate(int k){
        if(is_identity_[k]) return;
        if(k < size_){
            lazy_[k * 2 + 0] = h(lazy_[k * 2 + 0], lazy_[k]);
            is_identity_[k * 2 + 0] = false;
            lazy_[k * 2 + 1] = h(lazy_[k * 2 + 1], lazy_[k]);
            is_identity_[k * 2 + 1] = false;
        }
        data_[k] = g(data_[k], lazy_[k]);
        lazy_[k] = om1_;
        is_identity_[k] = true;
    }

    void RecursiveApply(int ul, int ur, OperatorMonoid x, int left, int right, int cell){
        Evaluate(cell);
        if(ul <= left && right <= ur){
            lazy_[cell] = h(lazy_[cell], x);
            is_identity_[cell] = false;
            Evaluate(cell);
        }
        else if(ul < right && left < ur){
            int mid = (left + right) / 2;
            RecursiveApply(ul, ur, x, left, mid, cell * 2 + 0);
            RecursiveApply(ul, ur, x, mid, right, cell * 2 + 1);
            data_[cell] = f(data_[cell * 2 + 0], data_[cell * 2 + 1]);
        }
    }

    Monoid RecursiveFold(int ql, int qr, int left, int right, int cell){
        Evaluate(cell);
        if(qr <= left || right <= ql){
            return m1_;
        }
        if(ql <= left && right <= qr){
            return data_[cell];
        }
        int mid = (left + right) / 2;
        Monoid ans_left = RecursiveFold(ql, qr, left, mid, cell * 2 + 0);
        Monoid ans_right = RecursiveFold(ql, qr, mid, right, cell * 2 + 1);
        return f(ans_left, ans_right);
    }
};

#line 2 "Library/Common.hpp"

/**
 * @file Common.hpp
 */

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cstdint>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

using ll = int64_t;
using ull = uint64_t;

constexpr const ll INF = (1LL << 62) - (3LL << 30) - 1;
#line 2 "Library/DataStructure/LazySegmentTree.hpp"

template<typename Monoid, typename OperatorMonoid = Monoid>
class LazySegmentTree{
    public:
    using F = function<Monoid(Monoid, Monoid)>;
    using G = function<Monoid(Monoid, OperatorMonoid)>;
    using H = function<OperatorMonoid(OperatorMonoid, OperatorMonoid)>;

    LazySegmentTree(
        vector<Monoid> &A,
        F merge,
        G mapping,
        H composite,
        const Monoid &e_m,
        const OperatorMonoid &e_o,
        bool zero_index = false
    ) : f(merge), g(mapping), h(composite), m1_(e_m), om1_(e_o), zero_index_(zero_index){
        size_ = 1;
        while(size_ < (int)A.size()) size_ <<= 1;
        offset_ = size_ - 1;
        data_.resize(2 * size_, m1_);
        lazy_.resize(2 * size_, om1_);
        is_identity_.resize(2 * size_, true);
        for(int i = 0; i < (int)A.size(); ++i){
            data_[size_ + i] = A[i];
        }
        for(int i = offset_; i >= 1; --i){
            data_[i] = f(data_[i * 2 + 0], data_[i * 2 + 1]);
        }
    }

    void Apply(int l, int r, OperatorMonoid x){
        Validate(l + zero_index_);
        Validate(r + zero_index_ - 1);
        RecursiveApply(l + zero_index_, r + zero_index_, x, 1, size_ + 1, 1);
    }

    Monoid Fold(int l, int r){
        Validate(l + zero_index_);
        Validate(r + zero_index_ - 1);
        return RecursiveFold(l + zero_index_, r + zero_index_, 1, size_ + 1, 1);
    }

    Monoid operator[](const int &k){
        Validate(k + zero_index_);
        return Fold(k, k + 1);
    }

    private:
    int size_, offset_, zero_index_;
    vector<Monoid> data_;
    vector<OperatorMonoid> lazy_;
    vector<bool> is_identity_;
    const F f;
    const G g;
    const H h;
    const Monoid m1_;
    const OperatorMonoid om1_;

    inline void Validate(int x){
        assert(1 <= x && x <= size_);
    }

    void Evaluate(int k){
        if(is_identity_[k]) return;
        if(k < size_){
            lazy_[k * 2 + 0] = h(lazy_[k * 2 + 0], lazy_[k]);
            is_identity_[k * 2 + 0] = false;
            lazy_[k * 2 + 1] = h(lazy_[k * 2 + 1], lazy_[k]);
            is_identity_[k * 2 + 1] = false;
        }
        data_[k] = g(data_[k], lazy_[k]);
        lazy_[k] = om1_;
        is_identity_[k] = true;
    }

    void RecursiveApply(int ul, int ur, OperatorMonoid x, int left, int right, int cell){
        Evaluate(cell);
        if(ul <= left && right <= ur){
            lazy_[cell] = h(lazy_[cell], x);
            is_identity_[cell] = false;
            Evaluate(cell);
        }
        else if(ul < right && left < ur){
            int mid = (left + right) / 2;
            RecursiveApply(ul, ur, x, left, mid, cell * 2 + 0);
            RecursiveApply(ul, ur, x, mid, right, cell * 2 + 1);
            data_[cell] = f(data_[cell * 2 + 0], data_[cell * 2 + 1]);
        }
    }

    Monoid RecursiveFold(int ql, int qr, int left, int right, int cell){
        Evaluate(cell);
        if(qr <= left || right <= ql){
            return m1_;
        }
        if(ql <= left && right <= qr){
            return data_[cell];
        }
        int mid = (left + right) / 2;
        Monoid ans_left = RecursiveFold(ql, qr, left, mid, cell * 2 + 0);
        Monoid ans_right = RecursiveFold(ql, qr, mid, right, cell * 2 + 1);
        return f(ans_left, ans_right);
    }
};

Back to top page