gzr_csdn的博客

单点修改，区间查询多了树状数组也干不了，接下来全文描述的是单点加，区间和查询。

设想一个区间上的问题，单点修改值，动态查询某区间的和。

仔细思考求解最短路径的算法多了什么冗余的东西，我们不需要知道具体路径是什么，也不需要知道最短路径的长度，我们只需要知道能不能走过去，我们甚至不需要知道两个人互相怎么称呼对方，我们只需要知道。不知道你是否这样思考过，如果每个树只有两级，上面是代表元素，下面是在这个集合里的元素，这些元素与代表元素直接相连就好了，这样每次查询都是O(1)那么我们可以用某个代表元素指代集合，如果没有特殊元素的情况下，这个“代表”可以随意指派，此时，这个问题由图转变为了树，先讲按树的大小合并，即元素少的合并到元素多的上去。