千鋒教育-做有情懷、有良心、有品質(zhì)的職業(yè)教育機構

手機站

千鋒學習站 | 隨時隨地免費學

掃一掃進入千鋒手機站

領取全套視頻

關注千鋒學習站小程序
隨時隨地免費學習課程

一、樹狀數(shù)組的原理

原理

樹狀數(shù)組的原理是，樹狀數(shù)組為了節(jié)省空間，刪去了不必要的結點，將結點數(shù)壓縮到與數(shù)組長度相同。方案是這樣的：數(shù)組的每個位置代表其在圖中垂直向上追溯可以達到的較高的結點。

樹狀數(shù)組可以解決什么問題

可以解決大部分區(qū)間上面的修改以及查詢的問題，例如1.單點修改，單點查詢，2.區(qū)間修改，單點查詢，3.區(qū)間查詢，區(qū)間修改，換言之，線段樹能解決的問題，樹狀數(shù)組大部分也可以，但是并不一定都能解決，因為線段樹的擴展性比樹狀數(shù)組要強。

樹狀數(shù)組和線段樹的區(qū)別在哪

有人會問了既然線段樹的問題能夠用樹狀數(shù)組解決而且線段樹還比樹狀數(shù)組擴展性強，那為什么不直接用線段樹呢？問的很好，樹狀數(shù)組的作用就是為了簡化線段樹，舉個例子：一個問題可以用線段樹解決寫代碼半個小時，但是用樹狀數(shù)組只需要10分鐘，那么你會選擇哪一個算法呢?沒錯，基于某些簡單的問題，我們沒必要用到功能性強但實現(xiàn)復雜的線段樹(殺雞焉用宰牛刀)。

優(yōu)缺點

優(yōu)點：修改和查詢操作復雜度于線段樹一樣都是logN,但是常數(shù)比線段樹小，并且實現(xiàn)比線段樹簡單

缺點：擴展性弱，線段樹能解決的問題，樹狀數(shù)組不一定能解決。

延伸閱讀：

二、完全二叉樹

完全二叉樹是一種特殊的二叉樹，滿足以下要求：

所有葉子節(jié)點都出現(xiàn)在 k 或者 k-1 層，而且從 1 到 k-1 層必須達到最大節(jié)點數(shù)；第 k 層可以不是滿的，但是第 k 層的所有節(jié)點必須集中在最左邊。?需要注意的是不要把完全二叉樹和“滿二叉樹”搞混了，完全二叉樹不要求所有樹都有左右子樹，但它要求：任何一個節(jié)點不能只有左子樹沒有右子樹；葉子節(jié)點出現(xiàn)在最后一層或者倒數(shù)第二層，不能再往上。