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

0-indexedのセグメント木
(data_structure/segment_tree_0-indexed.hpp)

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

0-indexedのセグメント木

使い方

• $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)$

概要

完全二分木は 1-indexed で作った方が何かと便利なため、これは観賞用である（ただ、0-indexedの完全二分木の考え方が本質な問題があったため、こちらも残しておく）。

Verified with

• verify/aoj/dsl/2_A___segment_tree_0-indexed.test.cpp
• verify/aoj/dsl/2_B___segment_tree_0-indexed.test.cpp

Code

#pragma once

#include<functional>
#include<vector>

template<typename T>
struct [[deprecated("use 1-indexed segment tree (segment_tree.hpp)")]] segment_tree {
	using F = std::function<T(T, T)>;

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

	segment_tree(std::vector<T> v, F _combine, T _identity) : combine(_combine), identify(_identity) {
		int sz = (int)v.size();
		n = 1;
		while(n < sz)n *= 2;
		node.resize(2 * n - 1, identify);

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

	segment_tree(int _n, F _combine, T _identify) : combine(_combine), identify(_identify){
		int sz = _n;
		n = 1;
		while(n < sz)n *= 2;
		node.resize(2 * n - 1, identify);
	}

	T operator[](int x) {return node[x + n - 1]; }

	void set(int x, T val){
		x += (n - 1);

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

	T fold(int a, int b, int k = 0, int l = 0, int r = -1){
		if(r < 0) r = n;

		if(r <= a || b <= l)return identify;
		
		if(a <= l && r <= b)return node[k];

		T vl = fold(a, b, 2 * k + 1, l, (l + r) / 2);
		T vr = fold(a, b, 2 * k + 2, (l + r) / 2, r);
		return combine(vl, vr);
	}
};

#line 2 "data_structure/segment_tree_0-indexed.hpp"

#include<functional>
#include<vector>

template<typename T>
struct [[deprecated("use 1-indexed segment tree (segment_tree.hpp)")]] segment_tree {
	using F = std::function<T(T, T)>;

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

	segment_tree(std::vector<T> v, F _combine, T _identity) : combine(_combine), identify(_identity) {
		int sz = (int)v.size();
		n = 1;
		while(n < sz)n *= 2;
		node.resize(2 * n - 1, identify);

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

	segment_tree(int _n, F _combine, T _identify) : combine(_combine), identify(_identify){
		int sz = _n;
		n = 1;
		while(n < sz)n *= 2;
		node.resize(2 * n - 1, identify);
	}

	T operator[](int x) {return node[x + n - 1]; }

	void set(int x, T val){
		x += (n - 1);

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

	T fold(int a, int b, int k = 0, int l = 0, int r = -1){
		if(r < 0) r = n;

		if(r <= a || b <= l)return identify;
		
		if(a <= l && r <= b)return node[k];

		T vl = fold(a, b, 2 * k + 1, l, (l + r) / 2);
		T vr = fold(a, b, 2 * k + 2, (l + r) / 2, r);
		return combine(vl, vr);
	}
};

Back to top page