倍增
本文最后更新于:2024年2月12日 晚上
定义
倍增法(binary lifting),顾名思义就是翻倍,可以把线性的处理转换为对数级别的处理,本质是DP。
最常用于解决RMQ(区间最大/小值)问题和求LCA(最近公共祖先)。
LCA
状态转移方程为:
解释:要找到距离节点
所以,需要计算距离每一个节点为
预处理时间复杂度为:
public TreeAncestor(int n, int[] parent) {
dp = new int[n][32];
// 首先记录每个节点的父节点:2 ^ 0 = 1
for (int i = 0; i < n; i++) dp[i][0] = parent[i];
// 动态规划计算距离为 2 ^ j 的祖先
for (int j = 1; j < 20; j++) {
for (int i = 0; i < n; i++) {
// 状态转移
dp[i][j] = dp[i][j - 1] != -1 ? dp[dp[i][j - 1]][j - 1] : -1;
}
}
}
查询时间复杂度为:
public int getKthAncestor(int node, int k) {
if (k == 0 || node == -1) return node;
// 找到k的最高位1所在的位置(0-based)
int pos = 31 - Integer.numberOfLeadingZeros(k);
// 递归的查找祖先节点的祖先节点
return getKthAncestor(dp[node][pos], k - (1 << pos));
}
class TreeAncestor {
int[][] dp;
public TreeAncestor(int n, int[] parent) {
dp = new int[n][32];
// 首先记录每个节点的父节点:2 ^ 0 = 1
for (int i = 0; i < n; i++) dp[i][0] = parent[i];
// 动态规划计算距离为 2 ^ j 的祖先
for (int j = 1; j < 20; j++) {
for (int i = 0; i < n; i++) {
// 状态转移
dp[i][j] = dp[i][j - 1] != -1 ? dp[dp[i][j - 1]][j - 1] : -1;
}
}
}
public int getKthAncestor(int node, int k) {
if (k == 0 || node == -1) return node;
// 找到k的最高位1所在的位置(0-based)
int pos = 31 - Integer.numberOfLeadingZeros(k);
// 递归的查找祖先节点的祖先节点
return getKthAncestor(dp[node][pos], k - (1 << pos));
}
}
RMQ
ST表
参考
本文作者: MerickBao
本文链接: https://merickbao.top/post/%E7%AE%97%E6%B3%95/%E8%BF%9B%E9%98%B6%E7%AE%97%E6%B3%95/%E5%80%8D%E5%A2%9E.html
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!
Powered By Valine
v1.5.1
v1.5.1