Subtree Sum Costs Extra

An LCT maintains path aggregates for free. Why is a subtree sum harder, and what is the standard repair?

A

A splay node already aggregates its whole represented subtree. Nothing hangs off it that the parent fails to merge. No repair is needed, since access(x) gathers the entire subtree of xx into one splay tree and the root's aggregate is the answer.

B

A splay node only aggregates its own preferred path. Everything else hangs off as virtual children the parent never merges. The repair is a separate virtual-subtree aggregate per node, updated whenever access promotes or demotes a preferred child.

C

A splay node only aggregates its own preferred path. Everything else hangs off as virtual children the parent never merges. There is no repair available inside an LCT, so the standard answer is HLD, or an Euler tour with a Fenwick tree over the tour.

D

A splay node only aggregates its own preferred path. Everything else hangs off as virtual children the parent never merges. The repair is a makeroot(x) before every subtree query, whose reversal flag pushes the whole query to O(log⁡2n)O(\log^2 n).