Segment Tree - セグメント木
(Library/DataStructure/SegmentTree.hpp)

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

Segment Tree - セグメント木

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

数列 $A$ の要素はモノイド $M$ である必要があります。以下、モノイドの単位元を $e$ とします。

Function

Constructor

SegmentTree(
    vector<Monoid> &A,
    F merge,
    const Monoid &e,
    bool zero_index = false
)

• セグメント木を配列 $A$ で初期化します。以降、セグメント木の長さを $N = \lvert A \rvert$ で表します。
• merge には $2$ つのモノイドに対する二項演算 $\oplus : M \times M \rightarrow M$ を渡します。
  • 本ドキュメントでは merge の計算量を定数時間としています。
  • 区間最小値 : [](int x, int y){return min(x, y);}
  • 区間総和 : [](int x, int y){return x + y;}
• 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$ を行う関数
• $e$ は $M$ の単位元

計算量

• $\textrm{O}(N)$

---

Apply

void Apply(int k, Monoid x)

• $A_k$ に対して一点更新クエリを実行します。
• すなわち、$A_k \leftarrow x$ を行います。

制約

• $1 \le k \le N$
• $x \in M$

計算量

• $\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}(1)$

---

Depends on

• Library/Common.hpp

Verified with

• verify/AOJ-DSL-2-A.test.cpp
• verify/AOJ-DSL-2-B.test.cpp
• verify/LC-PointAddRangeSum.test.cpp
• verify/LC-PointSetRangeComposite.test.cpp
• verify/LC-VertexAddPathSum.test.cpp
• verify/LC-VertexAddSubtreeSum.test.cpp
• verify/LC-VertexSetPathComposite.test.cpp

Code

#include "../Common.hpp"

template<typename Monoid>
class SegmentTree{
    public:
    using F = function<Monoid(Monoid, Monoid)>;
    
    SegmentTree(
        vector<Monoid> &A, 
        F merge, 
        const Monoid &e, 
        bool zero_index = false
    ) : f(merge), id_(e), zero_index_(zero_index){
        size_ = 1;
        while(size_ < (int)A.size()) size_ <<= 1;
        offset_ = size_ - 1;
        data_.resize(2 * size_, id_);
        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 k, Monoid x){
        Validate(k + zero_index_);
        k = offset_ + k + zero_index_;
        data_[k] = x;
        while(k >>= 1){
            data_[k] = f(data_[2 * k], data_[2 * k + 1]);
        }
    }

    Monoid Fold(int l, int r){
        if(l == r) return id_;
        Validate(l + zero_index_);
        Validate(r + zero_index_ - 1);
        int lh = l + zero_index_ + offset_, rh = r + zero_index_ + offset_;
        Monoid al = id_, ar = id_;
        while(lh < rh){
            if(lh & 1) al = f(al, data_[lh++]);
            if(rh & 1) ar = f(data_[--rh], ar);
            lh >>= 1, rh >>= 1;
        }
        return f(al, ar);
    }

    Monoid operator[](const int &k){
        Validate(k + zero_index_);
        return data_[offset_ + k + zero_index_];
    }

    private:
    int size_, offset_, zero_index_;
    vector<Monoid> data_;
    const F f;
    const Monoid id_;

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

#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/SegmentTree.hpp"

template<typename Monoid>
class SegmentTree{
    public:
    using F = function<Monoid(Monoid, Monoid)>;
    
    SegmentTree(
        vector<Monoid> &A, 
        F merge, 
        const Monoid &e, 
        bool zero_index = false
    ) : f(merge), id_(e), zero_index_(zero_index){
        size_ = 1;
        while(size_ < (int)A.size()) size_ <<= 1;
        offset_ = size_ - 1;
        data_.resize(2 * size_, id_);
        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 k, Monoid x){
        Validate(k + zero_index_);
        k = offset_ + k + zero_index_;
        data_[k] = x;
        while(k >>= 1){
            data_[k] = f(data_[2 * k], data_[2 * k + 1]);
        }
    }

    Monoid Fold(int l, int r){
        if(l == r) return id_;
        Validate(l + zero_index_);
        Validate(r + zero_index_ - 1);
        int lh = l + zero_index_ + offset_, rh = r + zero_index_ + offset_;
        Monoid al = id_, ar = id_;
        while(lh < rh){
            if(lh & 1) al = f(al, data_[lh++]);
            if(rh & 1) ar = f(data_[--rh], ar);
            lh >>= 1, rh >>= 1;
        }
        return f(al, ar);
    }

    Monoid operator[](const int &k){
        Validate(k + zero_index_);
        return data_[offset_ + k + zero_index_];
    }

    private:
    int size_, offset_, zero_index_;
    vector<Monoid> data_;
    const F f;
    const Monoid id_;

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

Back to top page