线段树优化建图

1. 概念1.1.本质本质就是用两颗线段树优化建图节省空间1.2.作用看标题可以知道 这东西其实就是一个辅助优化我们建图的东西可以辅助优化我们干些什么点向区间连边区间向点连边区间向区间连边2.实现2.1.口胡实则不然为什么要优化如果我们要将图上的[1,1]区间向[2,2]区间中的每一个点连一条边那么这一个小操作需要连(1−11)∗(2−21)条边如果有一个,区间很大的操作我们就寄寄了光是存边就可能会炸掉用虚点行吗考虑使用虚点就是一个我们强行加进去的一个原图上不存在的点把[1,1]中的每一个点向虚点连一条边然后虚点向[2,2]中每一个点连一条边os:我的图片好精美这个网站太好用了 https://app.diagrams.net/这样我们就成功地把(1−11)∗(2−21)条边缩减到了(1−11)(2−21)条边但是如果有个操作我们就又寄寄了怎么办回归到今天的知识点梳理一下现在的信息我们每一次需要把一堆点连到一个点上 然后把一个点向一堆点连线我们看第二个点像什么东西呢 为了方便实现区间操作自然地想到了线段树怎么用还是先看第二个问题把一个点向一堆点连线那么我们直接在原图基础上在旁边加一颗线段树并把要连的点连到对应的线段树的点上1−[2,4]这样我们不管连多大的区间最多也就只需要连级别的边数第二个问题是解决了那第一个问题呢?第二个问题实现的是点到区间的映射第一个问题实现的是区间到点的映射这两个刚好反过来了于是我们考虑把线段树倒过来本来是父亲指向儿子我们把它变成儿子指向父亲这样从[1,2]的一条出边从[1,2]向其他点连的边就可以使[1,2]整个区间内的点都连出去了画一下这样就成功实现了为了方便表示我们把第一个图中的树叫做出树第二个图的叫做入树这里就理解成父节点连的是出边还是入边就好不然容易被绕晕2.2.代码实现2.2.1.建树(build)在建树的时候记得边权全部赋0具体可根据题意调整struct Edge{ int to,w;//id 花费 };vectorEdge e[N];//邻接链表 inline void add_edge(int u,int v,int w){//u-v e[u].push_back({v,w}); } inline void build_out(int o,int l,int r){//建出树 if(lr)return ol,void(); /* if(lr)return ol,void(); 相当于 if(lr){ ol; return; } */ onode_tot; int mid(lr)1; build_out(lc[o],l,mid),build_out(rc[o],mid1,r); add_edge(o,lc[o],0),add_edge(o,rc[o],0); } inline void build_in(int o,int l,int r){//建入树 if(lr)return ol,void(); onode_tot; int mid(lr)1; build_in(lc[o],l,mid),build_in(rc[o],mid1,r); add_edge(lc[o],o,0),add_edge(rc[o],o,0); }2.2.2.连边(update)inline void update_out(int o,int l,int r,int L,int R,int u,int w){//u-[L,R]连边 权值为w if(LlrR)return add_edge(u,o,w),void(); int mid(lr)1; if(Lmid)update_out(lc[o],l,mid,L,R,u,w); if(Rmid)update_out(rc[o],mid1,r,L,R,u,w); } inline void update_in(int o,int l,int r,int L,int R,int u,int w){//[L,R]-u连边 取值为w if(LlrR)return add_edge(o,u,w),void(); int mid(lr)1; if(Lmid)update_in(lc[o],l,mid,L,R,u,w); if(Rmid)update_in(rc[o],mid1,r,L,R,u,w); }3.例题CF786B LegacyCFluogu给定 个节点参数 有 次操作给定参数 ,,从 向 连一条权值为 的边。给定参数 ,,,从 向 连 [,] 一条权值为 的边。给定参数 ,,, 从 [,] 向 连一条权值为 的边。求 到每个节点的最短路。1≤,≤105,1≤≤1092256。板子题 把上面的入树出树和原图的个点放在一起建一堆边然后跑Dijikstra即可附上本蒟蒻的丑陋代码#includebits/stdc.h using namespace std; #define int long long const int N4e510; const int INF0x3f3f3f3f3f3f3f3f; int n,s,Q; struct Edge{ int to,w; };vectorEdge e[N]; bool operator(const Edge x,const Edge y){ return x.wy.w; }inline void add_edge(int u,int v,int w){ e[u].push_back({v,w}); } int lc[4*N],rc[4*N]; int node_tot; int root_out; int root_in; int dis[N]; int vis[N]; priority_queueEdge q; inline void build_out(int o,int l,int r){ if(lr)return ol,void(); onode_tot; int mid(lr)1; build_out(lc[o],l,mid),build_out(rc[o],mid1,r); add_edge(o,lc[o],0),add_edge(o,rc[o],0); }inline void build_in(int o,int l,int r){ if(lr){ ol; return; } onode_tot; int mid(lr)1; build_in(lc[o],l,mid); build_in(rc[o],mid1,r); add_edge(lc[o],o,0); add_edge(rc[o],o,0); } inline void update_out(int o,int l,int r,int L,int R,int u,int w){