Segment Tree

Info

Monoidの区間fold、一点更新が\(O(\log{n})\)でできるデータ構造

Complexity

構築 - \(O(n)\)
1点更新 - \(O(\log{n})\)
1点取得 - \(O(1)\)
区間fold - \(O(\log{n})\)

Interface

SegmentTree<M>(int n) モノイド\(M\)、大きさ\(n\)で初期化する
[int i] \(i\)番目の要素への参照を返す
build() セグ木を構築する
update(int i, M a) \(i\)番目の要素を\(a\)に変更する
fold(int l, int r) 区間\([l,r)\)をfoldした値を返す

Interface(Monoid)

I() 単位元を返す
f(M lhs, M rhs) モノイド間の演算\(f:(M,M)\rightarrow M\)

Code

using lnt=long long;
/* <SegmentTree> */

template<typename M>
struct SegmentTree
{
	const int n;
	std::vector<M> data;
	SegmentTree(int n) : n(n),data(n<<1,M::I()) {}
	M& operator[](int i) { return data[i+n]; } // get / pair with build
	void update(int i, const M& a) { data[i+n]=a; for(i+=n;i>1;i>>=1) data[i>>1]=M::f(data[i],data[i^1]); }
	void build() { for(int i=n-1;i>0;i--) data[i]=M::f(data[i<<1],data[i<<1|1]); }
	M fold(int l, int r) const {
		M L=M::I(),R=M::I();
		for(l+=n,r+=n;l<r;l>>=1,r>>=1) {
			if(l&1) L=M::f(data[l++],L);
			if(r&1) R=M::f(R,data[--r]);
		}
		return M::f(L,R);
	}
};

/* <SegmentTree> */

/* <SegmentTree::Template> */
template<typename T=lnt>
struct Template
{
	T v; bool alive;
	static Template I() { return Template(); }
	Template() : alive(false) {}
	Template(T v) : v(v),alive(true) {}
	static Template f(const Template& lhs, const Template& rhs) {
		if(lhs.alive&&rhs.alive) return Template(lhs.v+rhs.v);
		return (lhs.alive)?lhs:rhs;
	}
	operator T() const { return v; }
};
/* <SegmentTree::Template> */

/* <SegmentTree::RangeSum> */
template<typename T=lnt>
struct RangeSum
{
	T v;
	static RangeSum I() { return RangeSum(0); }
	RangeSum(T v) : v(v) {}
	static RangeSum f(const RangeSum& lhs, const RangeSum& rhs) {
		return lhs+rhs;
	}
	operator T() const { return v; }
};
/* <SegmentTree::RangeSum> */

/* <SegmentTree::RangeMin> */
template<typename T=lnt>
struct RangeMin
{
	T v;
	static RangeMin I() { return RangeMin(std::numeric_limits<T>::max()); }
	RangeMin(T v) : v(v) {}
	static RangeMin f(const RangeMin& lhs, const RangeMin& rhs) {
		return std::min(lhs,rhs);
	}
	operator T() const { return v; }
};
/* <SegmentTree::RangeMin> */

/* <SegmentTree::RangeMax> */
template<typename T=lnt>
struct RangeMax
{
	T v;
	static RangeMax I() { return RangeMax(std::numeric_limits<T>::min()); }
	RangeMax(T v) : v(v) {}
	static RangeMax f(const RangeMax& lhs, const RangeMax& rhs) {
		return std::max(lhs,rhs);
	}
	operator T() const { return v; }
};
/* <SegmentTree::RangeMax> */

/* <SegmentTree::RangeMinIndex> */
template<typename T=lnt>
struct RangeMinIndex
{
	T v; int i;
	static RangeMinIndex I() { return RangeMinIndex(std::numeric_limits<T>::max()); }
	RangeMinIndex(T v, int i=-1) : v(v),i(i) {}
	static RangeMinIndex f(const RangeMinIndex& lhs, const RangeMinIndex& rhs) {
		if(lhs.v<rhs.v) return lhs; else return rhs;
	}
	operator T() const { return v; }
};
/* <SegmentTree::RangeMinIndex> */

Examples

using M=RangeMax<int>;
SegmentTree<M> seg(10);

for(int i=0;i<10;i++) seg[i]=i;
seg.build();

std::cout << seg.fold(2,5) << '\n'; // 4

seg.update(2,seg[2]*100);

std::cout << seg.fold(2,5) << '\n'; // 200