初识—树链剖分

对于树链剖分怎么说呢，结构大致是怎么样的呢？我觉得我的理解和网上教程写的很不一样！！！很不一样！！！

他们说：首先把一棵树剖分成  m 条链 ，然后对于重新组成线段树，其节点是区间。

但是我觉得是：

首先我给出一个要求用树形的结构处理的东西，然后预处理这棵树（方便建树的时候或者查询的时候进行加速是吧？）将这棵树化成重链和轻链，将每条边编上号，按照先重链再轻链的方式给每条边编号，就是按照这个标号进行建树，节点 1 节点 2 。。。。

什么什么的。建好之后呢？重点是什么？

重点是树链剖分可以在查询的时候加速，比如，我想查 节点 i  和节点 j 之间的最短路（也就是边权最小值）那么我就可以利用重链进行加速，就是说沿着重链走下去，加速？

先写这么多吧，让我见几个题目看看吧。

树链剖分 真谛：

假如给你一个树形结构，当然不是简单的二叉树，每个节点上都可能有好多分叉，现在，要求你对这样的一棵树，假设是下图这种。

操作：

一开始，每个节点都有一个初值。

添加： 将  u 节点 到 v 节点路径上所有的点加上   值  val

查询：  查询单个点，或者  u  到  v   路径上所有点值的和。

那么我们怎么做？

树链剖分正是解决这种问题的一种方法。

首先，我们对这棵树进行剖分，对每条边都按照某种次序（先重链后轻链）编号，然后把这些编号看成线段树中的节点，用线段树处理这类问题。

简单来说，线段树是一种工具，解决这个问题工具。