hdu1394 树状数组 解法

本题使用树状数组果然更加快。

树状数组难点：

1 如何遍历树

2 如何利用数组数据

建立一个树状数组就如上图红色部分代表所有的树状数组节点了。

基本操作：

查找下一个节点的计算，如不明白下面函数的作用，请查看负数内存存放的问题。

简而言之就是：内存放是求反+1； 利用这个函数可以神奇地寻找到其单亲节点和兄弟节点，比如上图6->8，6->4或者7->8， 7 -> 6这样跳转节点。

这是树状数组实现的关键了，理解了如何遍历这样的树，就会使用这个数据结构了。

更新节点：

求和操作：

参考资料：

http://www.cppblog.com/Ylemzy/articles/98322.html

主要是看图，然后自己思考，看代码吧。

解决这道题的代码：