rangeAddMonoid (区間和モノイド)
(src/utility/monoid/rangeAddMonoid.hpp)

• View this file on GitHub
• Last update: 2023-03-10 16:33:31+09:00
• Include: #include "src/utility/monoid/rangeAddMonoid.hpp"

概要

加法のモノイドを表現した構造体です。RAQで利用できます

作用を表現する構造体でa.value + a.size * hogeとするといい感じになります。

機能

dat

テンプレート引数 T: 型、operator +が定義されているもの

T value: 保持している値

std::size_t size: 保持している区間の長さ

rangeAddMonoid

テンプレート引数 T : datのTに利用される

using valueType = dat<T>

• データ構造で利用するために必要なエイリアス

static constexpr valueType identity

• 単位元、 value = 0、size = 0ULL

static valueType opration(const valueType& a, const valueType& b)

• 加法
• value = a.value + b.value
• size = a.size + b.size

Verified with

• test/lazySegmentTree-AOJ-RAQRSQ.test.cpp
• test/lazySegmentTree-AOJ-RUQRSQ.test.cpp
• test/lazySquareDecomp-AOJ-RAQRSQ.test.cpp
• test/lazySquareDecomp-AOJ-RUQRSQ.test.cpp

Code

#pragma once

#include <cstddef>

namespace zawa {

template <class T>
struct dat {
	T value;
	std::size_t size;
	constexpr dat(const T& value = 0, const std::size_t& size = 0ULL) : value(value), size(size) {}
};

template <class T>
struct rangeAddMonoid {
	using valueType = dat<T>;
	static constexpr valueType identity{};
	static valueType operation(const valueType& a, const valueType& b) {
		return valueType(a.value + b.value, a.size + b.size);
	}
};

} // namespace zawa

#line 2 "src/utility/monoid/rangeAddMonoid.hpp"

#include <cstddef>

namespace zawa {

template <class T>
struct dat {
	T value;
	std::size_t size;
	constexpr dat(const T& value = 0, const std::size_t& size = 0ULL) : value(value), size(size) {}
};

template <class T>
struct rangeAddMonoid {
	using valueType = dat<T>;
	static constexpr valueType identity{};
	static valueType operation(const valueType& a, const valueType& b) {
		return valueType(a.value + b.value, a.size + b.size);
	}
};

} // namespace zawa

Back to top page