预处理静态树，以便支持O(1)时间O(N)空间的RMQ/LCA/

一、Intro

最近在刷MIT 6.851，记录下笔记。
MIT 6.851 session-15-static-trees/
Lecture note

In this lecture, we look at various data structures for static trees, in which, given a static tree, we
perform some preprocessing and then answer queries on the data structure. The three problems
we look at in this lecture are range minimum queries (RMQ), least common ancestors (LCA), and
level ancestors (LA); we will support all these queries in constant time per operation and linear
space.

二、用自己的话解释

我们的目标是通过预处理静态树，实现能够O(1)时间进行RMQ/LCA/LA查询、占用O(N)空间的数据结构。

2.1. 支持快速RMQ和LCA查询的数据结构应该怎么设计？

朴素的看，RMQ问题用线段树可以O(N)预处理，O(logN)查询，或者用ST表，O(NlogN)预处理，O(1)查询。
朴素的看，LCA问题可以暴力染色法，或者用树上倍增的思想，O(NlogN)预处理，O(logN)查询（这方法在《算法竞赛进阶指南》上有）。
那么怎么优化到O(1)时间查询，O(N)的空间和预处理时间？

核心思想是：RMQ和LCA可以互相归约（用笛卡尔树归约），因此都能用ST表在O(1)时间内查询，但是需要O(nlogN)的空间。
怎么优化ST表的空间？为了优化空间复杂度中的log系数，可以用indirection的思想（个人理解indirection翻译成“间接层”比较合适。总之这个优化掉log的思想就是分块+间接层），先分块（每块1/2logN大小），再在所有块之上套一层间接层，加的这层数据较少(有2n/logn个元素)，用ST表只占O(n)的空间。

image.png

而对于每个小块内的RMQ，思想是针对这种块很多、但每块大小很小的场景，都可以构造lookup table+DP减少不同块的个数（比如减少元素的取值范围从而减少不同数组的个数）
具体到本问题，如果我们限定每个块内的元素只能有+1或-1（通过把LCA问题归约成+-1 RMQ，这个蛮复杂的看课件吧)，那么总共只有O(根号N)个不一样的块（可以理解成对数组的“形状”做DP，有O(根号N)个形状不同的数组），暴力算每个块内每个区间的rmq结果然后存到lookup table里，总的占用空间小于O(N)。
最终达到时间O(1),空间线性。
过程较复杂，个人怀疑工程实现出来比O(logN)的还慢。不过OI wiki上还真有例题https://oi-wiki.org/graph/lca/#_5

2.2. 支持快速LA查询的数据结构应该怎么设计？

2.2.1. 思想

朴素的方法：暴力法，或者用树上倍增，O(NlogN)预处理，O(logN)查询。见https://leetcode-cn.com/problems/kth-ancestor-of-a-tree-node/

优化思路：树上倍增+树链剖分（扩展长链剖分，把长链剖分扩展为两倍长），实现O(nlogn)空间，O(1)时间；然后树上indirection，优化到O(N)空间。具体细节贼复杂。

image.png

2.2.2. 实现

查了下中文博客，还真有人实现出来了……清华大佬真厉害
https://ljt12138.github.io/2019/08/13/level-ancestor/#more

吐槽

数据结构领域研究出来的新东西该怎么应用，好像只能在算法竞赛用上？
更奇葩的是这个大学课程感觉还不如算法竞赛的视频资料讲得好……可能是因为非母语，听起来各种听半天听不懂。