首页 > 其他分享 >线段树优化建图学习笔记

线段树优化建图学习笔记

时间:2023-01-14 20:45:04浏览次数:36  
标签:连边 单点 线段 笔记 建图 入点 区间 顶点 节点

使用场景:单点向区间,区间向单点或区间向区间建边。
实现原理:用线段树的一个节点管辖一段图上区间的顶点。
实现步骤:

  1. 将原图中的顶点拆点(理论上,实际代码中不需要),出点和入点。
  2. 建立两棵线段树,出点的树和入点的树。
  3. 出点的树由子节点连向父节点,边权为 \(0\),入点的树由父节点向子节点连边,边权为 \(0\)。

使用方法:

  1. 单点 \(x\) 与单点 \(y\) 连边,则用出点的树上编号 \(out_x\) 连向 \(y\) 的入点 \(in_y\)。
  2. 单点 \(x\) 向区间顶点 \([lt,rt]\) 连边,\(out_x\) 向入树的根节点递归连边。
  3. 区间顶点 \([lt,rt]\) 向单点 \(x\) 连边,出树从根节点递归向 \(out_x\) 连边。
  4. 区间顶点 \([lt,rt]\) 向区间 \([lt2,rt2]\) 连边,虚拟一个节点 \(v\),转化为 \(2\) 和 \(3\) 连边。

标签:连边,单点,线段,笔记,建图,入点,区间,顶点,节点
From: https://www.cnblogs.com/Forever1507/p/17052501.html

相关文章

  • Redis 6 学习笔记 3 —— 用SpringBoot整合Redis的踩坑,了解事务、乐观锁、悲观锁
    SpringBoot整合Redis时踩到的坑jdk1.8环境,用idea的SpringInitializr创建springboot项目,版本我选的2.7.6。pom文件添加的依赖如下,仅供参考。注意commons-pool2选错版本......
  • vue-cli笔记
    一、安装全局安装npminstall-g@vue/cli创建项目vuecreate项目名二、目录介绍src--main.js入口文件main.js介绍//引入vueimportVuefrom'vue'/......
  • 《态度-吴军》 读书笔记
    教育首先是关怀备至地、深思熟虑地、小心翼翼地去触及年轻的心灵。——苏霍姆林斯基一、前言《态度》一书为吴军老师给上高中和大学的两个女儿写的四十封家书,针对成长过......
  • linux工具grep的使用心得笔记
    grep作为linux管理中常用的三大工具之一(grep、awk、sed),其功能十分强大,因此难以对其进行全面的使用介绍,因此本文只作为个人学习的笔记之用。 grep的用处:在文本中匹配要......
  • 数论学习笔记
    逆元定义存在$a\timesx\equiv1\pmod{m}$,我们称\(x\)为\(a\)的逆元。完全剩余系假设\(1\toP-1\)都存在逆元,我们则称他为一个完全剩余系。当......
  • Spring 学习笔记
    Spring笔记1.Spring基本概念这里介绍一下,spring的基本概念,简单的说一下ioc是什么,ioc容器是什么,ioc怎么实现的。spring默认是单例的1.1IOCioc是一种思想叫控制反转......
  • MySql学习笔记--进阶05
          ......
  • Android studio学习笔记2
    Androidstudio学习笔记220201303张奕博2023.1.14androidstudio动态调试apk1.配置环境androidstudio需要安装插件:1,Smalidea2,SmaliSupport2.打开APK包注......
  • 数据结构 玩转数据结构 9-1 什么是线段树
    0课程地址https://coding.imooc.com/lesson/207.html#mid=13843 1重点关注1.1线段树解决的问题墙体染色区间查询某区间天空天体数量 1......
  • 环论中中国剩余定理证明笔记
    这一阵在看Maki的《抽象代数I》视频课(https://www.bilibili.com/video/BV1xG411j7Hk),其中第20课讲到环论的中国剩余定理,即:若(R,+,·)是交换环,Ii ◁R,i=1,...,......