线段树优化建图

线段树优化建图

神奇数据结构QwQ
本蒟蒻学习的时候在网上找到了一堆讲解
但是都没有图片讲解 于是写下了这一篇有精美图片的随笔

1. 概念

1.1.本质

本质就是用两颗线段树优化建图（节省空间）
1.2.作用

看标题可以知道 这东西其实就是一个辅助（优化）我们建图的东西
可以辅助（优化）我们干些什么：

• 点向区间连边
  
• 区间向点连边
  
• 区间向区间连边
  

2.实现

2.1.口胡（实则不然）

（为什么要优化？）
如果我们要将图上的\([l_1,r_1]\)区间向\([l_2,r_2]\)区间中的每一个点连一条边
那么这一个小操作需要连\((r_1-l_1+1)*(r_2-l_2+1)\)条边，如果有一个\(l\),\(r\)区间很大的操作我们就寄寄了，光是存边就可能会炸掉
（用虚点行吗？）
考虑：使用虚点（就是一个我们强行加进去的一个原图上不存在的点）
把\([l_1,r_1]\)中的每一个点向虚点连一条边，然后虚点向\([l_2,r_2]\)中每一个点连一条边
<blockquote>
os:我的图片好精美
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

这个好，看起来很实用