树链剖分简介 链剖分 指对树的边进行划分的一种操作，目的是减少在链上修改、查询等操作的复杂度。链剖分分三类：轻重链剖分、虚实链剖分和长链剖分。 树链剖分思想 通过轻重链剖分将树分为多条链，保证每个节点都属于且只属于一条链。树链剖分时轻重链剖分，节点到重儿子，也就是到子树节点最多的儿子之间的路径就是重链。每条重链都相当于一段区间，把所有重链首尾相接组…