icontofig | 发布于 2019-11-20 12:11:47 | 阅读量 359 | 并查集 可持久化数据结构
发布于 2019-11-20 12:11:47 | 并查集 可持久化数据结构
可持久化数据结构众所周知,在竞赛界有这么一种神奇的解决方案,用以解决简单数据结构无法恢复历史版本的问题。 它就是可持久化! 如何可持久化?当然是要记录历史信息了。 但是那消耗空间不会巨大吗? 起始如果我们可以合理运用历史版本信息,我们就可以在创建新版本的时候尽可能地缩减需要的空间。 我们可以在当前版本复用未被修改地上一个版本的信息内存。 然而如何才能尽可能地去复用内存空间呢?这就需要树形结构了。 所以,对于所有的可持久化数据结构而言,都需要可持久化数组(一棵树)这样的基础。 怎么建立可持久化数组呢?可持久化数组的建立类似线段树,也就是可持久化线段树的建树过程。 所以说,可持久化线段树的建树是所
继续阅读