P13825 【模板】线段树 1.5（指针式动态开点线段树） · znzryb
## 题目大意
# P13825 【模板】线段树 1.5
## 题目描述
如题，已知一个长度为 $n$
的数列 $\{a_i\}$（$1 \leq i \leq n$），初始时 $a$ 序列满足 $a_i = i$。你需要进行下面两种操作：
1. 将某区间每一个数加上 $k$。
1. 求出某区间每一个数的和。
## 输入格式
第一行包含两个整数 $n, m$，分别表示该数列数字的个数和操作的总个数。
接下来 $m$ 行每行包含 $3$ 或 $4$ 个整数，表示一个操作，具体如下：
1. `1 l r k`：将区间 $[l,r]$ 内每个数加上 $k$。
1. `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$。
## 思路讲解
```cpp
/*
* 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](https://www.luogu.com.cn/record/266006147)
::: 源代码
```cpp
/**
* 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……）
不要忘记初始化这个根节点。
