[問題案] SegTree系

[yosupo06]

No description provided.

[yosupo06]

#113

基本的に色んな種類の演算を1個用意して、色々作っていく

1点add / 区間sum

• 一番基本的といって過言ではない、採用
• 可換, 結合, 逆元

[yosupo06]

2 x 2行列、1点変更 / 区間積

• 非可換, 結合, 逆元はどっちでもできる

バイナリ文字列、1点変更 / 転倒数

• マイナー？
• 非可換, 結合, 逆元なし

どっちがいいだろう(非可換, 結合タイプ)

[yosupo06]

#3

[kmyk]

1次関数、1点変更 / 区間関数合成
(f = ax + b, g = cx + d のとき演算 f ○ g = f(g(x)) = acx + ad + b)

• 非可換、結合、逆元なし
• マイナーではなくかつ行列より実装が楽

これどうかな

[yosupo06]

ありです

[yosupo06]

区間加算/区間max

• (Starry Sky Treeの影響が大きい気もするが)多分一番基本的な遅延伝搬segtree
• 区間変更(加算): 可換、結合、逆元
• 区間結合(max): 可換、結合、逆元なし

遅延伝搬segtree、パラメーターが多すぎないか？

[yosupo06]

#20 #125

[yosupo06]

区間行列積/区間行列set

• 区間変更(行列積): 非可換、結合、逆元どっちでもいい
• 区間結合(行列set): 非可換、結合、逆元なし
• 変更、結合で両方非可換なのがこれぐらいしか思いつかなかった
• 実装が面倒(行列+k乗)、ランダムケースだと多分めっちゃ弱い(数列にランダムにsetクエリを飛ばすとひどいことになる)

そもそも結合じゃないと多分どうしようも無いから書く必要なかったな

[yosupo06]

↑一次関数でも可能だった

[yosupo06]

操作一覧 基本的に逆元は消す理由がないので消さない

• 基本、可換 [問題案]Point Add Range Sum(point_add_range_sum) #20
  • 1点add
  • 区間sum
• 基本、非可換 [問題案] Point Set Range Composite (Linear Functions) (point_set_range_composite) #122
  • 1点変更、f(x) = ax + b
  • 区間合成、f(f(...f(x))))
• 遅延伝搬、要素可換、伝搬非可換 (問題例まだなし)
  • 区間変更、f(x) = ax + b
  • 区間sum

欲しいかもしれない候補？

• 伝搬可換だと実装の自由度が上がる(遅延伝搬がいらなくなったり)
• 要素非可換、伝搬非可換は欲しいか？

[yosupo06]

この3種類で一通りは大丈夫なはず