树上倍增|st表

lc1483

ST表的本质就是二进制拆分，只要满足传递性，可加性即可，和线段树，树状数组，二分查找的底层数学模型是一致的

不得不说，这种记录2^j父节点的想法太巧妙了，第一次见，觉得惊艳。 blow my mind 的感觉，极具美感的算法让人如受洗礼一样，佩服第一次想出这种算法的大佬。

5. 类似的思想在很多算法里都有体现.

6. 树的高度如果是N怎么办，比如退化成链表

7. 代码没变化，复杂度分析没变化。文字确实有个小错误：树的最大的高度是 n 级别的，所以人一个节点到距离为 1, 2, 4, 8, 16, 32 ... 的祖先，最多存储到 logn 这么多祖先的距离，所以状态总数是 nlogn 的。

8. 我一直以为叫ST表

9. st 也用到了 binary lifting 的思想，但 st 不是 binary lifting，st 是指创建一个表快速求查询一个数组的最大值，最小值，和或者其他统计数据。可以参考这里：https://cp-algorithms.com/data_structures/sparse-table.html

class TreeAncestor {

private:

vector<vector<int>> dp;

public:

TreeAncestor(int n, vector<int>& parent) : dp(n) {

for(int i = 0; i < n; i ++)

dp[i].push_back(parent[i]);

for(int j = 1; ; j ++){

bool allneg = true;

for(int i = 0; i < n; i ++){

int t = dp[i][j - 1] != -1 ? dp[dp[i][j - 1]][j - 1] : -1;

dp[i].push_back(t);

if(t != -1) allneg = false;

}

if(allneg) break; // 所有的节点的 2^j 的祖先都是 -1 了，就不用再计算了

}

}

int getKthAncestor(int node, int k) {

if(k == 0 || node== -1) return node;

int pos = ffs(k) - 1; // C++ 语言中 ffs(k) 求解出 k 的最右侧第一个 1 的位置（1-based）

return pos < dp[node].size() ? getKthAncestor(dp[node][pos], k - (1 << pos)) : -1;

}

};