基于子树大小的小空间常数树分块

· · 题解

Part1 前言

当我发现我写不动“暴力写挂”了，这是一大树上数据结构的终结。

众所周知，根号半 \log 一般都不是正解，所以严格根号是有必要的，这道题可以称之为树分块维护修改的模板。

Part2 基于随机的树分块

也就是随机撒点建虚树，这样的方式是可行的，期望复杂度为 O(n+q\sqrt n)。

但我觉得在这道题目卡空间的同时还能使用严格复杂度是更有趣的。

Part3 基于子树大小的树分块

就是在搜索时，如果一个节点有一个以上的子树内有关键点，或者除去关键点子树之后的大小超过了 \sqrt n 就将该子树设为关键点，这样能保证分成的块数和大小均不超过 \sqrt n，当然这道题为了防止栈空间过大，需要使用非递归形式，注意到这里将节点权值和子树大小共用了同一个数组，所以不会超过只能开两个 O(n) 的 int 的限制。

我们需要保证根节点为关键点，认为每一个关键点一直往上走，直到碰到关键点为止，这样的一个路径上的点为一个块，块的深度就是该块上方的块数。

考虑两个节点不断将块更深的跳到块顶，可以在 O(\sqrt n) 的时间内找到两个节点的 LCA，这时，修改和询问都可以差分成根到某节点路径上的修改或询问。

Part4 细节

首先，这道题只能开两个 O(n) 的数组，即父亲和单点权值，在解码权值之前，要将关键点先求出。

求 LCA 当两个点同块时，可以借鉴 access 求 LCA 的方法，就是将一个点往上跳跳父亲，标记，另一个点往上跳，碰到的第一个点就是答案。

Part5 后记

其实只要你会树分块那么这道题就是签到题了，因为就是模板，只是卡掉了高空间常数做法而已，LOJ 上的 AC 记录。