This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ageprocpp/competitive-programming-library
#include "data-structure/SegTree.hpp"
要素の更新と区間への演算の適用を行うデータ構造です。
template <class T, T (*nodef)(const T&, const T&)>
class SegTree;
T
は扱う要素の型、nodef
は要素同士に適用する演算を表します。
SegTree(T e_); // (1)
SegTree(unsigned int m_, T e_); // (2)
SegTree(unsigned int m_, T init, T e_); // (3)
template <class U>
SegTree(const std::vector<U>& initvec, T e_); // (4)
単位元 e_
の Segment Tree を構築します。
長さ m_
、単位元 e_
の Segment Tree を構築し、T()
で初期化します。O(m_) で動作します。
長さ m_
、単位元 e_
の Segment Tree を構築し、init
で初期化します。O(m_) で動作します。
単位元 e_
で初期状態 initvec
をもつ Segment Tree を構築します。m_ を initvec
の長さとして、O(m_) で動作します。
void update(int i, T x);
i 番目の要素を x に変更します。O(logm_) で動作します。
T query(int l, int r) const;
[l,r) に nodef
を作用させた結果を返します。O(logm_) で動作します。
T query_all() const;
全体に nodef
を作用させた結果を返します。O(1) で動作します。
const T& operator[](const int& x) const;
i 番目の要素への const
な参照を返します。O(1) で動作します。
void fill(T x);
全体を x に変更します。O(m_) で動作します。
template <class F>
int max_right(int st, F check) const; // (1)
template <bool (*check)(const T&)>
int max_right(int st) const; // (2)
[st,r) に nodef
を作用させた結果が check
を満たす最小の r を返します。O(logm_) で動作します。
template <class F>
int min_left(int st, F check) const; // (1)
template <bool (*check)(const T&)>
int min_left(int st) const; // (2)
[l,st) に nodef
を作用させた結果が check
を満たす最大の l を返します。O(logm_) で動作します。
template <typename T>
class RSQ : public SegTree<T, RSQ_nodef>;
RSQ_nodef
は加法を表します。
template <typename T, typename U = void>
class RMiQ : public SegTree<T, RMiQ_nodef>; // (1)
template <typename T>
class RMiQ<T, std::enable_if_t<std::numeric_limits<T>::is_specialized, std::nullptr_t>> : public SegTree<T, RMiQ_nodef>; // (2)
RMiQ_nodef
は min
演算を表します。
T
が std::numeric_limits
で特殊化された型の場合、その型の最大値を単位元とします。
template <typename T, typename U = void>
class RMaQ : public SegTree<T, RMaQ_nodef>; // (1)
template <typename T>
class RMaQ<T, std::enable_if_t<std::numeric_limits<T>::is_specialized, std::nullptr_t>> : public SegTree<T, RMaQ_nodef>; // (2)
RMaQ_nodef
は max
演算を表します。
T
が std::numeric_limits
で特殊化された型の場合、その型の最小値を単位元とします。
#pragma once
#include "../basic/template.hpp"
template <class T, T (*nodef)(const T&, const T&)>
class SegTree {
protected:
unsigned int n = 1, m = 1, rank = 0;
std::vector<T> node;
T ident;
public:
SegTree(T e_) : ident(e_) {}
SegTree(unsigned int m_, T e_) : m(m_), ident(e_) {
while (n < m) {
n *= 2;
rank++;
}
node.resize(2 * n, ident);
}
SegTree(unsigned int m_, T init, T e_) : m(m_), ident(e_) {
while (n < m) {
n *= 2;
rank++;
}
node.resize(2 * n, ident);
for (unsigned int i = n; i < 2 * n; i++) node[i] = init;
for (unsigned int i = n - 1; i > 0; i--) node[i] = nodef(node[i << 1], node[i << 1 | 1]);
}
template <class U>
SegTree(const std::vector<U>& initvec, T e_) : ident(e_) {
m = initvec.size();
while (n < m) {
n *= 2;
rank++;
}
node.resize(2 * n, ident);
for (unsigned int i = n; i < 2 * n; i++) {
if (i - n < m) node[i] = initvec[i - n];
}
for (unsigned int i = n - 1; i > 0; i--) node[i] = nodef(node[i << 1], node[i << 1 | 1]);
}
void update(int i, T x) {
i += n;
node[i] = x;
while (i != 1) {
i >>= 1;
node[i] = nodef(node[2 * i], node[2 * i + 1]);
}
}
T query(int l, int r) const {
l += n;
r += n;
T ls = ident, rs = ident;
while (l < r) {
if (l & 1) ls = nodef(ls, node[l++]);
if (r & 1) rs = nodef(node[--r], rs);
l >>= 1;
r >>= 1;
}
return nodef(ls, rs);
}
const T& operator[](const int& i) const { return node[n + i]; }
T query_all() const { return node[1]; }
void fill(T x) {
for (unsigned int i = n; i < 2 * n; i++) node[i] = x;
for (unsigned int i = n - 1; i > 0; i--) node[i] = nodef(node[i << 1], node[i << 1 | 1]);
}
private:
template <class F>
int max_right(int st, F& check, T& acc, int k, int l, int r) const {
if (l + 1 == r) {
acc = nodef(acc, node[k]);
return check(acc) ? m : k - n;
}
int mid = (l + r) >> 1;
if (mid <= st) return max_right(st, check, acc, (k << 1) | 1, mid, r);
if (st <= l && check(nodef(acc, node[k]))) {
acc = nodef(acc, node[k]);
return m;
}
int vl = max_right(st, check, acc, k << 1, l, mid);
if (vl != m) return vl;
return max_right(st, check, acc, (k << 1) | 1, mid, r);
}
template <class F>
int min_left(int st, F& check, T& acc, int k, int l, int r) const {
if (l + 1 == r) {
acc = nodef(node[k], acc);
return check(acc) ? 0 : k - n + 1;
}
int mid = (l + r) >> 1;
if (st <= mid) return min_left(st, check, acc, k << 1, l, mid);
if (r <= st && check(nodef(node[k], acc))) {
acc = nodef(node[k], acc);
return 0;
}
int vr = min_left(st, check, acc, (k << 1) | 1, mid, r);
if (vr != 0) return vr;
return min_left(st, check, acc, k << 1, l, mid);
}
public:
template <class F>
int max_right(int st, F check) const {
T acc = ident;
return max_right(st, check, acc, 1, 0, n);
}
template <bool (*check)(const T&)>
int max_right(int st) const {
T acc = ident;
return max_right(st, check, acc, 1, 0, n);
}
template <class F>
int min_left(int st, F check) const {
T acc = ident;
return min_left(st, check, acc, 1, 0, n);
}
template <bool (*check)(const T&)>
int min_left(int st) const {
T acc = ident;
return min_left(st, check, acc, 1, 0, n);
}
};
namespace {
template <typename T>
T RSQ_nodef(const T& lhs, const T& rhs) {
return lhs + rhs;
}
template <typename T>
T RMiQ_nodef(const T& lhs, const T& rhs) {
return std::min(lhs, rhs);
}
template <typename T>
T RMaQ_nodef(const T& lhs, const T& rhs) {
return std::max(lhs, rhs);
}
} // namespace
template <typename T>
class RSQ : public SegTree<T, RSQ_nodef> {
using Base = SegTree<T, RSQ_nodef>;
public:
template <class... Args>
RSQ(Args&&... args) : Base(std::forward<Args>(args)..., 0) {}
};
template <typename T, typename U = void>
class RMiQ : public SegTree<T, RMiQ_nodef> {
using Base = SegTree<T, RMiQ_nodef>;
public:
template <class... Args>
RMiQ(Args&&... args) : Base(std::forward<Args>(args)...) {}
};
template <typename T>
class RMiQ<T, std::enable_if_t<std::numeric_limits<T>::is_specialized>>
: public SegTree<T, RMiQ_nodef> {
using Base = SegTree<T, RMiQ_nodef>;
public:
template <class... Args>
RMiQ(Args&&... args) : Base(std::forward<Args>(args)..., std::numeric_limits<T>::max()) {}
};
template <typename T, typename U = void>
class RMaQ : public SegTree<T, RMaQ_nodef> {
using Base = SegTree<T, RMaQ_nodef>;
public:
template <class... Args>
RMaQ(Args&&... args) : Base(std::forward<Args>(args)...) {}
};
template <typename T>
class RMaQ<T, std::enable_if_t<std::numeric_limits<T>::is_specialized>>
: public SegTree<T, RMaQ_nodef> {
using Base = SegTree<T, RMaQ_nodef>;
public:
template <class... Args>
RMaQ(Args&&... args) : Base(std::forward<Args>(args)..., std::numeric_limits<T>::min()) {}
};