mmrz's library

This documentation is automatically generated by online-judge-tools/verification-helper

Project maintained by mm-rz Hosted on GitHub Pages — Theme by mattgraham

セグメント木
(data_structure/segment_tree.hpp)

View this file on GitHub
Last update: 2025-07-01 03:22:56+09:00
Include: #include "data_structure/segment_tree.hpp"

セグメント木

使い方

$N$ を要素数

とする。

また、要素の取り方は 0-indexed であることに注意する。

segment_tree<T>(int N, auto combine, T identify) : 要素数 $N$ のセグメント木を生成する
segment_tree<T>(vector<T> v, auto combine, T identify) : 要素数 $N$ で、 vector<T> v で初期化されたセグメント木を生成する
void set(int x, T val) : $x$ 番目の要素を $val$ に変更する $O(\log(N))$
T fold(int l, int r) : $[l, r)$ を満たす区間内に対する区間演算クエリの結果を返す $O(\log(N))$
seg[x] : $x$ 番目の値を返す。$O(1)$
max_right(f<bool(T)>, int l) : $l \leq i < N$ のうち、各要素に対する条件 $f$ を満たすもののなかで最も最大（ $N-1$ 寄り）のものを返す $O(\log(N))$

!!CAUTION!!

max_right(f<bool(T)>, int l) の検証は atcoder の問題上に手動で提出しており、自動では verify されない

!!!UNVERIFIED!!!

min_left(f<bool(T)>, int r) : $0 \leq i \leq r$ のうち、各要素に対する条件 $f$ を満たすもののなかで最も最小（ $0$ 寄り）のものを返す $O(\log(N))$
T all_fold() : $[0, n)$ を満たす区間内に対する区間演算クエリの結果を返す $O(1)$

概要

内部で完全二分木を 1-indexed で構築している。こちらの方が定数倍がよく、また max_right() なども実装しやすい。

Verified with

Code

#pragma once

#include<cassert>
#include<functional>
#include<vector>

template<typename T>struct segment_tree {
	using F = std::function<T(T, T)>;

	int offset;
	int n;
	std::vector<T> node;
	F combine;
	T identify;

	segment_tree(int _n, F _combine, T _identify) : segment_tree(std::vector<T>(_n, _identify), _combine, _identify) {}

	segment_tree(const std::vector<T> &v, F _combine, T _identify) : n((int)v.size()), combine(_combine), identify(_identify) {
		offset = 1;
		while(offset < n)offset <<= 1;

		node.resize(2*offset, identify);

		for(int i = 0;i < n;i++)node[i + offset] = v[i];
		for(int i = offset - 1;i >= 1;i--)node[i] = combine(node[2 * i + 0], node[2 * i + 1]);
	}

	T operator[](int x) {return node[x + offset]; }

	void set(int x, T val){
		assert(0 <= x && x < n);
		x += offset;

		node[x] = val;
		while(x >>= 1){
			node[x] = combine(node[2 * x + 0], node[2 * x + 1]);
		}
	}

	T fold(int l, int r){
		assert(0 <= l && l <= r && r <= n);
		if(l == r)return identify;

		T L = identify, R = identify;
		for(l += offset, r += offset; l < r;l >>= 1, r >>= 1){
			if(l&1)L = combine(L, node[l++]);
			if(r&1)R = combine(node[--r], R);
		}
		return combine(L, R);
	}

	T all_fold() { return node[1]; };

	int max_right(const std::function<bool(T)> f, int l = 0){
		assert(0 <= l && l <= n);
		assert(f(identify));

		if(l == n)return n;
		
		l += offset;
		T sum = identify;
		do{
			while(l%2 == 0)l >>= 1;
			if(not f(combine(sum, node[l]))){
				while(l < offset){
					l <<= 1;
					if(f(combine(sum, node[l]))){
						sum = combine(sum, node[l]);
						l++;
					}
				}
				return l - offset;
			}
			sum = combine(sum, node[l]);
			l++;
		}while((l&-l) != l);
		return n;
	}

	int min_left(const std::function<bool(T)> f, int r = -1){
		if(r == 0)return 0;
		if(r == -1)r = n;
		r += offset;
		T sum = identify;
		do{
			--r;
			while(r > 1 && (r % 2))r >>= 1;
			if(not f(combine(node[r], sum))){
				while(r < offset){
					r = r*2 + 1;
					if(f(combine(node[r], sum))){
						sum = combine(node[r], sum);
						--r;
					}
				}
				return r+1 - offset;
			}
			sum = combine(node[r], sum);
		}while((r&-r) != r);
		return 0;
	}
};

#line 2 "data_structure/segment_tree.hpp"

#include<cassert>
#include<functional>
#include<vector>

template<typename T>struct segment_tree {
	using F = std::function<T(T, T)>;

	int offset;
	int n;
	std::vector<T> node;
	F combine;
	T identify;

	segment_tree(int _n, F _combine, T _identify) : segment_tree(std::vector<T>(_n, _identify), _combine, _identify) {}

	segment_tree(const std::vector<T> &v, F _combine, T _identify) : n((int)v.size()), combine(_combine), identify(_identify) {
		offset = 1;
		while(offset < n)offset <<= 1;

		node.resize(2*offset, identify);

		for(int i = 0;i < n;i++)node[i + offset] = v[i];
		for(int i = offset - 1;i >= 1;i--)node[i] = combine(node[2 * i + 0], node[2 * i + 1]);
	}

	T operator[](int x) {return node[x + offset]; }

	void set(int x, T val){
		assert(0 <= x && x < n);
		x += offset;

		node[x] = val;
		while(x >>= 1){
			node[x] = combine(node[2 * x + 0], node[2 * x + 1]);
		}
	}

	T fold(int l, int r){
		assert(0 <= l && l <= r && r <= n);
		if(l == r)return identify;

		T L = identify, R = identify;
		for(l += offset, r += offset; l < r;l >>= 1, r >>= 1){
			if(l&1)L = combine(L, node[l++]);
			if(r&1)R = combine(node[--r], R);
		}
		return combine(L, R);
	}

	T all_fold() { return node[1]; };

	int max_right(const std::function<bool(T)> f, int l = 0){
		assert(0 <= l && l <= n);
		assert(f(identify));

		if(l == n)return n;
		
		l += offset;
		T sum = identify;
		do{
			while(l%2 == 0)l >>= 1;
			if(not f(combine(sum, node[l]))){
				while(l < offset){
					l <<= 1;
					if(f(combine(sum, node[l]))){
						sum = combine(sum, node[l]);
						l++;
					}
				}
				return l - offset;
			}
			sum = combine(sum, node[l]);
			l++;
		}while((l&-l) != l);
		return n;
	}

	int min_left(const std::function<bool(T)> f, int r = -1){
		if(r == 0)return 0;
		if(r == -1)r = n;
		r += offset;
		T sum = identify;
		do{
			--r;
			while(r > 1 && (r % 2))r >>= 1;
			if(not f(combine(node[r], sum))){
				while(r < offset){
					r = r*2 + 1;
					if(f(combine(node[r], sum))){
						sum = combine(node[r], sum);
						--r;
					}
				}
				return r+1 - offset;
			}
			sum = combine(node[r], sum);
		}while((r&-r) != r);
		return 0;
	}
};