线段树动态开点有什么优点?看见一般做法都是有一个函数和一个 top 控制。我写了一个定点 new 运算符的动态开点,有什么不足吗?
template<class Tp>
class Seg_tree {
struct Node {
Tp data, lazy_tag;
long part_left, part_right;
Node *lson, *rson;
constexpr Node(long left, long right)
:part_left(left), part_right(right), lson(nullptr), rson(nullptr)
{}
};
void* const buffer;
void* top;
Node* root;
static bool cover(const Node* parent, long left, long right) {
return left <= parent->part_left && parent->part_right <= right;
}
static void push_up(Node* parent) {
parent->data = parent->lson->data + parent->rson->data;
}
static void add_tag(Node* parent, const Tp& val) {
parent->lazy_tag += val;
parent->data += (parent->part_right - parent->part_left + 1) * val;
}
static void push_down(Node* parent) {
if(!parent->lazy_tag)
return;
add_tag(parent->lson, parent->lazy_tag);
add_tag(parent->rson, parent->lazy_tag);
parent->lazy_tag = 0;
}
void build(Node* parent, const Tp* arr) {
if(parent->part_left == parent->part_right)
{
parent->data = arr[parent->part_left];
return;
}
long mid = parent->part_left + parent->part_right >> 1;
parent->lson = new(top += sizeof(Node))Node(parent->part_left, mid);
build(parent->lson, arr);
parent->rson = new(top += sizeof(Node))Node(mid + 1, parent->part_right);
build(parent->rson, arr);
push_up(parent);
}
void modify_(Node* parent, long left, long right, const Tp& val) {
if(cover(parent, left, right))
{
add_tag(parent, val);
return;
}
push_down(parent);
if(left <= parent->lson->part_right)
modify_(parent->lson, left, right, val);
if(right >= parent->rson->part_left)
modify_(parent->rson, left, right, val);
push_up(parent);
}
Tp query_(Node* parent, long left, long right) {
if(cover(parent, left, right))
return parent->data;
push_down(parent);
Tp res = 0;
if(left <= parent->lson->part_right)
res += query_(parent->lson, left, right);
if(right >= parent->rson->part_left)
res += query_(parent->rson, left, right);
return res;
}
public:
void modify(long left, long right, const Tp& val) { modify_(root, left, right, val); }
Tp range_sum(long left, long right) { return query_(root, left, right); }
Seg_tree(const Tp* arr, std::size_t len)
:buffer(malloc(sizeof(Node) * len * 4)),
top(buffer),
root(new(top)Node(1, len))
{ build(root, arr); }
~Seg_tree() { free(buffer); }
}