This documentation is automatically generated by online-judge-tools/verification-helper
This project is maintained by tsutaj
// @category セグメント木 (Segment Tree)
// @title 動的セグメント木 (Dynamic Segment Tree)
// 動的セグメント木 (必要なノードだけ作る)
template <typename MonoidType>
struct SegNode {
MonoidType value;
SegNode *ch[2];
SegNode() {}
SegNode(MonoidType value_) : value(value_) {
ch[0] = ch[1] = nullptr;
}
};
template <typename MonoidType, typename IdxType = int>
struct DynamicSegmentTree {
using Function = function< MonoidType(MonoidType, MonoidType) >;
// node, identity element
IdxType n;
SegNode<MonoidType> *root;
MonoidType E0;
// update / combine function
Function upd_f, cmb_f;
// initialize
DynamicSegmentTree() {
root = new SegNode<MonoidType>;
}
DynamicSegmentTree(IdxType n_, MonoidType E0_,
Function upd_f_, Function cmb_f_) :
E0(E0_), upd_f(upd_f_), cmb_f(cmb_f_) {
root = new SegNode<MonoidType>(E0_);
n = 1; while(n < n_) n *= 2;
}
void update(SegNode<MonoidType> *node, IdxType k, MonoidType x, IdxType l, IdxType r) {
if(r - l == 1) {
node->value = upd_f(node->value, x);
return;
}
IdxType mid = (l + r) / 2;
MonoidType vl = E0, vr = E0;
if(l <= k and k < mid) {
if(!node->ch[0]) node->ch[0] = new SegNode<MonoidType>(E0);
update(node->ch[0], k, x, l, mid);
}
if(mid <= k and k < r) {
if(!node->ch[1]) node->ch[1] = new SegNode<MonoidType>(E0);
update(node->ch[1], k, x, mid, r);
}
vl = (node->ch[0] ? node->ch[0]->value : E0);
vr = (node->ch[1] ? node->ch[1]->value : E0);
node->value = cmb_f(vl, vr);
}
MonoidType query(SegNode<MonoidType> *node, IdxType a, IdxType b, IdxType l, IdxType r) {
if(b <= l or r <= a) return E0;
if(a <= l and r <= b) return node->value;
IdxType mid = (l + r) / 2;
MonoidType vl = (node->ch[0] ? query(node->ch[0], a, b, l, mid) : E0);
MonoidType vr = (node->ch[1] ? query(node->ch[1], a, b, mid, r) : E0);
return cmb_f(vl, vr);
}
// update k-th element (applied value: x)
void update(IdxType k, MonoidType x) {
update(root, k, x, 0, n);
}
// range query for [a, b)
MonoidType query(IdxType a, IdxType b) {
return query(root, a, b, 0, n);
}
};
#line 1 "structure/strc_020_dynamic_segtree.cpp"
// @category セグメント木 (Segment Tree)
// @title 動的セグメント木 (Dynamic Segment Tree)
// 動的セグメント木 (必要なノードだけ作る)
template <typename MonoidType>
struct SegNode {
MonoidType value;
SegNode *ch[2];
SegNode() {}
SegNode(MonoidType value_) : value(value_) {
ch[0] = ch[1] = nullptr;
}
};
template <typename MonoidType, typename IdxType = int>
struct DynamicSegmentTree {
using Function = function< MonoidType(MonoidType, MonoidType) >;
// node, identity element
IdxType n;
SegNode<MonoidType> *root;
MonoidType E0;
// update / combine function
Function upd_f, cmb_f;
// initialize
DynamicSegmentTree() {
root = new SegNode<MonoidType>;
}
DynamicSegmentTree(IdxType n_, MonoidType E0_,
Function upd_f_, Function cmb_f_) :
E0(E0_), upd_f(upd_f_), cmb_f(cmb_f_) {
root = new SegNode<MonoidType>(E0_);
n = 1; while(n < n_) n *= 2;
}
void update(SegNode<MonoidType> *node, IdxType k, MonoidType x, IdxType l, IdxType r) {
if(r - l == 1) {
node->value = upd_f(node->value, x);
return;
}
IdxType mid = (l + r) / 2;
MonoidType vl = E0, vr = E0;
if(l <= k and k < mid) {
if(!node->ch[0]) node->ch[0] = new SegNode<MonoidType>(E0);
update(node->ch[0], k, x, l, mid);
}
if(mid <= k and k < r) {
if(!node->ch[1]) node->ch[1] = new SegNode<MonoidType>(E0);
update(node->ch[1], k, x, mid, r);
}
vl = (node->ch[0] ? node->ch[0]->value : E0);
vr = (node->ch[1] ? node->ch[1]->value : E0);
node->value = cmb_f(vl, vr);
}
MonoidType query(SegNode<MonoidType> *node, IdxType a, IdxType b, IdxType l, IdxType r) {
if(b <= l or r <= a) return E0;
if(a <= l and r <= b) return node->value;
IdxType mid = (l + r) / 2;
MonoidType vl = (node->ch[0] ? query(node->ch[0], a, b, l, mid) : E0);
MonoidType vr = (node->ch[1] ? query(node->ch[1], a, b, mid, r) : E0);
return cmb_f(vl, vr);
}
// update k-th element (applied value: x)
void update(IdxType k, MonoidType x) {
update(root, k, x, 0, n);
}
// range query for [a, b)
MonoidType query(IdxType a, IdxType b) {
return query(root, a, b, 0, n);
}
};