前置芝士：线段树动态开点
使用场景：
- 维护区间太大，\(4\times N\) 存不下，通常是值域线段树。
- 维护的区间下标存在负数。
空间复杂度：
- 全部开点，则 \(2\times N -1\)
- 每递归一次，最多开点 \(O(\log N)\)，若调用 \(M\) 次就是 \(M\log N\)。
原理:
- 若一段子区间 \([L,R]\) 对应的线段树节点为 \(cur\)，当不需要递归时，就不建点。
- 当调用
addtag()时，新建节点。
注意事项：
- 没有
build()的过程。都让你动态开点了怎么可能要build()啊喂 - 区间存在负数时，\(mid\) 应是
lt+rt-1>>1而不是lt+rt>>1。（虽然正整数写这个也没关系） addtag()的 \(cur\) 加上取址符。- 根节点占一个，所以总结点数 \(tot\) 的初始值为 \(1\)。
模板代码（P3372）
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100005;
int n,m,tot;
int a[N];
#define lc(x) tree[x].lc
#define rc(x) tree[x].rc
#define sum(x) tree[x].val
#define tag(x) tree[x].tag
struct node{
int val,tag,lc,rc;
}tree[N<<1];
void push_up(int cur){
tree[cur].val=tree[lc(cur)].val+tree[rc(cur)].val;
return;
}
void addtag(int &cur,int lt,int rt,int val){
if(!cur)cur=++tot;
tree[cur].tag+=val;
tree[cur].val+=(rt-lt+1)*val;
return;
}
void push_down(int cur,int lt,int rt){
if(lt>=rt)return;
int mid=(lt+rt-1)>>1;
addtag(lc(cur),lt,mid,tree[cur].tag);
addtag(rc(cur),mid+1,rt,tree[cur].tag);
tree[cur].tag=0;
return;
}
int query(int cur,int lt,int rt,int qx,int qy){
if(lt>qy||rt<qx)return 0;
if(qx<=lt&&qy>=rt)return tree[cur].val;
push_down(cur,lt,rt);
int mid=(lt+rt-1)>>1;
return query(lc(cur),lt,mid,qx,qy)+query(rc(cur),mid+1,rt,qx,qy);
}
void update(int cur,int lt,int rt,int qx,int qy,int val){
if(lt>qy||rt<qx)return;
if(qx<=lt&&qy>=rt){
addtag(cur,lt,rt,val);
return;
}
int mid=(lt+rt-1)>>1;
push_down(cur,lt,rt);
update(lc(cur),lt,mid,qx,qy,val);
update(rc(cur),mid+1,rt,qx,qy,val);
push_up(cur);
return;
}
signed main(){
cin>>n>>m;
tot=1;
for(int i=1;i<=n;i++){
cin>>a[i];
update(1,1,n,i,i,a[i]);
}
for(int i=1;i<=m;i++){
int kind;
cin>>kind;
if(kind==1){
int x,y,k;
cin>>x>>y>>k;
update(1,1,n,x,y,k);
}
else{
int x,y;
cin>>x>>y;
cout<<query(1,1,n,x,y)<<'\n';
}
}
return 0;
}
正题：线段树合并
使用场景:有多棵线段树，维护了相同的区间 \([L,R]\)，通常是权值线段树。每一棵线段树维护了区间内的最大值（区间元素和），\(M\) 次单点修改，每次修改一棵线段树的位置为 \(pos\) 的值，修改后所有线段树对应区间位置的权值相加并维护区间最大值。
板子
int merge(int a,int b,int l,int r){
if(!a||!b)return a+b;
if(l==r){
tree[a].val+=tree[b].val;
tree[a].pos=tree[a].val?l:0;
}
int mid=lt+rt>>1;
lc(a)=merge(lc(a),lc(b),l,mid);
rc(a)=merge(rc(a),rc(b),mid+1,r);
push_up(a,l,r);;
return a;
}