两道相对模板的例题，都是线段树优化建图之后跑最短路。
分几种情况：
- 点向点连边
- 点向区间连边
- 区间向点连边
- 区间向区间连边
显然，如果直接建图，每次能建立 (n^2) 数量级的边，总边数大概是 (O(mn^2))（因为重边会多次计算），空间复杂度不允许。
对于区间问题，我们有神器：线段树。
既然直接连边太麻烦，那么就可以用线段树上的一个节点代表图上的一个区间的点。
不过，在同一棵线段树上维护这些点会很混乱。所以我们考虑用两棵线段树维护分别这些点的出边和入边，称为 出树、入树。
对于出树，每个区间的两个子区间向当前区间连边权为 0 的边（以下简称 0 边）；
对于入树，每个区间向两个子区间连 0 边。
这个是显然的，在小区间和大区间之间穿梭不需要代价。
虽然建两棵线段树，但事实上，入树上的节点 dis 值更改后应该都可以更新出树上的点进一步更新其他节点的 dis 值，所以应该有入树向出树连的 0 边。
而对于叶子节点，还应该有出树向入树连的 0 边（自己到自己的 dis 值为 0）。
处理好细节，代码就是这样：
const int inf=2e6+7;
int n,m,s;
struct edge{
int to;ll val;
edge(int to,ll val):to(to),val(val){}
};
vectore[inf];
void ins(int x,int y,ll z)
{//vector 存图
e[x].push_back(edge(y,z));
}
struct Seg_Tree{
int le,ri;
int id;
}O[inf],I[inf];//out 出树，in 入树
int leafO[inf],leafI[inf],sum;//存放叶子节点
void build(int i,int l,int r)
{
O[i].le=I[i].le=l,O[i].ri=I[i].ri=r;
O[i].id=++sum,I[i].id=++sum;
ins(I[i].id,O[i].id,0);//入树向出树建 0 边
if(l==r)
{//叶子节点
leafO[l]=O[i].id;
leafI[l]=I[i].id;
ins(O[i].id,I[i].id,0);
return;
}
int lc=i<>1;
build(lc,l,mid);
build(rc,mid+1,r);
//出树子区间向当前区间连 0 边
ins(O[lc].id,O[i].id,0);
ins(O[rc].id,O[i].id,0);
//入树当前区间向子区间连 0 边
ins(I[i].id,I[lc].id,0);
ins(I[i].id,I[rc].id,0);
}
作为最简单的一种情况，直接在出树和入树的两个叶子节点之间建边即可。
if(op==1)
{
int u=re(),v=re(),w=re();
ins(leafO[u],leafI[v],w+0ll);
}
在入树上找到对应的区间，然后建边。
void askI(int x,int i,int l,int r,ll k)
{
if(l>1;
if(l
和 2. 差不多，只是换成在出树上找对应区间。
void askO(int i,int l,int r,int x,ll k)
{
if(l>1;
if(l
对于这种情况，并不是对应区间向对应区间全部连边，而是找一个中介点，出树对应区间向中介点连边，中介点向入树对应区间连边。
void askO(int i,int l,int r,int x)
{
if(l>1;
if(l>1;
if(l
最短路
这种题最恶心的地方就是建图，建完图之后跑裸的 dijkstra 就可以了。
当然，最终的答案应该是入树的叶节点的 dis 值。
AC Code:
CF786B
const int inf=2e6+7;
int n,m,s;
struct edge{
int to;ll val;
edge(int to,ll val):to(to),val(val){}
};
vectore[inf];
void ins(int x,int y,ll z)
{
e[x].push_back(edge(y,z));
}
struct Seg_Tree{
int le,ri;
int id;
}O[inf],I[inf];
int leafO[inf],leafI[inf],sum;
void build(int i,int l,int r)
{
O[i].le=I[i].le=l,O[i].ri=I[i].ri=r;
O[i].id=++sum,I[i].id=++sum;
ins(I[i].id,O[i].id,0);
if(l==r)
{
leafO[l]=O[i].id;
leafI[l]=I[i].id;
ins(O[i].id,I[i].id,0);
return;
}
int lc=i<>1;
build(lc,l,mid);
build(rc,mid+1,r);
ins(O[lc].id,O[i].id,0);
ins(O[rc].id,O[i].id,0);
ins(I[i].id,I[lc].id,0);
ins(I[i].id,I[rc].id,0);
}
void askO(int i,int l,int r,int x,ll k)
{
if(l>1;
if(l>1;
if(lb.val;
}
};
priority_queueh;
ll dis[inf];
bool vis[inf];
signed main()
{
n=re();m=re();s=re();
build(1,1,n);
for(int i=1;idis[now]+e[now][i].val)
{
dis[p]=dis[now]+e[now][i].val;
h.push(node(p,dis[p]));
}
}
}
for(int i=1;i
P6348
const int inf=1e7+7;
int n,m,s;
struct edge{
int to,val;
edge(int to,int val):to(to),val(val){}
};
vectore[inf];
void ins(int x,int y,int z)
{
e[x].push_back(edge(y,z));
}
struct Seg_Tree{
int le,ri;
int id;
}O[inf],I[inf];
int leafO[inf],leafI[inf],cnt;
void build(int i,int l,int r)
{
O[i].le=I[i].le=l;O[i].ri=I[i].ri=r;
O[i].id=++cnt;I[i].id=++cnt;
ins(I[i].id,O[i].id,0);
if(l==r)
{
leafO[l]=O[i].id;
leafI[l]=I[i].id;
ins(O[i].id,I[i].id,0);
return;
}
int lc=i<>1;
build(i<>1;
if(l>1;
if(lb.val;
}
};
priority_queueh;
int dis[inf];
bool vis[inf];
int main()
{
n=re();m=re();s=re();
build(1,1,n);
for(int i=1;idis[now]+e[now][i].val)
{
dis[p]=dis[now]+e[now][i].val;
h.push(node(p,dis[p]));
}
}
}
for(int i=1;i>1),putchar('\n');
return 0;
}
当然，线段树优化建图不止用于最短路，多数图论问题都可以利用线段树优化建图。
Original: https://www.cnblogs.com/Zvelig1205/p/16670596.html
Author: Zvelig1205
Title: 线段树优化建图
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/605295/
转载文章受原作者版权保护。转载请注明原作者出处！