树状数组入门篇2

树状数组的高效性主要就是通过将一条线段分成若干个小线段(其中每个小线段存储着2^k大小的区间和,这就将区间和问题复杂度降到了logn),而不是一个一个单一的点

add()操作修改了单点的值,同时对之后的父亲节点进行了更新(之所以只更新该点以及该点的父亲节点而不更新该点的非父亲节点,是因为求和时父亲节点直接包含该点所以会跳过该点,也就不能接受该点,所以就需要自身更新,而非父亲节点在求和时会直接加上该点,所以就不需要进行更新)

正是由于add()操作对父亲节点以及非父亲节点的区别才使每次的sum()操作求到的就是更新之后的正确值

也正是由于树状数组的add()通过对单点的修改就能对该点之后的区间和进行修改,所以树状数组不仅可以解决简单的单点修改与区间和查询,还能进行区间点修改与单点查询

其中进行单点修改时的add()修改单点,sum()查询区间和,而进行区间点修改时,add()修改区间点的变动次数,sum()查询单点的变动次数

杭电oj1556http://acm.hdu.edu.cn/showproblem.php?pid=1556

原文地址:https://www.cnblogs.com/MekakuCityActor/p/8507298.html