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