前言
来补一下暑期集训的坑。
正文
标记可持久化
这个很好理解，在进行区间修改的时候，不下传懒标记，查询的时候直接对每一层再进行处理即可。
这个主要用于线段树分治，所以理解就行，代码不给了。
动态开点
之前一直不太会，现在来补一下。
这种线段树主要用于优化空间复杂度。就是对于下标，不用常规方法存储节点的左右儿子，而用一个单独的变量 \(tot\) 来存储。
这点大家作为资深 OIER 一定都懂，下面说一下代码方面和普通线段树的区别。
在写函数的时候，需要额外定义当前节点所代表的区间的信息。
本人喜欢用结构体存储，所以需要在结构体里面增加 \(lc,rc\) 代表儿子下标，并且用宏定义优化代码长度。在调用的时候将 \(t_{p*2}\) 改为 \(t_{lc(p)}\) 即可，右儿子同理。
懒标记部分判断一下 \(lc,rc\) 是否被赋值，如果没有让 \(tot++\) 然后再去赋值就行了。
区修部分需要额外开一个变量 \(p\) 来表示当前节点编号，函数里面用实参调用 \(p\)，这样方便对 \(lc,rc\) 进行赋值，其余不变。
查询部分只需要在最开始判断一下当前编号是否已经被赋值，如果没有直接返回。这也是动态开点线段树优化空间的直接表现。
稍微放下洛谷线段树模板一的代码，最开始的时候忘记 \(upd\) 了，查了好久才发现我太菜了。
点击查看代码
#include<bits/stdc++.h>
#define int long long
const int maxn=1e6+10;
using namespace std;
inline int read()
{
int w=1,s=0;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch)){s=s*10+(ch-'0');ch=getchar();}
return w*s;
}
int n,Q,tot,st;
struct no
{
int d,add;
int lc,rc;
#define lc(x) t[x].lc
#define rc(x) t[x].rc
}t[maxn<<2];
void upd(int p)
{
t[p].d=t[lc(p)].d+t[rc(p)].d;
}
void spread(int p,int tl,int tr)
{
if(!t[p].add)return ;
int mid=(tl+tr)>>1;
if(!lc(p))t[p].lc=++tot;
if(!rc(p))t[p].rc=++tot;
t[lc(p)].d+=t[p].add*(mid-tl+1);
t[rc(p)].d+=t[p].add*(tr-mid);
t[lc(p)].add+=t[p].add;
t[rc(p)].add+=t[p].add;
t[p].add=0;
}
void add(int &p,int tl,int tr,int l,int r,int k)
{
if(!p) p=++tot;
if(tl>=l&&tr<=r)
{
t[p].d+=k*(tr-tl+1);
t[p].add+=k;
return ;
}
spread(p,tl,tr);
int mid=(tl+tr)>>1;
if(mid>=l)add(lc(p),tl,mid,l,r,k);
if(mid<r)add(rc(p),mid+1,tr,l,r,k);
upd(p);
}
int ask(int p,int tl,int tr,int l,int r)
{
if(!p)return 0;
if(tl>=l&&tr<=r)return t[p].d;
spread(p,tl,tr);
int mid=(tl+tr)>>1,ma=0;
if(mid>=l)ma+=ask(lc(p),tl,mid,l,r);
if(mid<r)ma+=ask(rc(p),mid+1,tr,l,r);
return ma;
}
signed main()
{
cin>>n>>Q;
for(int i=1;i<=n;i++)
{
int x=read();
add(st,1,n,i,i,x);
}
while(Q--)
{
int opt=read(),l=read(),r=read();
if(opt==1){int k=read();add(st,1,n,l,r,k);}
else printf("%lld\n",ask(st,1,n,l,r));
}
return 0;
}
线段树合并
这个东西找不到模板题目，所以就讲一下部分实现吧。
其实很简单，对两个线段树维护的信息进行合并，需要更新下标和维护内容。
下标的话只需要特判一下是否存在，然后不存在的话新开一个节点就行，维护内容的话就正常处理。
代码很短，不放了。
线段树优化建图
这个比前面的稍微难一点，不过也还行。
放一道模板题。
考虑建图的时候如果需要让一个节点和一个区间内的所有节点连边，那么正常情况下会爆时间。
所以我们把连边操作放到线段树里面。连边时，我们只需要让节点对对应区间连边即可。
但是如果有无向边的话，一颗线段树会乱套，所以我们建两棵线段树，分别存储点连向线段树区间节点和线段树区间结点连向点的边。下文我们称它们分别为入树和出树。
最开始的时候，我们让入树中左右节点连向它的两个儿子，出树则让儿子连向它的父亲节点，都是有向边，边权为 \(0\)。同时让两棵树对应位置的所有叶节点也连上边权为 \(0\) 的无向边，这样两棵线段树就完成了初始化。
对于编号的话，我们让入树的节点编号正常搞，出树则根据数据范围加上一个偏移量 \(k\)。对于所有叶节点，我们用一个数组 \(id\) 表示原数组中的位置在入树中所对应的叶节点编号，然后对于出树，叶节点编号直接就是 \(id_i+k\) 了。
以点连向区间为例，我们让出树中对应的叶节点连向入树中覆盖该区间的节点，借用一下 maoyiting 大佬的图
另一种操作同理。
模板题要求跑单源最短路，那么我们找到起点在出树中所对的编号，然后正常 dijkstra 即可。
点击查看代码
正在写，别急。
主席树
明天再更。
标签：lc,int,线段,扩展,学习,add,rc,节点 From： https://www.cnblogs.com/Lydic/p/18320928