衡阳网站建设怎样收费,织梦如何做英文网站,TP框架网站的中英文切换怎么做,分享站wordpress主题主要应用场景
RMQ#xff1a;区间最值问题 LCA#xff1a;最近公共祖先问题
RMQ问题——区间最值
如果用数组f[N]存储,用数组a[i][j]表示从第i个数起连续 2^j 个数中的最大值,[i,i 2^j - 1],显然a[i][0] f[i],则很容易得到状态转移方程: a[i][j] max(a[i][j - 1], a[i …主要应用场景
RMQ区间最值问题 LCA最近公共祖先问题
RMQ问题——区间最值
如果用数组f[N]存储,用数组a[i][j]表示从第i个数起连续 2^j 个数中的最大值,[i,i 2^j - 1],显然a[i][0] f[i],则很容易得到状态转移方程: a[i][j] max(a[i][j - 1], a[i 2^(j - 1)][j - 1]) 那么我们只需要对开始时,对于数组a进行预处理。我们先更新所有长度为0的情况a[i][0] f[i]。然后,通过2个1元素的最值a[i][0]获得1个2元素的最值a[i][1],依次类推。 由于这里第二维j表示的是从i起,长度为2^j个数,所以j最大为logn,这里的复杂度应该是O(nlogn)。 此时,对于每一次询问的复杂度为O(1) 如果我们查询区间为[l,r],那么此时区间长度为 (r - l 1),所以取 k log(r - l 1),可以将询问转换成 max(l,r) max(a[l][k], a[r - (1 k) 1][k])。 其中,a[l][k]表示的是区间[l, l 2^k - 1], a[r - 2^k 1][k]表示的区间是[r - 2^k 1, r]。
参考代码
参考例题洛谷 P3865 【模板】ST 表
#include bits/stdc.h
using namespace std;
typedef long long ll;
const int N 2e6 3;
int n, t, arr[N][32];int query(int l, int r)
{int k (int)(log((r - l 1) * 1.0) / log(2.0));return max(arr[l][k], arr[r - (1 k) 1][k]);
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin n t;for (int i 1; i n; i)cin arr[i][0];for (int j 1; j (int)(log(n * 1.0) / log(2.0)); j){for (int i 1; i (1 j) - 1 n; i){arr[i][j] max(arr[i][j - 1], arr[i (1 (j - 1))][j - 1]);}}while (t--){int l, r;cin l r;cout query(l, r) \n;}
}LCA问题——最近公共祖先
参考例题
洛谷 P3379 【模板】最近公共祖先LCA蓝桥OJ 最近公共祖先LCA查询
要求两个点的LCA先将这两个点调整到同一高度(结点高度大的向上跳)之后两个结点同时往上跳当他们到达同一高度时该结点即为他们的LCA。 这里关键的是预处理将每个结点的向上的父节点全部记录下来方便结点向上跳时候使用。
例1参考代码(C)
#include bits/stdc.h
using namespace std;
// 2^logn 需要大于 N
const int N 500003, logn 22;
struct zzz {int t, nex;
}e[N 1];
int head[N], tot;
void add(int x, int y) {e[tot].t y;e[tot].nex head[x];head[x] tot;
}
int depth[N], fa[N][logn], lg[N];
void dfs(int now, int fath) {fa[now][0] fath; depth[now] depth[fath] 1;for(int i 1; i lg[depth[now]]; i)fa[now][i] fa[fa[now][i-1]][i-1];for(int i head[now]; i; i e[i].nex)if(e[i].t ! fath) dfs(e[i].t, now);
}
int LCA(int x, int y) {if(depth[x] depth[y]) swap(x, y);while(depth[x] depth[y])x fa[x][lg[depth[x]-depth[y]] - 1];if(x y) return x;for(int k lg[depth[x]] - 1; k 0; --k)if(fa[x][k] ! fa[y][k])x fa[x][k], y fa[y][k];return fa[x][0];
}
int main() {int n, m, s; scanf(%d%d%d, n, m, s);// 建树for(int i 1; i n-1; i) {int x, y; scanf(%d%d, x, y);add(x, y); add(y, x);}// 预处理for(int i 1; i n; i)lg[i] lg[i-1] (1 lg[i-1] i);dfs(s, 0);for(int i 1; i m; i) {int x, y; scanf(%d%d,x, y);printf(%d\n, LCA(x, y));}return 0;
}例2参考代码
#include bits/stdc.h
using namespace std;
// 2^logn 需要大于 N
const int N 1e5 3, logn 20;
class TreeEdge
{
public:int to, nex;
} edge[N 1];
// head
int head[N], tot;
void add(int x, int y)
{edge[tot].to y;edge[tot].nex head[x];head[x] tot;
}
int n, q, depth[N], f[N][logn], lg[N];void dfs(int now, int fath)
{f[now][0] fath, depth[now] depth[fath] 1;for (int i 1; i lg[depth[now]]; i)f[now][i] f[f[now][i - 1]][i - 1]; // 2^(i - 1) * 2^(i - 1) 2^ifor (int i head[now]; i; i edge[i].nex)if (edge[i].to ! fath)dfs(edge[i].to, now);
}int lca(int a, int b)
{if (depth[a] depth[b])swap(a, b);while (depth[a] depth[b])a f[a][lg[depth[a] - depth[b]] - 1];if (a b)return a;for (int k lg[depth[a]] - 1; k 0; --k)if (f[a][k] ! f[b][k])a f[a][k], b f[b][k];return f[a][0];
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin n;for (int i 1; i n; i){int u, v;cin u v;add(u, v), add(v, u);}for (int i 1; i n; i)lg[i] lg[i / 2] 1;dfs(1, 0);cin q;while (q--){int a, b;cin a b;cout lca(a, b) \n;}
}
