关于动态开点和new
  • 板块学术版
  • 楼主wfirstzhang
  • 当前回复4
  • 已保存回复4
  • 发布时间2024/8/4 10:21
  • 上次更新2024/8/4 11:22:26
查看原帖
关于动态开点和new
1312537
wfirstzhang楼主2024/8/4 10:21

线段树动态开点有什么优点?看见一般做法都是有一个函数和一个 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); }
}
2024/8/4 10:21
加载中...