麗山演算法讀書會
線段樹 (Segment Tree)
Try
HackMD
麗山演算法讀書會
·
Follow
Last edited by
自由星光
on
Feb 4, 2021
Linked with GitHub
Contributed by
Edit
0
Comments
Feedback
Log in to edit or delete your comments and be notified of replies.
Sign up
Already have an account? Log in
There is no comment
Select some text and then click Comment, or simply add a comment to this page from below to start a discussion.
Discard
Send
線段樹 (Segment Tree)
前言:
線段樹的功能很強大,可以支援各種區間操作
區間查詢(以RMQ為例):
相對ST表而言,這分法犧牲了查詢複雜度,但仍舊可以解決大部分區間查詢的問題
線段樹的常數有點大,請多多留意~
方法:
考慮把區間拆成
O
(
l
o
g
n
)
個「不重疊的」區間
建表建成這樣(對於以下這些區間建立最大值):
Image Not Showing
Possible Reasons
The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported
Learn More →
這麼一來,
建表複雜度:
O
(
n
)
查詢複雜度:
O
(
l
o
g
n
)
單點修改:
如果只有單點修改,很簡單
觀察一下上面的圖,如果我們要將點k做修改,會發現整棵樹包含到點k的區間只有
O
(
l
o
g
n
)
個,所以:
時間複雜度:
O
(
l
o
g
n
)
區間修改(以 RMQ 為例):
如果修改一個區間,最暴力的作法是把每個區間內的點做單點修改。
時間複雜度:
O
(
n
)
似乎有點太大!
沒關係,現在才是線段樹真正厲害的地方~~!
我們從區間查詢的方法,發現如果我們只修改至多這
O
(
l
o
g
n
)
個區間就好了~
時間複雜度:
O
(
l
o
g
n
)
可是有些需要被修改的點就沒被改到阿!?沒關係,我們有懶人標記。
懶人標記(lazy tag)
如果我們修改了一個點,並且那個點之後都
沒被查詢
,那不修改也沒差對吧(?)
所以我們只要記得這個區間有被修改過,並且查詢時,分別告訴左右子樹(如果有的話),你們也被修改了!
講的抽象,舉個例子:
你現在是小主管,總經理要發年終獎金給大家,並且拿一部分給你的老闆(Alien),希望你的老闆(Bob)分配給你底下的成員。
有趣的事情來了:
你的老闆(Bob)懶得發下去,就先自己獨吞了>_<
總經理(Alien)也不是笨蛋,他要去檢查你有沒有拿到年終獎金。
你的老闆(Bob)不得已,只好把獎金發給你們了
於是你通過檢查了~
這次換你懶得發下去,就先自己獨吞了>_<
總經理(Alien)也不是笨蛋,他要去檢查你的下屬(Clinton)有沒有拿到年終獎金。
你被迫將該給你下屬們的年終獎金發給它們
於是你的下屬(Clinton)通過檢查了~
題目:
模板 ZJ d539
變形題 POJ 3419
變形題 ZJ a164
挑戰題 SPOJ DQUERY
線段樹 (Segment Tree)
Expand all
Back to top
Go to bottom
線段樹 (Segment Tree)
Expand all
Back to top
Go to bottom
×
Sign in
Email
Password
Forgot password
or
By clicking below, you agree to our
terms of service
.
Sign in via Facebook
Sign in via Twitter
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet
Wallet (
)
Connect another wallet
New to HackMD?
Sign up
Comment