algo — C++23 日本語リファレンス
GitHub

SegmentTree

クラス · セグメント木 (SegmentTree)

template <monoid M>
struct SegmentTree;

概要

セグメント木

計算量

構築・破棄

名前 説明 計算量
(constructor) (1) 空の木を構築する
(2) n要素をeで初期化する
(3) 列vから構築する		 (1) $O(1)$
(2) $O(n)$
(3) $O(n)$

メンバ関数

名前 説明 計算量
assign 確保済み領域を保ったままn要素をeで埋め直す $O(n)$
at k番目の値を返す $O(1)$
get k番目の値を返す $O(1)$
set k番目をvalへ変更する $O(\log n)$
reset k番目を単位元へ戻す $O(\log n)$
all_prod 全要素の積を返す $O(1)$
prod 半開区間[a,b)の積を返す $O(\log n)$
max_right (1) 0から右へ述語fが真である最大境界を返す
(2) lから右へ述語fが真である最大境界を返す		 $O(\log n)$
min_left (1) nから左へ述語fが真である最小境界を返す
(2) rから左へ述語fが真である最小境界を返す		 $O(\log n)$

演算子

名前 説明 計算量
operator[] (1) k番目の値をconst参照で返す
(2) k番目を参照・代入できるproxyを返す		 (1) $O(1)$
(2) 取得は $O(1)$、代入は $O(\log n)$

メンバ型

名前 説明 計算量
Reference k番目の要素として振る舞うproxy。値への変換・代入・chmax / chmin ができる 値の取得は $O(1)$、代入は $O(\log n)$

メンバの詳細

(constructor)

// (1)
SegmentTree();

// (2)
explicit SegmentTree(int _n, T e = M::id());

// (3)
template <class U>
explicit SegmentTree(const std::vector<U> &v);

(1) 空の木を構築する

(2) n要素をeで初期化する

(3) 列vから構築する

max_right

// (1)
template <class F>
int max_right(F f) const;

// (2)
template <class F>
int max_right(int l, F f) const;

(1) 0から右へ述語fが真である最大境界を返す

(2) lから右へ述語fが真である最大境界を返す

min_left

// (1)
template <class F>
int min_left(F f) const;

// (2)
template <class F>
int min_left(int r, F f) const;

(1) nから左へ述語fが真である最小境界を返す

(2) rから左へ述語fが真である最小境界を返す

operator[]

// (1)
const T &operator[](int k) const;

// (2)
Reference operator[](int k);

(1) k番目の値をconst参照で返す

(2) k番目を参照・代入できるproxyを返す

参照