「？」兔说八道

惊堂一拍　话本翻翻　请让小的来讲　莫虚度中元 (?) 夜晚

  总之就是出题的时候得到的一个比较宏大的脑洞.

  众所周知, 有许多算法是基于重标号思想, 把一种不好维护的结构转化为另一种好维护的结构.

  比如重链剖分, 就是树 \(\to\) 序列的转化, 因为序列的 “区间” 是 “好维护的结构”, 所以 “树链” 变得可维护.

  众所又周知, 这种比较狭义的重标号也是很有潜力的. 例如兔的 毛毛虫剖分, 就将树剖的扩展, 通过树 \(\to\) 序列的转化, 将 “毛毛虫” 转化为 “(不交) 区间并”, 出色地实现了维护功能.

  众所还周知, 并不是只有树可以拿来重标号. 甚至一般图也可以. 出于某些原因 (钱还没恰), 所以这里不提.

  但是, 为什么一定要 \(\to\) 序列呢? 形式化地描述重标号, 对于一个图 \(G=(V,E)\), 我们构造了一个映射 \(\varphi:V\to V’\), 并描述了 \(V’\) 之间的邻接关系, 得到另一个图 \(G’=(V’,E’)\). 狭义的重标号多数是将 \(G’\) 构造为一条链 (也就是序列), 那么是否有可能让 \(G’\) 也变为树, DAG 甚至一般图, 并非直接解决而是将 \(G\) 上的维护需求归约到 \(G’\) 上的维护需求, 继而结合 \(G’\) 本身的性质求解, 更甚者再引入更多重标号, 使得 \(G\to G’\to G”\to\cdots\), 逐步归约向可直接维护的问题?

  好的我胡说八道结束了. 有没有好哥哥教教兔兔 (草, 叠词词三连连.

原文地址：http://www.cnblogs.com/rainybunny/p/16894808.html