segtree(セグメント木) (tree/segtree.cpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2023-10-06 03:54:40+09:00

なにこれ

区間取得・一点更新可能な要素数 $n$ のセグメント木．

コンストラクタ

• segtree(n, func, e)：要素数 n のセグメント木を構築する．
• segtree(v, func, e)：配列 v の要素を持つセグメント木を構築する．

func は二項演算の関数，e は単位元．$n \leq 10^8$ 程度．

メンバ関数

• update(idx, val)：idx 番目の要素を val に更新する．
• add(idx, val)：idx 番目の要素を val との二項演算の結果に更新する．
• get(idx)：idx 番目の要素を返す．
• get(L, R)：区間 [L, R) の二項演算の結果を返す．
• get_all()：全区間の二項演算の結果を返す．

idx, L, R は 0-indexed である．

計算量

二項演算の計算量を $O(1)$ と仮定したときの計算量を示す．

• segtree(n, func, e)：$O(n)$
• segtree(v, func, e)：$O(n)$
• update(idx, val)：$O(\log n)$
• add(idx, val)：$O(\log n)$
• get(idx)：$O(1)$
• get(L, R)：$O(\log n)$
• get_all()：$O(1)$

Verified with

• test/aoj_DSL_2_A.cpp
• test/yosupo_static_range_sum.cpp
• test/yosupo_staticrmq.cpp

Code

#pragma once

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

template<typename T, typename F> struct segtree {
private:
	int siz = 1, N;
	vector<T> node;
	const F op;
	const T e_;

public:
	segtree(int n, const F func, const T e) : N(n), op(func), e_(e) {
		while(siz < N) siz <<= 1;
		node.resize(2 * siz - 1, e_);
	}
	segtree(const vector<T> &v, const F func, const T e) : N(v.size()), op(func), e_(e) {
		while(siz < N) siz <<= 1;
		node.resize(2 * siz - 1, e_);
		for(int i = 0; i < N; i++) node[siz - 1 + i] = v[i];
		for(int i = siz - 2; i >= 0; i--) node[i] = op(node[2 * i + 1], node[2 * i + 2]);
	}

	void update(int idx, T val) {
		idx += siz - 1;
		node[idx] = val;

		while(idx > 0) {
			idx = (idx - 1) / 2;
			node[idx] = op(node[2 * idx + 1], node[2 * idx + 2]);
		}
	}

	void add(int idx, T val) {
		idx += siz - 1;
		node[idx] = op(node[idx], val);

		while(idx > 0) {
			idx = (idx - 1) / 2;
			node[idx] = op(node[2 * idx + 1], node[2 * idx + 2]);
		}
	}

	T get(int idx) {
		assert(0 <= idx && idx < N);
		return node[siz - 1 + idx];
	}
	T get(int L, int R) {
		if(L < 0) L = 0;
		if(R > N) R = N;
		assert(L < R);
		return get__(L, R, 0, 0, siz);
	}

private:
	T get__(int L, int R, int id, int l, int r) {
		if(r <= L || R <= l) return e_;
		if(L <= l && r <= R) return node[id];
		T vl = get__(L, R, 2 * id + 1, l, (l + r) / 2);
		T vr = get__(L, R, 2 * id + 2, (l + r) / 2, r);
		return op(vl, vr);
	}

public:
	T get_all() {
		return node[0];
	}
};

#line 2 "tree/segtree.cpp"

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

template<typename T, typename F> struct segtree {
private:
	int siz = 1, N;
	vector<T> node;
	const F op;
	const T e_;

public:
	segtree(int n, const F func, const T e) : N(n), op(func), e_(e) {
		while(siz < N) siz <<= 1;
		node.resize(2 * siz - 1, e_);
	}
	segtree(const vector<T> &v, const F func, const T e) : N(v.size()), op(func), e_(e) {
		while(siz < N) siz <<= 1;
		node.resize(2 * siz - 1, e_);
		for(int i = 0; i < N; i++) node[siz - 1 + i] = v[i];
		for(int i = siz - 2; i >= 0; i--) node[i] = op(node[2 * i + 1], node[2 * i + 2]);
	}

	void update(int idx, T val) {
		idx += siz - 1;
		node[idx] = val;

		while(idx > 0) {
			idx = (idx - 1) / 2;
			node[idx] = op(node[2 * idx + 1], node[2 * idx + 2]);
		}
	}

	void add(int idx, T val) {
		idx += siz - 1;
		node[idx] = op(node[idx], val);

		while(idx > 0) {
			idx = (idx - 1) / 2;
			node[idx] = op(node[2 * idx + 1], node[2 * idx + 2]);
		}
	}

	T get(int idx) {
		assert(0 <= idx && idx < N);
		return node[siz - 1 + idx];
	}
	T get(int L, int R) {
		if(L < 0) L = 0;
		if(R > N) R = N;
		assert(L < R);
		return get__(L, R, 0, 0, siz);
	}

private:
	T get__(int L, int R, int id, int l, int r) {
		if(r <= L || R <= l) return e_;
		if(L <= l && r <= R) return node[id];
		T vl = get__(L, R, 2 * id + 1, l, (l + r) / 2);
		T vr = get__(L, R, 2 * id + 2, (l + r) / 2, r);
		return op(vl, vr);
	}

public:
	T get_all() {
		return node[0];
	}
};

Back to top page