#32776: 不用線段樹的方法
eason9506@gmail.com
(Eason Huang)
學校
:
不指定學校
編號 : 197870
來源 : [1.200.161.211]
最後登入時間 ：
2023-06-10 19:02:08
d799. 区间求和
| From: [180.217.46.180] |
發表日期
:
2022-11-05 20:05
有一個資料結構叫BIT(Binary Indexed Tree)或稱Fenwick Tree，中文是樹狀數組。一般情況下，BIT能單點改值、區間查詢。而此題要求區間改值、區間查詢，便需要改變一下原本的BIT。原理及實作可以自行去查詢 OuOb
以下是我用BIT實作的結果
#35169: Re: 不用線段樹的方法
eason9506@gmail.com
(Eason Huang)
學校
:
不指定學校
編號 : 197870
來源 : [1.200.161.211]
最後登入時間 ：
2023-06-10 19:02:08
d799. 区间求和
| From: [180.217.44.118] |
發表日期
:
2023-05-14 12:50
最近偶然點開這題，想說用線段樹解解看，發現比BIT快很多
但這不太可能，因為線段樹是用遞迴，常數很大，相較之下BIT都是迴圈，理論上會快很多
結果發現我之前BIT那份程式碼沒有I/O優化ww，開了之後果然BIT快了許多，記憶體用量也少很多
線段數 1.1s, 36.1MB
BIT 0.4s, 7.9MB
ZeroJudge Forum