倍增真的好难理解啊WSL

No.1 倍增RMQ:P3865 【模板】ST表

题目描述

给定一个长度为$N$的数列，和$M$次询问，求出每一次询问的区间内数字的最大值。

输入格式

第一行包含两个整数$N,M$,分别表示数列的长度和询问的个数。

第二行包含$N$个整数$($记为 $a_i)$,依次表示数列的第$i$项。

接下来$M$行，每行包含两个整数$l_i,r_i$,表示查询的区间为 $[ l_i, r_i] $

$1≤N≤10^5,1≤M≤10^6,a_i∈[0,10^9],1≤l_i≤r_i≤N$

输出格式

输出包含$M$行，每行一个整数，依次表示每一次询问的结果。

解法

  1. 线段树

emmmm,数据范围,请.

  1. ST表(重头戏)

倍增思想的重要应用,我们设$f[i][j]$表示从$i$开始,连续$2^j$个数中的最大(小)值.(我是真的难转过这个弯来,这样我们就可以发现一些事情:

  1. $f[i][0]=a[i]$(定义)
  2. $f[i][j] = max(f[i][j - 1], f[i + (1 <<(j - 1))][j - 1])$

第二条是因为什么呢?

首先我们要知道,$f$数组的处理顺序是先确定一个左端点,然后一直往右扩展$($固定$i$增加$j)$.因此每当我们把j+1,当前区间都会增长一倍,这时候区间$[i,j]$无非只有两种情况:

  1. 它在左半部分$([i,i+2^{j-1}])$
  2. 它在右半部分$([i+2^{j-1},i+2^{j}])$

这就是上式的意思啦.因为我们在处理$j$时,$j-1$的情况一定已经处理好了,所以可以做到递推.

代码:

for (int j = 1; j <= 20; ++j)
    for (int i = 1; i + (1 << j) - 1 <= n; ++i)
        f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);

接下来就是询问了.

当我们在询问时,肯定不能保证区间长度恰好是$2$的次幂,也就是和$f[l][k]$不一定重合.因此我们将区间分成两个相交的部分,比如区间是$[l,r]$,那么我们就把区间分成两部分,但是这两部分是相交的:$[l,l+2^k],[r-2^k+1,r]$,其中$k$是最大的满足$2^k\le$区间长度的正整数.这样取一下max就可以了.

但是我们注意到,k并不能用暴力来求,否则会当场去世.所以我们还要处理一个k的数组.我们注意到,我们需要$2^k\le r-l+1$,这意味着,$k(k\in N_+)$应该等于$\lfloor log_2(r-l+1)\rfloor$.我们需要处理一个$log_2$数组,(以及我们可以顺便初始化一下$f$数组).

LOG[0] = -1;
for (int i = 1; i <= n; ++i)
    f[i][0] = a[i], LOG[i] = LOG[i >> 1] + 1;

学过对数函数的自然能看明白

现在我们可以放心大胆的求解了

代码:

for (int i = 1; i <= m; ++i) {
    read(q1), read(q2);
    int k = LOG[q2 - q1 + 1];
    printf("%d\n", max(f[q1][k], f[q2 - (1 << k) + 1][k]));
}

No.2 倍增求LCA

序列和树链总是相通的——某位哲人

通常求$LCA$的方式有树剖,奇怪的我不会的神仙$O(1)$做法,以及本文要讲的倍增法.

一切都是从暴力开始的——某位哲人

当我们试图暴力求$LCA$的时候,画风将会是下面这个样子:

inline int LCA(int x, int y) {
    while (x != y) {
        if (dep[x] < dep[y])
            swap(x, y);
        x = father[x];
    }
    return x;
}

数据范围大起来以后时间复杂度显然是$O($跑不过$)$,只能另想别的办法.

还记得上一道题吗?如果暴力在序列上找,同样会$TLE$,而这个暴力找$LCA$的过程也是一样的复杂度.因此我们可以尝试相似的优化方法.如果我们一次跳一大段,肯定能省很大的复杂度,甚至还可以让两个点一起跳.

我们这样来考虑:

为了保证相遇,我们通常令深度较大的一个点向上跳.倍增和暴力的最大区别是一次跳的步数和跳时两个点是否同步.仍然设$f[i][j]$表示从点$i$往上连续$2^j$的点.这次不再需要$LOG$数组,只要$f$数组就够了.当我们在寻找$x,y$的$LCA$时,先选中深度较大的一个点,然后不断往上跳,直到与另一个点深度相同.这是如何实现的呢?众所周知,任何正整数都可以进行二进制拆分,这和我们维护的第二维恰好很契合.根本上来说,我们就是把初始时两个点的深度的差$K$进行二进制拆分,在每个$”1”$位代表的数处跳一次.操作上来说,就是倒序循环$20$到$1$,如果跳一步后还比另一个点深,就跳.或者说是从$K$可能的最高位往下匹配,如果匹配到1就跳.不过为了防止在$”0”$的位置仍然得出”能跳”的结论从而导致最后无法恰好一样深,一定要倒序哦.

现在$x,y$一样深了,接下来,我们就在它们相遇之前,不断一起往上跳.同样是二进制思想.最终,他们之差一点就相遇了,这时候只需要随便选一个当代表往上跳一步就可以了,这就是$LCA$!

代码:

int lca(int x, int y) {
    if (dep[x] < dep[y])
        swap(x, y);
    for (int i = 20; i >= 0; i--) {
        if (dep[f[x][i]] >= dep[y]) 
            x = f[x][i];
        if (x == y) 
            return x;
    }
    for (int i = 20; i >= 0; --i)
        if (f[x][i] != f[y][i])
            x = f[x][i], y = f[y][i];
    return f[x][0];
}

——Gensokyo