樹狀數(shù)組武鋼三中吳豪如果我們修改了任意一個A[i],S[i]、S[i+1]...S[n]樹狀數(shù)組武鋼三中吳豪如果我們修改了任意一個A[i],S[i]、S[i+1]...S[n]都會發(fā)生變化?？梢哉f，每次修改A[i]后，調(diào)S[]O(n)n非常大時，程序會運(yùn)行得非常緩慢。因此，這里我們引入“樹狀數(shù)組”，它的修改與求和都是O(logn)的，效率非常高。C[]0i2的冪方和表示時的最小指數(shù)。2^k=i&(i^(i-1))）同時，我們也不難發(fā)現(xiàn)，這個k就是該節(jié)點(diǎn)在樹中的高度，因而這個樹的高度不會超過logn。所以,當(dāng)我們修A[i]C[i]C[]即可，這個操作的復(fù)雜度在最O(logn)nn以前的所有最大子樹，Cn1n展開成2的冪方和時的項數(shù),因此，求和操作的復(fù)雜度也是O(logn)。i即p=i+i&(i^(i-1))(2^ki即p=i+i&(i^(i-1))(2^k是i2i為根節(jié)點(diǎn)子樹的規(guī)模即可。即p=i-i&(i^(i-1))。intSum(int{intsum=0;while(end>0){intLowbit(int{returnt&(t^(t-1)}voidplus(intpos,int{voidplus(intpos,int{while(pos<={in[pos]+=num;pos+=Lowbit(pos);}}sum+=end-=}return}saisai90101話說我學(xué)了這個樹狀數(shù)組N個日子了,還沒有用過,今天一用,果然不凡...-_-只是PKUOJ的E文讓我比較抓狂...看了半天才知道它講什么.這個題目乃入門題目,不贅述了...下面說一下我用樹狀數(shù)組的體會(語言比較難理解，字體比較難忍受==，請原諒)..組Treap、并查集等數(shù)據(jù)結(jié)構(gòu)一樣的美麗，清秀。不僅如此，它有著最大的藝術(shù)就在于1))，兩個可以隨便記一個，不過顯然第一個更容易記憶。雖然到現(xiàn)在我還不知道這兩句是如何計算到k化為二進(jìn)制數(shù)時末尾0的個數(shù)”(補(bǔ)充:可以參考本貼#17)=。＝！，但我很享受這一種奇特的除了insert()和get()時間復(fù)雜度都是O(logn)之外，其實(shí)這個很正常，樹狀數(shù)組特別的是 2/3Code//c[x]為樹狀數(shù)組,a[x]其實(shí)這里叫//mixN//因?yàn)樾薷腸[k]的話對 c[mix]有影響，所以不難想到k的變化為增變8.voidinsert(int*c,intk,intfor(;k<=mix;k+=(-k)＆k)c[k]}//getsum(int*c,intk){intt;for(t=0;getsum(int*c,intk){intt;for(t=0;k>0;k-=(-k)k)t+=c[k];returnt;}可能你看某幅圖會容易搞清楚啥是樹狀數(shù)組 ：世界上沒有免費(fèi)的午餐，你喜歡上樹狀數(shù)組，你就一定要承受它的缺點(diǎn),-_-//MM不過有一點(diǎn)我還沒有絕對地搞清楚，有人說樹狀數(shù)組可以解“最長不下降子序列”問題，但這個應(yīng)該會涉及到求某一個區(qū)間范圍內(nèi)最值。但是貌似樹狀數(shù)組要符合減法原則，也就是說不能求某一個區(qū)間范圍內(nèi)最值。初步來講，我認(rèn)為“樹狀數(shù)組解最長不下降子序列”和“減法原則”可能并不矛盾，可能有一在很多的情況下,線段樹都可以用樹狀數(shù)組實(shí)現(xiàn).凡是能用樹狀數(shù)組的一定能用線段樹.當(dāng)題目不滿足減法原則的時候,就只能用線段樹,不能用樹狀數(shù)組.例如數(shù)列操作如果讓我們求出一段數(shù)字中最大或者最小的數(shù)字,就不能用樹狀數(shù)組了。除了上面的“減法原則”之外，還需要說明的是：樹狀數(shù)組1樹狀數(shù)組必須由1開始。具體細(xì)節(jié)想一下就會知道，那是因?yàn)楦莻€“將k化為二進(jìn)制數(shù)時末尾0的個PKUOJ2352Stars2.#include6.voidinsert(intk,intdetal)7.{for(;k<=mix;k+=(-k)k)c[k]9.getsum(intintfor(t=0;k>0;k-=(-k)k)t+