为什么需要？原因很简单，当需要有大量的边去连时，用线段树优化可以直接用点连向区间，或从区间连向点，或从区间连向区间，如果普通连边，复杂度是不可比拟的。下面简单讲解一下线段树（ST）优化建图。
2讲解 2.1 两棵树线段树优化建图需要两棵树：入树和出树，入树指被点或区间指向的树，连边时从结点或边连向入树，出树指连向点或结点的边的树，连边时连向点或结点。入树之间的边是父亲指向儿子，出树之间的边是儿子指向父亲，如果结点个数为n，我们通常用k表示第一颗线段树，k+4*n表示第二颗线段树，k+8*n表示普通结点（为什么要有普通结点一会说），这样，实际上给每颗线段树都留了4*n个结点。
上面的三张图分别是出树，入树和连结点时的样子。
为什么要这么做，可以这么想，出树保证的是所有的儿子结点都能走到他们父亲结点连向的边，
所有的儿子结点都能被两项他们父亲节点的边走到，所以不难理解为什么出树和入树的父亲结点与儿子结点之间的边这样建。
2.2 建树这个过程其实与我们普通线段树的建法一样，只不过多了一个步骤加边，同时，如果当前结点已经是叶子结点，还需要一步操作，及新建一个绿色结点，把每棵树的子结点向对应绿色结点连一条 无向边，如图（蓝色边）：
代码：
inline void build(ll k,ll l,ll r){ if(l==r){ add(k,l+8*n,0);add(l+8*n,k,0); add(k+4*n,l+8*n,0);add(l+8*n,k+4*n,0); return; } add(k,k*2,0);add(k,k*2+1,0); add(k*2+4*n,k+4*n,0);add(k*2+1+4*n,k+4*n,0); ll mid=l+r>>1; build(k*2,l,mid);build(k*2+1,mid+1,r); }实际上，我们建绿色结点是为了方便我们连点对区间边，比如上图，同时也给了一个点连到区间的例子。所以，如果没有点对区间的连边，这个过程可以省略。（但是为了好理解，博主一般打上）
2.3 邻接表这个地方只放代码，不知道的请参考其他博客
struct edge{ ll next,to,w; inline void intt(ll to_,ll next_,ll w_){ next=next_;to=to_;w=w_; } }; edge li[M];ll head[N],tail; inline void add(ll from,ll to,ll w){ li[++tail].intt(to,head[from],w); head[from]=tail; } 2.4 加边这个地方只讲解点与区间相连，事实上，如果是区间与区间想连的话，可以通过加一个虚拟结点来实现，如下：
注：虚拟结点之间的边带权值，其余边权值为0。
这里的加边和我们对普通线段树的操作大同小异。只需要注意边的方向就行了：
inline void addh(ll k,ll z,ll y,ll pd,ll u,ll w){ ll l=p[k].l,r=p[k].r,mid=l+r>>1; if(l==z&&y==r){ if(!pd) return add(u+8*n,k,w); else return add(k+4*n,u+8*n,w); } if(y<=mid) addh(k*2,z,y,pd,u,w); else if(z>mid) addh(k*2+1,z,y,pd,u,w); else addh(k*2,z,mid,pd,u,w),addh(k*2+1,mid+1,y,pd,u,w); }代码里的pd是用来判断是边连向区间还是从区间连向边。
注：只有线段树上的点连到绿色结点时才带边权，如2.2那个图，只有绿色边带权值。
2.5 跑最短路事实上可以跑dij，如果是只有0边权和1边权建议跑01bfs，因为01bfs的复杂度是\(O(n)\)
现在放01bfs的代码如下，想看dij代码的可以去本博客存的最短路代码中去看:
deque<ll> q;ll d[N]; bool vis[N]; inline void bfs(ll s){ memset(d,INF,sizeof(d)); q.push_front(s);d[s]=0; while(q.size()){ ll top=q.front();q.pop_front(); if(vis[top]) continue; vis[top]=1; for(ll k=head[top];k;k=li[k].next){ ll to=li[k].to; if(vis[to]) continue; if(d[to]>d[top]+li[k].w){ d[to]=d[top]+li[k].w; if(li[k].w) q.push_back(to); else q.push_front(to); } } } }01bfs的思想其实就是贪心，实现方法双端队列，0边权加到队首，1边权加到队尾，这样从队头取结点能保证它经过了较多的0边。其余与普通bfs无异。
2.6注意事项注意在有点到区间连线时才必须要绿色节点，其余情况绿色节点不必要。
在区间与区间连线时我们使用了虚拟节点，事实上直接区间连区间也未尝不可，但是我们习惯上操作还是喜欢用区间连向点，这样只需要写一个函数，方便操作。