Segment Tree
作成日：2019.04.05
最終更新日：2019.04.05
目次
実装
テンプレート引数
T
以下のようなモノイド構造体
struct monoid{
//必要な変数を定義
monoid(){
//単位元
}
void update(...){
//...は適切に埋める(場合によっては引数の異なる複数のupdate関数を用意する)
//引数の示す演算を作用させる
}
void prop(monoid &a){
//モノイドaから遅延伝播を受ける
}
void reset(){
//遅延伝播用の変数に単位元を代入
}
const monoid operator *(const monoid &a) const{
monoid ret;
//モノイドの演算
return ret;
}
};N
要素数の対数、デフォルトで$18$($2^{18} \gt 2\times10^5$)
変数
T x[1<<(N+1)]
各頂点におけるモノイド$T$の値をもつ(この実装ではx[0]は使われない)
プライベート関数
void prop(int a)
頂点$a$の子に遅延させていたものを伝播させる
template<class... Args> void put(int a, int s, int t, int l, int r, Args&... args)
半開区間$[l,r)$にargsの示す演算を作用させる時、半開区間$[s,t)$を表している頂点$a$での処理を行う
T query(int a, int s, int t, int l, int r)
半開区間$[s,t),[l,r)$の共通部分にあるモノイド$T$を累積演算させたものを返す
パブリック関数
コンストラクタ
各頂点を単位元で初期化する
template<class... Args> void put(int l, int r, Args... args)
半開区間$[l,r)$にargsの示す演算を作用させる(argsの展開はモノイド$T$のupdate関数で行われる)
T query(int l, int r)
半開区間$[l,r)$にあるモノイド$T$を累積演算させたものを返す
ソースコード
template<class T, int N = 18> class SegTree{
T x[1<<(N+1)];
void prop(int a){
if(a < (1<<N)){
x[a*2].prop(x[a]);
x[a*2+1].prop(x[a]);
}
x[a].reset();
}
template<class... Args>
void put(int a, int s, int t, int l, int r, Args&... args){
if(t <= l || r <= s) return;
if(l <= s && t <= r){
x[a].update(args...);
return;
}
prop(a);
put(a*2,s,(s+t)/2,l,r,args...);
put(a*2+1,(s+t)/2,t,l,r,args...);
x[a] = x[a*2]*x[a*2+1];
}
T query(int a, int s, int t, int l, int r){
if(t <= l || r <= s) return T();
if(l <= s && t <= r) return x[a];
prop(a);
return query(a*2,s,(s+t)/2,l,r)*query(a*2+1,(s+t)/2,t,l,r);
}
public:
SegTree(){
fill(x,x+(1<<(N+1)),T());
}
template<class... Args>
void put(int l, int r, Args... args){
put(1,0,1<<N,l,r,args...);
}
T query(int l, int r){
return query(1,0,1<<N,l,r);
}
};注意点
$l \geq r$である時、put関数は何もせず、query関数は単位元を返す。
また$l \lt 0, r \gt 2^N$である時、半開区間$[0,2^N)$からはみ出した分は無視される。