线段树优化建图
线段树优化建图神奇数据结构QwQ
本蒟蒻学习的时候在网上找到了一堆讲解
但是都没有图片讲解 于是写下了这一篇有精美图片的随笔
1. 概念
1.1.本质
本质就是用两颗线段树优化建图（节省空间）
1.2.作用
看标题可以知道 这东西其实就是一个辅助（优化）我们建图的东西
可以辅助（优化）我们干些什么：
[*]点向区间连边
[*]区间向点连边
[*]区间向区间连边
2.实现
2.1.口胡（实则不然）
（为什么要优化？）
如果我们要将图上的\(\)区间向\(\)区间中的每一个点连一条边
那么这一个小操作需要连\((r_1-l_1+1)*(r_2-l_2+1)\)条边，如果有一个\(l\),\(r\)区间很大的操作我们就寄寄了，光是存边就可能会炸掉
（用虚点行吗？）
考虑：使用虚点（就是一个我们强行加进去的一个原图上不存在的点）
把\(\)中的每一个点向虚点连一条边，然后虚点向\(\)中每一个点连一条边
<blockquote>
os:我的图片好精美
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ yyds。多谢分享 新版吗？好像是停更了吧。 鼓励转贴优秀软件安全工具和文档！ 很好很强大我过来先占个楼 待编辑 谢谢楼主提供！ 感谢分享，学习下。 东西不错很实用谢谢分享
页:
[1]