樹(shù)狀數(shù)組的幾種用法？假設(shè)數(shù)組的長(zhǎng)度為n，線段樹(shù)和樹(shù)數(shù)組的基本功能是在滿足約束律的一定運(yùn)算（如加法、乘法、最大值、最小值）下，修改單個(gè)元素，并在o（logn）時(shí)間復(fù)雜度內(nèi)保持區(qū)間信息。不同的是樹(shù)數(shù)組只能

樹(shù)狀數(shù)組的幾種用法？

假設(shè)數(shù)組的長(zhǎng)度為n，線段樹(shù)和樹(shù)數(shù)組的基本功能是在滿足約束律的一定運(yùn)算（如加法、乘法、最大值、最小值）下，修改單個(gè)元素，并在o（logn）時(shí)間復(fù)雜度內(nèi)保持區(qū)間信息。不同的是樹(shù)數(shù)組只能維護(hù)前綴“運(yùn)算和”（前綴和、前綴積、前綴max min），而段樹(shù)可以維護(hù)區(qū)間運(yùn)算和。但有些運(yùn)算有逆元素，這給人一種錯(cuò)覺(jué)，認(rèn)為樹(shù)數(shù)組可以保持區(qū)間信息：保持區(qū)間和、模素?cái)?shù)意義上的區(qū)間積、區(qū)間異或和。這樣做的實(shí)質(zhì)是取右端點(diǎn)的前綴和，然后對(duì)左端點(diǎn)的前綴和的逆做一個(gè)操作，所以樹(shù)數(shù)組的區(qū)間查詢實(shí)際上是兩個(gè)前綴和查詢?？梢?jiàn)樹(shù)數(shù)組可以保留某些運(yùn)算的區(qū)間信息，但不能保留其它運(yùn)算的區(qū)間信息：Max/min值，模非素?cái)?shù)意義下的乘法，因?yàn)檫@些運(yùn)算中沒(méi)有逆元素，所以不能使用兩個(gè)前綴的和。但是片段樹(shù)是不同的。分段樹(shù)直接維護(hù)區(qū)間信息，所有滿足組合規(guī)則的操作都可以維護(hù)區(qū)間和，而懶標(biāo)記的存在也使得分段樹(shù)支持區(qū)間修改，這是樹(shù)數(shù)組所不能做到的。可以說(shuō)樹(shù)數(shù)組所能做的實(shí)際上是線段樹(shù)的子集。在大多數(shù)情況下，真正使用樹(shù)數(shù)組僅僅是因?yàn)樗子诰帉?xiě)，而且它的常量很小。然而，隨著zkw段樹(shù)的流行，樹(shù)數(shù)組僅有的兩個(gè)優(yōu)點(diǎn)已經(jīng)不復(fù)存在了，我想這將是一個(gè)巨大的挑戰(zhàn)。興趣相關(guān)：弱省、弱校、弱菜。我們只能討論一些基本功能。請(qǐng)不要在這個(gè)答案中談?wù)摌?shù)數(shù)組的高級(jí)用法，因?yàn)槲疫€沒(méi)有學(xué)會(huì)

定義：如果二叉樹(shù)的深度設(shè)置為h，則除h層外，每層（1-h-1）中的節(jié)點(diǎn)數(shù)達(dá)到最大值，h層中的所有節(jié)點(diǎn)都連續(xù)地集中在最左邊，這是一個(gè)完整的二叉樹(shù)。

所以，第一行有1=2^0，第二行有2=2^1，依此類推，第n行有2^（n-1）

那么總數(shù)是一個(gè)等比序列，前n行有2^n-1

很明顯，一維數(shù)組是按下標(biāo)順序表示的，我們可以找到在完全二叉樹(shù)中的位置

假設(shè)數(shù)組從a[1]開(kāi)始，例如a[25]，25=15 10=（2^4-1）10，那么a[25]是第四個(gè)1=5行中的第10個(gè)數(shù)

你的意思是以數(shù)組的形式存儲(chǔ)二叉樹(shù)，這需要利用完全二叉樹(shù)的特性樹(shù)。完全二叉樹(shù)通常用數(shù)組代替鏈表進(jìn)行存儲(chǔ)，其存儲(chǔ)結(jié)構(gòu)如下：樹(shù)：數(shù)組[1.. n] 在樹(shù)[i]的最長(zhǎng){n:integer n>=1}中，它具有以下特征：（1）如果i是奇數(shù)且i>=1，則樹(shù)的左兄弟是樹(shù)[i-1]；（2）如果i是偶數(shù)且i