倍增真的好难理解啊 WSL
No.1 倍增 RMQ:P3865 [模板] ST 表 https://www.luogu.org/problem/P3865
题目描述
给定一个长度为 \(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\)行, 每行一个整数, 依次表示每一次询问的结果.
解法
线段树
emmmm, 数据范围, 请.
ST 表(重头戏)
倍增思想的重要应用, 我们设 \(f[i][j]\)表示从 \(i\)开始, 连续 \(2^j\)个数中的最大 (小) 值.(我是真的难转过这个弯来, 这样我们就可以发现一些事情:
- \(f[i][0]=a[i]\)(定义)
- \(f[i][j] = max(f[i][j - 1], f[i + (1 <<(j - 1))][j - 1])\)
第二条是因为什么呢?
首先我们要知道,\(f\)数组的处理顺序是先确定一个左端点, 然后一直往右扩展 \((\)固定 \(i\)增加 \(j)\). 因此每当我们把 j+1, 当前区间都会增长一倍, 这时候区间 \([i,j]\)无非只有两种情况:
它在左半部分 \(([i,i+2^{j-1}])\)
它在右半部分 \(([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];
- }
来源: http://www.bubuko.com/infodetail-3163317.html