hdu1394 樹狀數組 解法

本題使用樹狀數組果然更加快。

樹狀數組難點：

1 如何周遊樹

2 如何利用數組資料

建立一個樹狀數組就如上圖紅色部分代表所有的樹狀數組節點了。

基本操作：

查找下一個節點的計算，如不明白下面函數的作用，請檢視負數記憶體存放的問題。

簡而言之就是：記憶體放是求反+1； 利用這個函數可以神奇地尋找到其單親節點和兄弟節點，比如上圖6->8，6->4或者7->8， 7 -> 6這樣跳轉節點。

這是樹狀數組實作的關鍵了，了解了如何周遊這樣的樹，就會使用這個資料結構了。

更新節點：

求和操作：

參考資料：

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

主要是看圖，然後自己思考，看代碼吧。

解決這道題的代碼：