Segment Tree

作成日:2019.04.05
最終更新日:2019.04.05

目次

  1. 概要
  2. 計算量
  3. 実装

実装

テンプレート引数

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)$からはみ出した分は無視される。

目次に戻る

広告

自己紹介

プログラミングとかUTAUとかドット絵とか
詳しくはこちら
twitter

プライバシーポリシー

個人情報利用についてはこちら

お問い合わせ

このページに関するお問い合わせはこちら

競技プログラミングMENU

問題を解くまでの道のり

その他

全体MENU

広告