我有一個陣列 a[0..n - 1]。我有兩種型別的操作：
- 總和 lr：總和 = a[l] * 1 a[l 1] * 2 ... a[r] * (r - l)
- 更新索引值：a[index] = value
如何為此任務修改標準總和段樹？
uj5u.com熱心網友回復：
存盤陣列總和的第二個段樹b，其中b[i] = (i 1) * a[i]。然后，設定a[index] = value也應該用 更新第二個段樹b[index] = value * (index 1)。
要計算您想要的總和，只要能夠查詢 和 的正常子陣列a總和b：
special_sum(l, r) = a[l] * 1 a[l 1] * 2 ... a[r] * (r - l)
can be rewritten as:
(l 1) * a[l] (l 2) * a[l 1] ... (r) * a[r]
- l * (a[l] a[l 1] ... a[r])
which becomes
b[l] b[l 1] ... b[r]
- l * (a[l] a[l 1] ... a[r])
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/424325.html
上一篇：尋找最接近的對