いじれるセグ木
いじれるセグ木
うえすぎさん(@takeda_SE)のおかげで公開できました。感謝します。
競プロerなら一度は憧れるフレーズ「セグ木で殴る」
憧れ続けてはや1年、機運が高まってきたので
作ってみました、視覚的に理解できるセグ木。
操作方法
初期化
- type: セグ木に載せたい機能を選択します。xorとかgcdも作る予定があります。2022/4/28 WhiteF326によりモノイドの種類が増えました。
- n: 配列の要素数です。32を越えると見づらくなり、65以上だと何が起きているかわからなくなるため、それなりの数字をお薦めしています。
- A: 配列の要素をスペースで区切って入力してください。私はデバッグの際、いちいち配列を考えるのが面倒になりました。ですので、random fillボタンを押すと1〜9の数字で要素数nの配列を生成します。
上記を埋めた後、initializeボタンを押すとセグ木が生成されます。
2022/4/28 セグ木の配列を2nのみ確保し、複数の木を作るタイプを実装しました。
クエリ1
[l, r)の区間に対し以下の処理を行います。
typeによって行う処理が異なります。
- sum: 区間和を求めます。単位元は0です。
- mul: 区間積を求めます。単位元は1です。
- xor: 排他的論理和を求めます。単位元は0です。
- or: 論理和を求めます。単位元は0です。
- and: 論理積を求めます。単位元は02b:1111111…なのですが未実装です。
- min: 区間内の最小値を求めます。単位元は♾です。
- max: 区間内の最大値を求めます。単位元は-♾です。
- gcd: 区間内の最大公約数を求めます。単位元は？？
処理に参加したセルが青く塗られます。
今後、もう少しわかりやすく動くようにしたいです。
クエリ2(update)
i(1-indexed)番目の値をxに更新します。
更新されたセルが青く塗られます。
このセグ木はえびちゃんさんのスライドを参考にして作られました。本当に助かりました。ありがとうございます。