問題リンク：https://yukicoder.me/problems/no/3112

tester：Shirotsumeさん

競技プログラミングでおなじみのフェニック木を、本来の使い方とは違った使い方で流用することが想定のネタ問題です。フェニック木がそもそもどのようなデータ構造だったかに立ち戻って考えなければ思いつけない使い方であるため、既にライブラリー化してしまって直書きする機会が減ってしまった人には盲点となりやすかったかもしれません。

ネタ要素が「用法を守らずにデータ構造を流用する」という部分なのでエイプリルフールコンの他の問題とは毛色がやや異なりますが、楽しんでくださいますと嬉しいです。

ちなみに詳しくは解説を読んでいただきたいですが、頑張るとセグメント木でも通すことが可能です。これもまたセグメント木の実装に立ち戻らないと思いつきにくいテクニックとなっておりますので興味のある人は是非挑戦してみてください。

さて、ここからはもう問題の内容に関係なく、久々にwriterをした嬉しさから来る雑談です。

上述したように結果的にはセグメント木でも通ってしまうのですが、元々は「フェニック木がセグメント木の下位互換でない部分を活かした作問をしてみたい」という気持ちがこの問題を考案したきっかけでした。競技プログラミングを勉強してみて色々なアルゴリズムの中でも特にデータ構造が好きなのですが、更にその中でも人から教わって一番最初に学んだデータ構造であるフェニック木は思い入れが強く、いまだに使い倒しています。

おかげでセグメント木はほとんど使ったことがなくライブラリー化も最低限しかしていないため理解が浅いままなのですが、フェニック木はセグメント木と比べるとだいぶ理解できるようになってきたと思います。まずセグメント木にはモノイドが乗り、モノイドに可換律や逆元律を課しても特に実装が変わらないので計算速度に影響がないように見えます（単純にセグメント木の理解が浅いだけの可能性もあります）が、一方でフェニック木もまたモノイドが乗り、可換律や逆元律を課すか否かで実装や計算速度が変わると考えています。代数の要件に従って抽象化の仕方を変えたり実装をいじったりしていると何だか代数の問題を解いているような気分を味わえるのも面白いところだと思っています。

最近は色々な方々に平方分割を教えていただいたおかげで平方分割も使い倒していて、フェニック木と平方分割を使い分けていけば自分がコンテスト中に出会える（つまり★3以下の）クエリであってセグメント木で処理できるものは基本的に何でも処理できるようになってしまうため、ますますセグメント木をきちんとライブラリー化する動機を見失ってしまっているのですが、そもそもセグメント木のライブラリーを整備する気が重い原因の一つに、セグメント木への自分の理解に引っかかりを感じているからでした。

どういうことかと言うと、「モノイドが乗ると言っている割に、遅延評価させる時の乗せ方がいびつじゃないか？」という引っ掛かりです。これは今まで自分の理解が浅いだけだからもっと深く理解が進んだら解消される引っ掛かりだと思っていたのですが、ついこの前、引っ掛かりの原因として１つの仮説に思い至りました。

それは、セグメント木に乗せるべき自然な対象は半開区間（を順序集合とみなしたもの）からの関手であって、モノイドはその具体例の１つに過ぎないのではないか、という仮説です。関手に対しては自然に実装できる処理も、それをモノイドに落とし込んで実装する際には色々と余計な情報を後から負荷しなければならないのではないでしょうか？　実際、区間加算も区間代入更新も区間等差数列加算も、関手への作用としては（モノイドのときのように構造を後から付加することなく）自然に実装できると考えています。

セグメント木に詳しい人に聞かれたら鼻で笑われるかもしれませんし、逆に常識だったりするかもしれませんが、こういった代数学がデータ構造に絡んでくる部分が競技プログラミングの面白いところの１つだと思っています。この辺もう少し自分の中で視野が広げられたらそろそろセグメント木のライブラリー整備に取り掛かるのもありかな、という気持ちが湧いてきています。

久々の嬉しさから長々と書いてしまいましたが、お読みいただきありがとうございました。そしてご参加いただきありがとうございました！