一、樹狀數組的原理
原理
樹狀數組的原理是，樹狀數組為了節(jié)省空間，刪去了不必要的結點，將結點數壓縮到與數組長度相同。方案是這樣的：數組的每個位置代表其在圖中垂直向上追溯可以達到的較高的結點。
樹狀數組可以解決什么問題
可以解決大部分區(qū)間上面的修改以及查詢的問題，例如1.單點修改，單點查詢，2.區(qū)間修改，單點查詢，3.區(qū)間查詢，區(qū)間修改，換言之，線段樹能解決的問題，樹狀數組大部分也可以，但是并不一定都能解決，因為線段樹的擴展性比樹狀數組要強。
樹狀數組和線段樹的區(qū)別在哪
有人會問了既然線段樹的問題能夠用樹狀數組解決而且線段樹還比樹狀數組擴展性強，那為什么不直接用線段樹呢？問的很好，樹狀數組的作用就是為了簡化線段樹，舉個例子：一個問題可以用線段樹解決寫代碼半個小時，但是用樹狀數組只需要10分鐘，那么你會選擇哪一個算法呢?沒錯，基于某些簡單的問題，我們沒必要用到功能性強但實現復雜的線段樹(殺雞焉用宰牛刀)。
優(yōu)缺點
優(yōu)點：修改和查詢操作復雜度于線段樹一樣都是logN,但是常數比線段樹小，并且實現比線段樹簡單
缺點：擴展性弱，線段樹能解決的問題，樹狀數組不一定能解決。
延伸閱讀：
二、完全二叉樹
完全二叉樹是一種特殊的二叉樹，滿足以下要求：
所有葉子節(jié)點都出現在 k 或者 k-1 層，而且從 1 到 k-1 層必須達到最大節(jié)點數；第 k 層可以不是滿的，但是第 k 層的所有節(jié)點必須集中在最左邊。?需要注意的是不要把完全二叉樹和“滿二叉樹”搞混了，完全二叉樹不要求所有樹都有左右子樹，但它要求：任何一個節(jié)點不能只有左子樹沒有右子樹；葉子節(jié)點出現在最后一層或者倒數第二層，不能再往上。
京公網安備 11010802030320號