树链剖分

问题

如果现在有一棵有根树,在树上进行路径的修改、求极值、求和,有什么方法呢?

1. 暴力

显然可以$LCA$+暴力修改查询,这样对于大多数随机数据,时间都可以接受,然鹅出题人大都并不那么友善,暴力显然容易被卡。

2.