This documentation is automatically generated by online-judge-tools/verification-helper
This project is maintained by tsutaj
// @category セグメント木 (Segment Tree)
// @title セグメント木 (Segment Tree)
// 抽象 SegmentTree (0-indexed・一点更新・区間取得)
template <typename MonoidType>
struct SegmentTree {
using Function = function< MonoidType(MonoidType, MonoidType) >;
// node, identity element
int n;
vector<MonoidType> node;
MonoidType E0;
// update / combine function
Function upd_f, cmb_f;
void build(int m, vector<MonoidType> v = vector<MonoidType>()) {
if(v != vector<MonoidType>()) m = v.size();
n = 1; while(n < m) n *= 2;
node = vector<MonoidType>(2*n-1, E0);
if(v != vector<MonoidType>()) {
for(int i=0; i<m; i++) {
node[n-1+i] = v[i];
}
for(int i=n-2; i>=0; i--) {
node[i] = cmb_f(node[2*i+1], node[2*i+2]);
}
}
}
// initialize
SegmentTree() {}
SegmentTree(int n_, MonoidType E0_,
Function upd_f_, Function cmb_f_,
vector<MonoidType> v = vector<MonoidType>()) :
E0(E0_), upd_f(upd_f_), cmb_f(cmb_f_) {
build(n_, v);
}
// update k-th element (applied value: x)
void update(int k, MonoidType x) {
k += n - 1;
node[k] = upd_f(node[k], x);
while(k > 0) {
k = (k - 1) / 2;
node[k] = cmb_f(node[2*k+1], node[2*k+2]);
}
}
// range query for [a, b)
// 非再帰のアイデア: http://d.hatena.ne.jp/komiyam/20131202/1385992406
MonoidType query(int a, int b) {
MonoidType vl = E0, vr = E0;
for(int l=a+n, r=b+n; l<r; l>>=1, r>>=1) {
if(l & 1) vl = cmb_f(vl, node[(l++)-1]);
if(r & 1) vr = cmb_f(node[(--r)-1], vr);
}
return cmb_f(vl, vr);
}
};
#line 1 "structure/strc_008_abst_segtree.cpp"
// @category セグメント木 (Segment Tree)
// @title セグメント木 (Segment Tree)
// 抽象 SegmentTree (0-indexed・一点更新・区間取得)
template <typename MonoidType>
struct SegmentTree {
using Function = function< MonoidType(MonoidType, MonoidType) >;
// node, identity element
int n;
vector<MonoidType> node;
MonoidType E0;
// update / combine function
Function upd_f, cmb_f;
void build(int m, vector<MonoidType> v = vector<MonoidType>()) {
if(v != vector<MonoidType>()) m = v.size();
n = 1; while(n < m) n *= 2;
node = vector<MonoidType>(2*n-1, E0);
if(v != vector<MonoidType>()) {
for(int i=0; i<m; i++) {
node[n-1+i] = v[i];
}
for(int i=n-2; i>=0; i--) {
node[i] = cmb_f(node[2*i+1], node[2*i+2]);
}
}
}
// initialize
SegmentTree() {}
SegmentTree(int n_, MonoidType E0_,
Function upd_f_, Function cmb_f_,
vector<MonoidType> v = vector<MonoidType>()) :
E0(E0_), upd_f(upd_f_), cmb_f(cmb_f_) {
build(n_, v);
}
// update k-th element (applied value: x)
void update(int k, MonoidType x) {
k += n - 1;
node[k] = upd_f(node[k], x);
while(k > 0) {
k = (k - 1) / 2;
node[k] = cmb_f(node[2*k+1], node[2*k+2]);
}
}
// range query for [a, b)
// 非再帰のアイデア: http://d.hatena.ne.jp/komiyam/20131202/1385992406
MonoidType query(int a, int b) {
MonoidType vl = E0, vr = E0;
for(int l=a+n, r=b+n; l<r; l>>=1, r>>=1) {
if(l & 1) vl = cmb_f(vl, node[(l++)-1]);
if(r & 1) vr = cmb_f(node[(--r)-1], vr);
}
return cmb_f(vl, vr);
}
};