habara-k / ICPCLibrary

https://habara-k.github.io/ICPCLibrary/

3 stars 0 forks source link

Closed habara-k closed 4 years ago

habara-k commented 4 years ago

概要

	index `i` に値`x` をset	index `i` に`x`を加算
現在の実装	`g = [](M a, M b){return b;}`	`g = [](M a, M b){return a+b;}`
提案実装	`segt.update(i, x)`	`segt.update(i, segt[i] + x)`

現在の実装のデメリット

現在の実装710ms, 提案実装711msでほぼ同速（segt[i]がO(1)で動作するため）

habara-k commented 4 years ago

cc @kanra824

kanra824 commented 4 years ago

クエリが更新のセグ木を別に作るということ？

habara-k commented 4 years ago

別ではなく、上書きしようかなと思っています（更新だけでも、加算がsegt.update(i, segt[i] + x)でできるので）

kanra824 commented 4 years ago

やりたいことはわかったけど、面倒な演算を載せたいときにupdateのたびにいちいち書かなきゃいけなくなってめちゃくちゃ面倒になりそう変更する理由に対してデメリットが大きすぎる気がします

kanra824 commented 4 years ago

いやその演算は別で関数として定義すればいいかそれもうセグ木の中にしまっておけばよくない？

habara-k commented 4 years ago

確かに面倒な演算は大変ですね...

LazySegmentTreeのg(M, OM) と区別したいので、せめて名前だけでも変えたいんですけどどうですか（例えばupdateのuとか）

もしかしてこのgって一点更新しかないLazySegmentTreeのgってことか

なるほどね

habara-k commented 4 years ago

変更、なし！

kanra824 commented 4 years ago

見てへんかった　変更なしでよい？

kanra824 commented 4 years ago

まあupdateの時の書き方を覚えればいいので...とは思う

kanra824 commented 4 years ago

あ、gはsegmenttreeのgを考えていた