天天看點

線段樹,樹狀數組,RMQ之間的差別與聯系

樹狀數組主要用于計算區間的和,在區間元素修改值的時候能夠

快速修改而不是以O(n)的複雜度進行修改;

線段樹是把區間以樹的形式分拆為若幹個小區間,每個小區間存

的都有一個值(樹狀數組的元素存的是區間值),是以線段樹可

以快速獲得這個區間裡面的所有的節點(元素),主要用于計算

每個區間的最大最小元素(也可以快速修改區間元素的值)

RMQ是用數組的形式存儲元素的值,用二分的方法進行計算區間

的最大最小值,是以他比較快!但是有個缺點就是每一次修改區

間的元素都會影響其最終結果,就是每一次修改都要進行一次

RMQ,是以修改的時候很複雜!

是以如果單純的計算差點問線或者插線問點用樹狀數組,如果單

純的求固定區間(即區間的元素無修改)的最大最小值用RMQ!

如果既求某一區間的最值且又修改值就用線段樹!