用

Python

構(gòu)建樹(shù)形數(shù)組，并且寫(xiě)出

GetSum,?update,?FindMax

三個(gè)函數(shù)，分別對(duì)應(yīng)的是：查

找從

1

到

n

的

sum

，

對(duì)于某一個(gè)元素增加

num

，需要對(duì)數(shù)組進(jìn)行維護(hù)更新(

update

)

，

并

且構(gòu)建一個(gè)

maxArray

數(shù)組供查詢?nèi)我庖欢螀^(qū)間的

max

#?Author

：

Z

#?Date:?2016-01-08

import?random

a?=?[0?for?i?in?xrange(30)]

b?=?[random.randint(0,100)?for?i?in?xrange(30)]

maxb?=?[0?for?i?in?xrange(30)]

minb?=?[0?for?i?in?xrange(30)]

def?lowbit(x):?#?lowbit?function

return?x&(-x)

def?build_tree_array():?#?Build?tree-array?a?by?inital-array?b

for?i?in?xrange(1,len(b)):

num1?=?i?-?lowbit(i)?+?1

num2?=?i?+?1

for?j?in?xrange(num1,num2):

a[i]?+=?b[j]

def?GetSum(x):?#?Get?sum(b)?[1,...x]

s?=?0

while?x?>?0:

s?+=?a[x]

x?-=?lowbit(x)

return?s

def?update(idex,num):

#?for?b:?b[idex]+=num?so?for?a?is:

while?idex?<=?(len(a)-1):

a[idex]?+=?num

idex?+=?lowbit(idex)

def?initmax():

for?i?in?xrange(1,30):

maxb[i]?=?b[i]

j?=?1

end?=?lowbit(i)

while?j

總結(jié)

以上是生活随笔為你收集整理的python树形_Python处理树形数组的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。