スパーステーブル (daylight/structure/sparse_table.hpp)

• View this file on GitHub
• Last update: 2024-12-26 20:32:55+09:00
• Include: #include "daylight/structure/sparse_table.hpp"

Depends on

• 基本テンプレート (daylight/base.hpp)

Verified with

• test/yosupo/structure/staticrmq.2.test.cpp

Code

#include "daylight/base.hpp"

/// @brief スパーステーブル
template<class S>
struct SparseTable {
private:
	vector<vector<S>> V;
	function<S(S, S)> op;
	vi lookup;

public:
	/// @brief 前計算を行う
	/// @param _V 配列の値
	/// @param op 演算を表すラムダ式
	SparseTable(vector<S> _V, function<S(S, S)> op)
		: op(op) {
		int N = SZ(_V);
		int len = 0;
		while((1 << len) <= N) len++;
		V.assign(len, vector<S>(1 << len));
		REP(i, N) {
			V[0][i] = _V[i];
		}
		FOR(i, 1, len) {
			for(int j = 0; j + (1 << i) <= (1 << len);
				j++) {
				V[i][j] = op(V[i - 1][j],
							 V[i - 1][j + (1 << (i - 1))]);
			}
		}
		lookup.resize(N + 1);
		FOR(i, 2, SZ(lookup)) {
			lookup[i] = lookup[i >> 1] + 1;
		}
	}
	/// @brief [l,r)の演算結果を取得する
	/// @param l 区間の左端(inclusive)
	/// @param r 区間の右端(exclusive)
	/// @return 演算結果
	inline S prod(int l, int r) {
		int len = lookup[r - l];
		return op(V[len][l], V[len][r - (1 << len)]);
	}
};

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj_resolve/resolver.py", line 181, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj/verify/languages/cplusplus.py", line 252, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 482, in update
    self.update(
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 477, in update
    raise BundleErrorAt(
competitive_verifier.oj.verify.languages.cplusplus_bundle.BundleErrorAt: daylight/base.hpp: line 103: unable to process #include in #if / #ifdef / #ifndef other than include guards

Back to top page