P13825 【模板】线段树 1.5（指针式动态开点线段树）

题目大意

P13825 【模板】线段树 1.5

题目描述

如题，已知一个长度为 $n$

的数列 $\{a_i\}$（$1 \leq i \leq n$），初始时 $a$ 序列满足 $a_i = i$。你需要进行下面两种操作：

1. 将某区间每一个数加上 $k$。

2. 求出某区间每一个数的和。

输入格式

第一行包含两个整数 $n, m$，分别表示该数列数字的个数和操作的总个数。

接下来 $m$ 行每行包含 $3$ 或 $4$ 个整数，表示一个操作，具体如下：

1. 1 l r k：将区间 $[l,r]$ 内每个数加上 $k$。

2. 2 l r：输出区间 $[l,r]$ 内每个数的和。

输出格式

输出包含若干行整数，即为所有操作 2 的结果。

输入输出样例 #1

输入 #1

5 5
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4

输出 #1

9
9
18

说明/提示

对于 $30\%$ 的数据，$n \le 8$，$m \le 10$。

对于 $50\%$ 的数据，$n \le {10}^5$。

对于 $100\%$ 的数据，$1 \le m,k \le {10}^5$，$1 \leq l \leq r \leq n\leq 10^9$。

思路讲解

/* 
 * 2026-03-08  P13825 【模板】线段树 1.5 动态开点线段树
 * AC https://www.luogu.com.cn/record/266006147
 *
 */
struct Tag {
    // 在母串中的这个位置
    ll add=0;
    bool need_apply=false;
    void apply(const Tag &t) {
        add+=t.add;
        need_apply=true;
    }
};

struct Info {
    ll l=0,r=0;
    i128 sum=0;
    static Info merge(const Info &a,const Info &b) {
        Info res=a;
        res.r=b.r;
        res.sum+=b.sum;
        return res;
    }
    void apply(const Tag&t) {
        if (!t.need_apply) {
            return;
        }
        ll len=r-l+1;
        sum+=len*t.add;
    }
};

// 我认为还是用 C++14 的写法，把你要写的东西传进去比较好，不容易写错
template<class I=Info,class T=Tag>
struct SEG {
    // 如果不需要泛型，可以用下面的来替代
    // using I=Info;
    // using T=Tag;
    struct Node {
        I info;
        T tag;
        Node* rs=nullptr;
        Node* ls=nullptr;
    };

    void init_node(Node *u,ll l,ll r) {
        u->info.l=l;
        u->info.r=r;
        u->info.sum=i128(u->info.l+u->info.r)*(u->info.r-u->info.l+1)/2;
    }

    Node* root=nullptr;
    ll N;

    static bool isIntersect(ll l1, ll r1, ll l2, ll r2) {
        if (!(l1 > r2 || r1 < l2)) return true;
        return false;
    }

    SEG(ll N):N(N) {
        root=new Node();
        root->info.l=1;
        root->info.r=N;
        init_node(root,1,N);
    }

    void extend(Node *u) {
        if (u->ls==nullptr) {
            u->ls=new Node();
            init_node(u->ls,u->info.l,(u->info.l+u->info.r)>>1);
        }
        if (u->rs==nullptr) {
            u->rs=new Node();
            init_node(u->rs,((u->info.l+u->info.r)>>1)+1,u->info.r);
        }
    }

    void push(Node *u) {
        if (u->info.l==u->info.r) {
            return;
        }
        extend(u);
        if (u->tag.need_apply) {
            u->ls->info.apply(u->tag);
            u->rs->info.apply(u->tag);
            u->ls->tag.apply(u->tag);
            u->rs->tag.apply(u->tag);
            u->tag={};
        }
    }
    void pull(Node *u) {
        if (u->info.l==u->info.r) {
            return;
        }
        u->info=I::merge(u->ls->info,u->rs->info);
    }
    void modify(Node*u,ll l,ll r,const T& t) {
        if (u->info.l>=l && u->info.r<=r) {
            u->info.apply(t);
            u->tag.apply(t);
            return;
        }
        push(u);
        if (isIntersect(u->ls->info.l,u->ls->info.r,l,r)) {
            modify(u->ls,l,r,t);
        }
        if (isIntersect(u->rs->info.l,u->rs->info.r,l,r)) {
            modify(u->rs,l,r,t);
        }
        pull(u);
    }

    Info query(Node *u,ll l,ll r) {
        if (u->info.l>=l && u->info.r<=r) {
            return u->info;
        }
        Info res;
        bool is_get=false;
        push(u);
        if (isIntersect(u->ls->info.l,u->ls->info.r,l,r)) {
            res=query(u->ls,l,r);
            is_get=true;
        }
        if (isIntersect(u->rs->info.l,u->rs->info.r,l,r)) {
            if (!is_get) {
                res=query(u->rs,l,r);
            }else {
                res=I::merge(res,query(u->rs,l,r));
            }
        }
        return res;
    }
};

AC代码

AC
https://www.luogu.com.cn/record/266006147

源代码

/**
 * Problem: P13825 【模板】线段树 1.5
 * Contest: 
 * Judge: Luogu
 * URL: https://www.luogu.com.cn/problem/P13825
 * Created: 2026-03-08 13:03:42
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */
ostream& operator<<(ostream& os, i128 x) {
    if (x < 0) os << '-', x = -x;
    if (x > 9) os << x / 10;
    return os << (char)('0' + x % 10);
}

struct Tag {
    // 在母串中的这个位置
    ll add=0;
    bool need_apply=false;
    void apply(const Tag &t) {
        add+=t.add;
        need_apply=true;
    }
};

struct Info {
    ll l=0,r=0;
    i128 sum=0;
    static Info merge(const Info &a,const Info &b) {
        Info res=a;
        res.r=b.r;
        res.sum+=b.sum;
        return res;
    }
    void apply(const Tag&t) {
        if (!t.need_apply) {
            return;
        }
        ll len=r-l+1;
        sum+=len*t.add;
    }
};

// 我认为还是用 C++14 的写法，把你要写的东西传进去比较好，不容易写错
template<class I=Info,class T=Tag>
struct SEG {
    struct Node {
        I info;
        T tag;
        Node* rs=nullptr;
        Node* ls=nullptr;
    };

    void init_node(Node *u,ll l,ll r) {
        u->info.l=l;
        u->info.r=r;
        u->info.sum=i128(u->info.l+u->info.r)*(u->info.r-u->info.l+1)/2;
    }

    Node* root=nullptr;
    ll N;

    static bool isIntersect(ll l1, ll r1, ll l2, ll r2) {
        if (!(l1 > r2 || r1 < l2)) return true;
        return false;
    }

    SEG(ll N):N(N) {
        root=new Node();
        root->info.l=1;
        root->info.r=N;
        init_node(root,1,N);
    }

    void extend(Node *u) {
        if (u->ls==nullptr) {
            u->ls=new Node();
            init_node(u->ls,u->info.l,(u->info.l+u->info.r)>>1);
        }
        if (u->rs==nullptr) {
            u->rs=new Node();
            init_node(u->rs,((u->info.l+u->info.r)>>1)+1,u->info.r);
        }
    }

    void push(Node *u) {
        if (u->info.l==u->info.r) {
            return;
        }
        extend(u);
        if (u->tag.need_apply) {
            u->ls->info.apply(u->tag);
            u->rs->info.apply(u->tag);
            u->ls->tag.apply(u->tag);
            u->rs->tag.apply(u->tag);
            u->tag={};
        }
    }
    void pull(Node *u) {
        if (u->info.l==u->info.r) {
            return;
        }
        u->info=I::merge(u->ls->info,u->rs->info);
    }
    void modify(Node*u,ll l,ll r,const T& t) {
        if (u->info.l>=l && u->info.r<=r) {
            u->info.apply(t);
            u->tag.apply(t);
            return;
        }
        push(u);
        if (isIntersect(u->ls->info.l,u->ls->info.r,l,r)) {
            modify(u->ls,l,r,t);
        }
        if (isIntersect(u->rs->info.l,u->rs->info.r,l,r)) {
            modify(u->rs,l,r,t);
        }
        pull(u);
    }

    Info query(Node *u,ll l,ll r) {
        if (u->info.l>=l && u->info.r<=r) {
            return u->info;
        }
        Info res;
        bool is_get=false;
        push(u);
        if (isIntersect(u->ls->info.l,u->ls->info.r,l,r)) {
            res=query(u->ls,l,r);
            is_get=true;
        }
        if (isIntersect(u->rs->info.l,u->rs->info.r,l,r)) {
            if (!is_get) {
                res=query(u->rs,l,r);
            }else {
                res=I::merge(res,query(u->rs,l,r));
            }
        }
        return res;
    }
};

void Solve() {
    ll N,M;
    cin >> N >> M;
    SEG<Info,Tag> seg(N);
    for (int i=1;i<=M;++i) {
        ll op;
        cin>>op;
        if (op==1) {
            ll l,r,k;
            cin>>l>>r>>k;
            seg.modify(seg.root,l,r,{k,true});
        }else {
            ll l,r;
            cin>>l>>r;
            cout<<seg.query(seg.root,l,r).sum<<"\n";
        }
    }
    
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC

*/

心路历程（WA，TLE，MLE……）

不要忘记初始化这个根节点。