Segment tree (src/datastructure/segment_tree.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2023-12-14 18:25:11+09:00
• Include: #include "src/datastructure/segment_tree.hpp"

概要

一点更新・区間取得を $O(\log N)$ で行えます。

要求される性質

セグメント木で扱う要素はモノイドである必要があります¹。 モノイドとは、集合 $S$ と二項演算 $\cdot: S \times S \rightarrow S$ が与えられたときに、次の条件を満たすものです。

• 結合律: $(a \cdot b) \cdot c = a \cdot (b \cdot c) \quad (\forall a, b, c \in S)$ を満たす
• 単位元の存在: $e \cdot a = a \cdot e = a \quad (\forall a \in S)$ を満たす $e \in S$ が存在する

1. 実際にはモノイドよりも条件を緩めることができます。 ↩

Required by

• Euler Tour (src/tree/euler_tour.hpp)

Verified with

• test/datastructure/segment_tree/aoj_dsl_2_a.test.cpp
• test/datastructure/segment_tree/aoj_dsl_2_b.test.cpp
• test/datastructure/segment_tree/yosupo_point_set_range_composite.test.cpp
• test/tree/euler_tour/aoj_grl_5_c.test.cpp
• test/tree/euler_tour/aoj_grl_5_d.test.cpp
• test/tree/euler_tour/atcoder_abc294_g.test.cpp
• test/tree/euler_tour/yosupo_vertex_add_path_sum.test.cpp

Code

#ifndef SEGTREE_SEGMENT_TREE_HPP
#define SEGTREE_SEGMENT_TREE_HPP

#include <vector>

template<class T, class F>
class SegmentTree { // 0-indexed
private:
	int n_{};
	std::vector<T> tree;
	F f; // function<T(T, T)>
	T ti;

public:
	SegmentTree(F f, T ti) : f(f), ti(ti) {}

	void init(int n) {
		n_ = 1;
		while (n_ < n) n_ *= 2;
		tree.assign(2 * n_, ti);
	}

	void build(std::vector<T> const &v) {
		int const N = v.size();
		init(N);
		for (int i = 0; i < N; ++i) tree[n_ + i] = v[i];
		for (int i = n_ - 1; i > 0; --i) tree[i] = f(tree[2 * i], tree[2 * i + 1]);
	}

	void update(int i, T const &x) {
		i += n_;
		tree[i] = x;
		while (i >>= 1) tree[i] = f(tree[2 * i], tree[2 * i + 1]);
	}

	T find(int l, int r) { // [l, r)
		l += n_, r += n_;
		T ll = ti, rr = ti;
		while (l < r) {
			if (l & 1) ll = f(ll, tree[l++]);
			if (r & 1) rr = f(tree[--r], rr);
			l >>= 1, r >>= 1;
		}
		return f(ll, rr);
	}

	T at(int i) { return tree[i + n_]; }
};

#endif // SEGTREE_SEGMENT_TREE_HPP

#line 1 "src/datastructure/segment_tree.hpp"



#include <vector>

template<class T, class F>
class SegmentTree { // 0-indexed
private:
	int n_{};
	std::vector<T> tree;
	F f; // function<T(T, T)>
	T ti;

public:
	SegmentTree(F f, T ti) : f(f), ti(ti) {}

	void init(int n) {
		n_ = 1;
		while (n_ < n) n_ *= 2;
		tree.assign(2 * n_, ti);
	}

	void build(std::vector<T> const &v) {
		int const N = v.size();
		init(N);
		for (int i = 0; i < N; ++i) tree[n_ + i] = v[i];
		for (int i = n_ - 1; i > 0; --i) tree[i] = f(tree[2 * i], tree[2 * i + 1]);
	}

	void update(int i, T const &x) {
		i += n_;
		tree[i] = x;
		while (i >>= 1) tree[i] = f(tree[2 * i], tree[2 * i + 1]);
	}

	T find(int l, int r) { // [l, r)
		l += n_, r += n_;
		T ll = ti, rr = ti;
		while (l < r) {
			if (l & 1) ll = f(ll, tree[l++]);
			if (r & 1) rr = f(tree[--r], rr);
			l >>= 1, r >>= 1;
		}
		return f(ll, rr);
	}

	T at(int i) { return tree[i + n_]; }
};

Back to top page