關於線段樹(Segment tree)和樹狀數組(BIT)的區別？

01-02

近期本人在學習樹狀數組和線段樹，主要參考的是劉汝佳的《演算法競賽入門經典》。
然而在網路上查詢到的相關資料，都是與劉汝佳的說法相反。那麼請問哪種說法才是正確的呢？

線段樹處理的數據和運算只需要是幺半群就可以支持單點修改區間查詢。而樹狀數組要求是交換群才行。

===

更新：

數據類型為 $S$ ，更新操作為將 $a_i$ 變為 $f(a_i,x)$ ，查詢為求 $sum_{i=l}^r a_i = a_l+a_{l+1}+ dots + a_r$ 。

如果 $(S, +)$ 構成一個幺半群，就可以用線段樹實現。

如果 $f(a_i,x) = a_i+x$ 並且(S, +)構成一個交換群，就可以用樹狀數組實現。

數據類型為 $S$ ，更新操作為對所有的 $l leq i leq r$ 將 $a_i$ 變為 $a_i*x$ ，查詢為求 $sum_{i=l}^r a_i = a_l+a_{l+1}+ dots + a_r$ 。

如果 $(S,+)$ 構成一個幺半群， $(S,*)$ 構成一個幺半群，並且滿足右分配律，即 $(a+b)*c=a*c+b*c$ ，就可以用帶懶標記的線段樹實現。

假設數組長度為n。

線段樹和樹狀數組的基本功能都是在某一滿足結合律的操作(比如加法，乘法，最大值，最小值)下，O(logn)的時間複雜度內修改單個元素並且維護區間信息。

不同的是，樹狀數組只能維護前綴「操作和」(前綴和，前綴積，前綴最大最小)，而線段樹可以維護區間操作和。

但是某些操作是存在逆元的，這樣就給人一種樹狀數組可以維護區間信息的錯覺:維護區間和，模質數意義下的區間乘積，區間xor和。能這樣做的本質是取右端點的前綴和，然後對左端點左邊的前綴和的逆元做一次操作，所以樹狀數組的區間詢問其實是在兩次前綴和詢問。

所以我們能看到樹狀數組能維護一些操作的區間信息但維護不了另一些的:最大/最小值，模非質數意義下的乘法，原因在於這些操作不存在逆元，所以就沒法用兩個前綴和做。

而線段樹就不一樣了，線段樹直接維護的就是區間信息，所以一切滿足結合律的操作都能維護區間和，並且lazy標記的存在還能使線段樹能夠支持區間修改，這點是樹狀數組做不到的。

可以說樹狀數組能做的事情其實是線段樹的一個子集，大多數情況下使用樹狀數組真的只是因為它好寫並且常數小而已。

不過隨著zkw線段樹的普及，樹狀數組僅有的兩點優勢也不復存在了……估計要成為時淚了吧。

利益相關:弱省弱校弱菜，只能討論一些基本功能，各位神犇就不要在這個回答下拿樹狀數組的高級用法說事了，因為我真的沒學過……

線段樹是擁有明確二分結構的樹，長這樣：

樹狀數組沒有明確的二分結構，只有類似於前綴和的結構，長這樣：

另外，您自己寫一遍這兩種數據結構，不就理解他們的區別了嗎……

謝邀

根據題目描述，我沒看出樹狀數組和線段樹的任何區別

都是一個空行

我好害怕這不符合我腦中的線段樹和樹狀數組我以前可能看了假書，參加了假NOIP，寫了假樹狀數組

我個人認為，主要差異是在對子結點的處理上，樹狀數組中的非葉點，有一個顯式表示的子結點和一個隱含的子結點（在存儲中不存在，通過自身與其它子結點做差可計算出來）。而線段樹中非葉點的所有子結點都是顯式表示的。

PS：你看了無字的假書

線段樹可以保存並維護許多區間的特性，如最大值、最小值（如在線RMQ）、存在值（如配合掃描線實現矩形覆蓋面積計算）等，而樹狀數組只能用於區間求和。

從效率來說

如果只用於求和

線段樹和樹狀數組時間複雜度都是O(log n)

空間複雜度為O(n)，但需要注意的是，線段樹的空間複雜度在常數上為樹狀數組的兩倍。

所以建議，如果只用於區間求和，寫樹狀數組，代碼短且少佔空間。如果需要實現各種功能，如在線RMQ，選擇線段樹。

再我看來，樹狀數組就是特化的線段數。

樹狀數組常數小，但是能幹的事也少。

除了bit求k大。

1. 所有能用樹狀數組的，一定能用線段樹求解。

2. 能用樹狀數組或者線段樹求解的，樹狀數組通常更快。

高中的時候我想了一個非常惡俗的比喻，如果說問題是上廁所，那麼樹狀數組就是站著上廁所，線段樹就是蹲著

bit的要求：有逆元，滿足交換律和結合律

線段樹的要求：有了結合律就可以！

我本來以為線段樹code比樹狀數組code多很多，直到有了zkw

在zkw的論文中，zkw大神講到線段樹和樹狀數組沒區別；

在我看來，除了儲存方式的區別外，也就空間和時間上的常數區別。