- 分享
ST表类-工程模板
- 2021-10-16 22:03:36 @
template<typename T>
class STtable {
vector<size_t> Log2;
vector<vector<T>> values;
size_t maxn;
bool build = false;
function<T(const T&, const T&)> fun;
function<T(const T&, const T&)> default_max = [](const T&a, const T&b)->T { return a >= b ? a : b;};
function<T(const T&, const T&)> default_min = [](const T&a, const T&b)->T { return b >= a ? a : b;};
public:
STtable(
size_t maxn,
function<T(const T&, const T&)> _fun = function<T(const T&, const T&)>(),
bool is_max = true
) : Log2(maxn + 1), maxn(maxn) {
Log2[1] = 0;
Log2[2] = 1;
for (size_t i = 3; i <= maxn; i++) {
Log2[i] = Log2[i / 2] + 1;
}
values.resize(Log2[maxn] + 1, vector<T>(maxn + 1));
if (_fun) {
fun = _fun;
} else {
fun = (is_max ? default_max : default_min);
}
}
inline size_t logn() {
return Log2.back();
}
inline size_t size() {
return maxn;
}
T& operator()(const size_t& k) {
return values[0][k];
}
T operator()(const size_t& i, const size_t& j) {
if (!build) {
for (size_t jj = 1; jj <= logn(); ++jj) {
for (size_t ii = 1; ii + (1 << jj) - 1 <= size(); ++ii) {
values[jj][ii] = fun(values[jj - 1][ii], values[jj - 1][ii + (1 << (jj - 1))]);
}
}
build = true;
}
size_t s = Log2[j - i + 1];
return fun(values[s][i], values[s][j - (1 << s) + 1]);
}
};
3 comments
-
神奈猫猫头 fafa SU @ 2021-10-16 23:25:28
朋友们,我做的对吗
-
2021-10-16 23:00:03@
-
2021-10-16 22:14:05@
- 1