【数据结构2-3】线段树的进阶用法

本章主要学习可持久化线段树与树状数组套权值线段树的一些应用。我们知道，对于一棵线 段树而言，如果它的总长度不变，那么它的形态是不会改变的。也就是说，在值域不变情况下， 权值树的形态是不会改变的。这样一来，就可以对权值树进行合并的操作。对于权值树$A$，$B$，若 $A$，$B$ 形态相同，则可以合并这两棵权值树，合并的方式就是对应结点相加。  显然，合并后的树依然是一棵权值线段树。可以将权值线段树的合并类比为加法。类似的， 也可以类比得到权值线段树的减法，即对应点数相减。这个性质非常的重要，接下的内容就要基 于这一性质。本章内容较难，读者可以将本章的阅读的优先级调后。