【问题解】关于Fhq解法的困惑
查看原帖
【问题解】关于Fhq解法的困惑
302750
Main_WF楼主2022/7/21 07:47
圈内代表节点编号,红字代表节点的值。

它显然不满足 BST 的性质,因为我们维护的是中序遍历。

那么目前,此序列即为 {2-3-5-1-4} 这是按照对此树中序遍历得来的。

有一个很显然的性质:对于目前序列一个连续的区间,在这棵树中所对应的节点也是相连的。

那么也很显然,我们只要分裂两次就能分裂出我们先要的区间。

那么分裂就显而易见了,对于翻转 [l,r][l,r],我们先把 [1,l-1][1,l−1] 这个区间分裂,也就是大小为 l-1l−1 的子树分裂,然后对于这个 [l,n][l,n] 的这个树,我们分裂出大小 r-l+1r−l+1 的一棵树。这个只要你知道啥是按大小分裂都能想清楚吧。

上面题解原话,但不是很懂为什么按照大小分裂能得到对应的区间,比如:为什么L-1为界分裂子树能得到分别对应[1,L-1]和[L-n]的子树

2022/7/21 07:47
加载中...