【每日一题】倍增思想
【倍增思想】
倍增经典递推公式：f[u][i]=f[f[u][i−1]][i−1]
即： u的第2^i个父亲节点是 u的第2^(i-1)个父亲的节点的第2^(i-1)个父亲节点
因为：2^i = 2^(i-1)+2^(i-1)
【本题】
在这题中，题目说是树上的多次查询，可以联想到倍增（优化暴力查询），如果不是多次查询，倍增并不好用，因为倍增需要预处理f数组以及树的深度
定义f[u][i]为从某节点u出发往根走，购买了2^i件物品的位置
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
int p[MAXN],h[MAXN],ne[MAXN];//链式前向星写法
int num=0;
const int N = 2e5 + 7;
int n, q, val[N], mrk[N];
int f[N][20], dep[N];
void addEdge(int from, int to){
p[++num] = to;//to->from
ne[num] = h[from];
h[from] = num;
p[++num] = from;
ne[num] = h[to];
h[to]=num;
}
//f[u][i]:保存u结点往根方向第2^i个val大于它的结点
void dfs(int u, int father){
dep[u] = dep[father] + 1;//记录深度
if (val[u] < val[father]){
f[u][0] = father;
}else{
int x = father;
for (int i = 19; i >= 0; --i){//x逼近第一个比val[u]大的结点下方的结点
if (f[x][i] && val[u] >= val[f[x][i]]){
x = f[x][i];
}
}
f[u][0] = f[x][0];//得到第一个比val[u]大的祖先结点
}
for (int i = 1; i <= 19; ++i){//刷新倍增数组
f[u][i] = f[f[u][i-1]][i-1];
}
for(int i=h[u];i!=0;i=ne[i])if(p[i]!=father){
// f[p[i]][0]=u;
dfs(p[i],u);
}
}
int main(void){
cin >> n >> q;
for (int i = 1; i <= n; ++i) cin >> val[i];
for (int i = 0; i < n-1; ++i){
int u, v; cin >> u >> v;
addEdge(u,v);
}
for (int i = 1; i <= q; ++i){
int u, v, c; cin >> u >> v >> c;
addEdge(n+i,u);//每个询问新加一个结点连在u下面
val[n+i] = c, mrk[i] = v;//新结点val设为c，记录目标祖先v
}
dep[0]=0;
dfs(1, 0);//dfs预处理倍增数组
for (int i = 1; i <= q; ++i){
int u = n+i, v = mrk[i], ans = 0;
for (int j = 19; j >= 0; --j){
if (dep[f[u][j]] >= dep[v]){//用倍增数组，从u往v跳
u = f[u][j];
ans += (1<<j);//记录跳了多少步
}
}
cout << ans << endl;
}
return 0;
}
【再贴一道ST表，理解倍增思想】
链接：https://ac.nowcoder.com/acm/contest/82/B
给你一个长为n的序列a和一个常数k
有m次询问，每次查询一个区间[l,r]内所有数最少分成多少个连续段，使得每段的和都 <= k
如果这一次查询无解，输出"Chtholly"
输入描述:
第一行三个数n,m,k 第二行n个数表示这个序列a 之后m行，每行给出两个数l r表示一次询问
输出描述:
输出m行，每行一个整数，表示答案
示例1
