我有一個三維fenwick tree數據結構。 我需要計算從(x0, y0, z0)到(x, y, z)的一些區段的總和3d Fenwick樹
什麼是包含排除的公式？ 例如，對於二維變體是預先
s = sum(x, y) - sum(x, y0 - 1) - sum(x0 - 1, y) + sum(x0 - 1, y0 - 1)
由於
http://www.comp.nus.edu.sg/~stevenha/ft.pdf
這裏是2D的情況： 
式涉及總共8個計算
value1 = sum(x,y,z)- sum(x0-1,y,z) - sum(x,y0-1,z) + sum(x0-1,y0-1,z)
value2 = sum(x,y,z0-1) - sum(x0-1,y,z0-1) - sum(x,y0-1,z0-1) + sum(x0-1,y0-1,z0-1)
final answer = value1 - value2
代碼的時間複雜度爲8 (logn)^3
你怎麼看得見。
1> assume it as a cube.
2> value 1 gives answer for upper square layer of cube, but it include sum upto 0 in z-axis.
You only want upto z0, so you have subtract that extra part(from z0 to 0, and that is value2).
請提供一個參考資料（鏈接）或一個很好的解釋什麼是三維Fenwick樹它。 – RBarryYoung 2012-07-29 22:36:46
我剛剛解決了我的問題。無論如何，也許有人也會堅持下去，所以：long s = sum（x，y，z）-sum（x0 - 1，y，z） - sum（x，y0 - 1，z） - sum（x （x0-1，y0-1，z）+ sum（x0-1，y，z0-1）+ sum（x0-1，y0-1，z0-1） sum（x，y0 - 1，z0 - 1） – 2012-07-29 23:05:54
@DenysAstanin：如果您發現自己的問題的解決方案，回來並添加作爲解決方案，並接受它，以便其他人可以知道，如果有人有同樣的問題，它也可以幫助他們。 – Rndm 2012-07-30 14:37:06