Chlience

【算法】按时间分治的一类算法
Chlience真是太蒟了,连分治都不会此篇博客资料引自《许昊然:浅谈数据结构题的几个非经典解法》《徐寅展:线段树...
扫描右侧二维码阅读全文
13
2018/10

【算法】按时间分治的一类算法

Chlience真是太蒟了,连分治都不会

此篇博客资料引自
《许昊然:浅谈数据结构题的几个非经典解法》
《徐寅展:线段树在一类分治问题上的应用》

概念介绍

确立几个概念
询问: 作出回答
修改: 对询问操作答案有影响的操作

修改独立,允许离线 的数据结构题

使用对时间分治算法需要满足下面两个条件

  1. 修改操作对询问贡献独立,修改之间互不影响效果
  2. 允许使用离线算法

对于操作序列 S ,将其按时间分为前半段和后半段

  1. 后一半操作中的 修改 对前一半操作中的 询问 没有任何影响
  2. 后一半操作中的 询问 只受 前一半操作的 所有修改 和 后一半操作在 此询问之前的修改

显然,后一半操作完全无法影响前一半操作,所以前一半操作就是原问题的子问题,递归处理
而又因为修改操作互相独立,则后半段的 修改 操作并不会受到前半段操作的影响;而后面一半操作中的 所有查询 操作会受到前一半的 修改 操作影响,且每个 查询 受到的影响相同,我们可以利用这个性质,将前半段的 所有修改 合起来,那么这样后半段操作也成为了原问题的子问题,从而递归处理

这样就相当于分别计算每一段修改对某个询问的贡献

https://i.loli.net/2018/09/28/5bad9953791c4.png

在此时,动态修改已经被转化为一开始给出所有修改,回答若干询问的问题,大大简化算法

假设无动态修改操作的问题时间复杂度为 $O(f(n))$
那么由主定理可得
$$T(n) = 2T(\frac{n}{2}) + O(f(n))$$
$$T(n) \leq O(f(n)\log n)$$

那么,只要数据结构题满足上面两个要求,则可以用一个 $\log$ 的代价将其转化为无动态修改问题,从而极大简化代码

对删除和变更操作的支持

由于对时间分治要求操作是互相独立的,但是在实际应用中,常常需要支持一些 删除/变更 操作,就不能应用按时间分治的方法,这种情况又该如何处理呢?

一个优秀的做法是进行一次分治后将时间倒过来,那么删除就变为了原来的加入操作,即 时光倒流 ,但是在这里提供一种另外的方法:时间线段树

先考虑没有 删除/变更 操作的子问题,在时间分治中,每次都处理在左区间中的修改,对右区间的询问的贡献,在最后,剩下的区间大小为 1 ,这也就相当于将对应的操作插入到线段树叶子中去
可以发现:整个过程就相当于建立了 以时间为序的线段树

那么如果直接使用线段树来解决这一问题会不会更加优秀呢?

首先将每个操作插入到线段树叶子中,叶子的位置为操作对应的时间。

在每个非叶子节点处,把它左儿子的 修改 取出来,查询对于右儿子中 查询 的贡献

这样的做法和直接按时间分治的区别就是 按时间分治是从大区间到小区间,而这里是从小区间到大区间

换个角度思考,每个 修改 都会对之后所有 查询 做贡献,干脆直接在线段树上打标记,表示某个区间被该修改影响

显然,这个方法是可以推广到 删除 操作的:一个 修改 + 删除 的贡献 显然是连续的一段时间,那么按区间打好标记就行了

统计答案时,只需要 DFS / BFS 一遍线段树,输出到达某个叶子(询问)节点的所有标记对 询问 的贡献和

题目

BZOJ 2961 共点圆
题解 戳这

BZOJ 3562 [SHOI2014]神奇化合物
题解 戳这

一种通用的转化方法

因为在现今信息学竞赛中,有像 删除/变更 这样的操作的题目较少
在这里提供一种方法将形如 $[l,r]$ 中所有元素全部变为某一相同元素 这种操作,转化为 添加 与 撤销 操作

将所有修改操作拿出来,依次插入到一棵按位置建的线段树中,并对区间打上标记
然后插入的时候 pushdown 一下,到达最终位置后将子树中标记全部取出
假设当前修改操作插入时间为 $i$ ,某个取出的标记插入时间为 $j$ ,取出的标记在线段树上的位置为 $[l , r]$ ,那么在转化后的问题中添加两个操作:

  1. $j$ 时刻将 $[l,r]$ 修改为某个元素
  2. $i$ 时刻将 1 操作撤销

实现时只需要记录某个节点的子树有无标记即可

转化后的问题操作数不会超过 $m \log n$

End

时间分治到这里就结束啦~
感谢观看 qwq

Last modification:October 13th, 2018 at 10:41 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment