accum1d (累積和)
(src/template/accum1d.hpp)

• View this file on GitHub
• Last update: 2023-01-19 16:06:43+09:00
• Include: #include "src/template/accum1d.hpp"

概要

1次元列の累積和をとります。

詳しくいうと、与えられた列 $A$ に対して、 $\displaystyle S_0\ =\ 0\land S_i\ =\ \sum_{j = 0}^{i - 1} A_j (i > 0)$ を満たす列 $S$ を構築します。

機能

コンストラクタ zawa::accum1d<T>()

• T()1要素のみの列を構築します。
• 累積和そのものを考えると0があったほうがいいかなって。困ったら消す。

zawa::accum1d<T>(const std::vector<T>& A)

• A から $S$ を構築します。
• std::partial_sumを内部で利用しています。

zawa::accum1d<T>(InputIterator begin, InputIterator end)

• beginからendまでの要素からSを構築します。

それぞれ計算量は: $O(\mid A\mid)$

メンバ関数

T sum(std::size_t l, std::size_t r)

• $\displaystyle \sum_{i = l}^{r - i} A_i$ を返す
• $S_r - S_l$ と同義です
• 計算量 : $O(1)$

std::vector<T>を継承しているので、std::vectorの機能がそのまま使えます。

メモ

• 区間で考えると頭が壊れるので、「左端」と「要素数」を利用してsumを呼び出そう。ex) sum(l, l + p)

TODO

• int型の列からlong long型のaccum1dを構築できるようにする

Verified with

• test/ABC267-C.test.cpp
• test/ARC075-E.test.cpp
• test/accum1d.test.cpp
• test/accum1d2.test.cpp

Code

#pragma once

#include <vector>
#include <numeric>

namespace zawa {

template <class T>
struct accum1d : std::vector<T> {
	using vector = std::vector<T>;
	accum1d() {
		(*this).push_back(T());
	}
	accum1d(const std::vector<T>& A) {
		(*this).push_back(T());
		std::partial_sum(A.begin(), A.end(), std::back_inserter(*this));
	}	
	template <class InputIterator>
	accum1d(InputIterator begin, InputIterator end) {
		(*this).push_back(T());
		std::partial_sum(begin, end, std::back_inserter(*this));
	}
	T sum(std::size_t l, std::size_t r) {
		return (*this)[r] - (*this)[l];
	}
};

} // namespace zawa

#line 2 "src/template/accum1d.hpp"

#include <vector>
#include <numeric>

namespace zawa {

template <class T>
struct accum1d : std::vector<T> {
	using vector = std::vector<T>;
	accum1d() {
		(*this).push_back(T());
	}
	accum1d(const std::vector<T>& A) {
		(*this).push_back(T());
		std::partial_sum(A.begin(), A.end(), std::back_inserter(*this));
	}	
	template <class InputIterator>
	accum1d(InputIterator begin, InputIterator end) {
		(*this).push_back(T());
		std::partial_sum(begin, end, std::back_inserter(*this));
	}
	T sum(std::size_t l, std::size_t r) {
		return (*this)[r] - (*this)[l];
	}
};

} // namespace zawa

Back to top page