一种基于指针+new实现动态开点的线段树模板

#include<iostream>

using namespace std;

int num[100000000];

struct node
{
    //左右子树节点
    node* child_l = NULL;
    node* child_r = NULL;
    //当前节点区间范围
    int l = 0, r = 0;
    //懒标记
    long long lzy = 0;
    //节点值
    long long val = 0;
};

void push_down(node* root)
{
    //如果到达叶节点或者没有标记没必要进行下放操作直接返回
    if (root->child_l == root->child_r || root->lzy == 0) return;
    //更新左右子树的值
    root->child_l->val = root->child_l->val + root->lzy * (root->child_l->r - root->child_l->l + 1);
    root->child_r->val = root->child_r->val + root->lzy * (root->child_r->r - root->child_r->l + 1);
    //懒标记下放
    root->child_l->lzy = root->child_l->lzy + root->lzy;
    root->child_r->lzy = root->child_r->lzy + root->lzy;
    //下放后将当前节点懒标记置0
    root->lzy = 0;
}

long long build(node* root, int num[])
{
    //如果到达叶节点进行赋值
    if (root->l == root->r)
    {
        root->val = num[root->l];
        return root->val;
    }
    int ln = root->l;
    int rn = root->r;
    int mid = (ln + rn) / 2;
    //建立左子树
    root->child_l = new node; root->child_l->l =   ln  , root->child_l->r = mid, root->child_l->val = build(root->child_l, num);
    //建立右子树
    root->child_r = new node; root->child_r->l = mid + 1, root->child_r->r = rn, root->child_r->val = build(root->child_r, num);
    //更新当前节点值
    root->val = root->child_l->val + root->child_r->val;
    return root->val;
}

void add(node* root, int l, int r, int val)
{
    //如果当前区间是目标区间的子集直接进行下方标记
    if (root->l >= l && root->r <= r)
    {
        root->val = root->val + val * (root->r - root->l + 1);
        root->lzy = root->lzy + val;
        return;
    }
    //下放标记
    push_down(root);
    //如果左右子树与目标区间有交集，查找该子树
    int mid = (root->r + root->l) / 2;
    if (l <= mid) add(root->child_l, l, r, val);
    if (r >= mid + 1) add(root->child_r, l, r, val);
    //更新根节点权值
    root->val = root->child_l->val + root->child_r->val;
}

long long find(node* root, int l, int r)
{
    //与add同理
    if (root->l >= l && root->r <= r) return root->val;
    push_down(root); long long re = 0;
    int mid = (root->r + root->l) / 2;
    if (l <= mid) re += find(root->child_l, l, r);
    if (r >= mid + 1) re += find(root->child_r, l, r);
    return re;
}

int main()
{
    int n, q; cin >> n >> q;
    node* G = new node;
    G->l = 1, G->r = n;
    for (int i = 1; i <= n; i++)
        cin >> num[i];
    build(G, num);
    for (int i = 1; i <= q; i++)
    {
        int x, y, v, b; cin >> x;
        if (x == 1) cin >> y >> v >> b, add(G, y, v, b);
        else cin >> y >> v, cout << find(G, y, v) << endl;
    }

}