RMQ 问题——线段树 & 树状数组 & ST 表板子笔记

发布于 2020-11-01  167 次阅读


前言

新名词:

  • LCA 算法:最近公共祖先,Least Common Ancestors。
  • RMQ/RSQ 问题:Range Minimum/Maximum/Sum Query。
  • Segment Tree:线段树。
  • Lazy Tag:懒标记。

区间修改

区间修改的懒标记关键点:如果单个元素被包含就只改变自己,如果整个区间被包含就修改整个区间。

区间查询得到各个区间要求的区间查询值后,进行区间修改。区间修改就可以运用到懒标记——“表示每个块被修改过多少”。

举例来说,分块中求 RSQ 问题时就可以通过记录懒标记:

inline void f(ll p,ll l,ll r,ll k)
 //(Parent, L-Son, R-Son, Change)
{
   tag[p]=tag[p]+k;
   ans[p]=ans[p]+k*(r-l+1);
   //由于是这个区间统一改变,所以 ans 数组要加元素个数次啦
}
//Adapted from 皎月半洒花 @ Luogu.

线段树 I

线段树有分块的影子,分块有暴力的影子。

线段树因为符合树特性,一个结点可以分儿子。例如 RMQ、RSQ 的区间问题可以用线段树解决。其传递满足结合律。

线段树相比于 O(n) 算法最大的优势在于,从根结点向下进行区间查询时,在 update() 的函数中已经完成了懒标记的预处理,这时再进行 push_down() 和 push_up() 的懒标记维护操作;再加上线段树本身的分块特性,这样我们就可以在 O(logn) 下得到想要的区间查询值啦。

在线段树中,我倾向于用这两个小名词:

  • 区间结点:例如 [1,6] 的区间,它的儿子是 [1,3] 和 [4.6] 对应的结点,那么称这两个儿子都为区间结点,而高级区间结点则是相当于 [1,2]、[1,3] 和 [1,6] 之间的关系,虽然说这里应该用“父结点”,但是高级更像是广义上的“父结点”,包含叶子(或某个中间结点)其上的所有父结点。
  • 影响:也就是懒标记,最新的区间修改传递值 k。没有被传递到懒标记,也可以看作没有成功产生影响,这种情况出现在一次区间更新或者查询中,完全覆盖到了一个区间,那么对于这个区间结点来说,它以下的结点都没有被传递懒标记,即没有产生影响。
if (l >= nl && r <= nr){
    ans[p] += k * (r - l + 1);
    tag[p] += k;
    return;
}//这个点主要描述“当前结点的区间真包含于要更新的区间内”

要实现几个函数:

  • f():正是前言中实现方式所提到的,该操作的目的是对一个(子)区间更新懒标记和 ans 的最新影响 k,更新了对应的父结点的 tag 和 ans 数组。这个操作的主要功能是更新高级区间结点的要求得的信息。
  • push_down():在必要时(即将对区间修改进行影响测量时),由父结点向儿子结点传递区间修改(懒标记),懒标记成功传递下去,对 ans 数组产生影响,并将父结点上的标记清空。这个操作的主要功能是在查询到小区间时应用上方大区间的修改。也就是说,在我们的区间修改或查询正好完全覆盖了一个区间结点,我们就可以不向下面的结点继续进行操作,直接返回这个结点已经处理好的 ans 就可以了。
  • push_up(),在 OI-wiki 上也可以叫作 maintain(),即维护函数:由儿子结点向父结点(回溯)传递区间查询。该操作是为了维护父子结点之间的逻辑关系。实质上在合并两个子结点的信息。有了递归,自然就有了回溯。这个操作的主要功能是向更高级结点传递两个子结点答案,直到大于查询或更新的区间以下,这方便小区间合并为大区间查询,故只需要父结点一个实参。
  • build(),建树嘛,很好理解哒。在这里注意,我们递归到 l 与 r 相等时,就是达到了叶子结点,从这里开始赋值 ans 数组。

在 update() 或 query() 函数中,我们看到二分的影子啦。

if(q_x<=mid) res+=query(q_x,q_y,l,mid,ls(p));
if(q_y>mid) res+=query(q_x,q_y,mid+1,r,rs(p));

这里我们看到了两个判断条件,在查询中,如果查询的左边界小于二分的中间值,那么继续进行左二分的分割查询。反之,如果左边界大于了二分的中间值,那么这个区间一定没有落在左二分中,对左二分不需要进行任何操作了。

另外,在 update() 和 query() 函数中,一定要注意及时进行 push_down() 和 push_up() 操作,对懒标记产生的影响进行推广或回溯。另外,这两个函数中,存在递归的返回,返回的条件是目前正计量的区间被完全包含在了要查询的区间

一篇很易于理解的文章:https://blog.csdn.net/weixin_43843835/article/details/88750190#Ologn_166,从前缀和和差分引入的思路真的很容易理解!

我终于搞懂了呜呜呜。

树状数组

因为 wqy 大佬说树状数组用不太上的样子,要不然我们就少看一点好了。

本来只想写线段树 I 的笔记的没想到越写越长啦。

在线段树 I 中,有一个单点修改操作,基本算法思想是树状数组——”将某一个数加上 x”或“求出某一个数的值”。而树状数组的实现和二进制的关系又很紧密。其传递满足交换律。

ST 表

ST 表的实质相当于 DP。

线段树 II


三叶望久,往复新秋。