ABC331Fでロリハをセグ木にのせろと言ってるようなもんじゃんっていう問題が出たわけですが、その場で解けず悲惨な目にあいました。

なので1点更新のロリハをライブラリ化したわけですが、最近Link Cut Treeのライブラリ化を試みていたりと地味に平衡二分木がマイブームで、平衡二分木にロリハ乗せればよさげなものができそうだと気づきました。

というわけなのでそのライブラリ整備の備忘録です。ちなみに、理論的な部分は多く語れません。（例えば、Splay Treeの計算量とか、なんでそうなるかは全くわかってない）
実装記録だと思ってください。

Rolling Hash

Rolling Hashについてはだいたいわかっているものとしますが、この記事では文字列 $s _ 0 s _ 1 s _ 2 ... s _ {N-1}$ とある基数 $b$ 、法 $M$ を用いて、以下の式で表されたハッシュ値を導くアルゴリズムということにします。

$(b ^ {N-1} s _ 0 + b ^ {N - 2}s _ 1 + b ^ {N - 3}s _ 2 + ... + bs _ {N - 2} + s _ {N-1}) \bmod M$

法 $M$ にはクソデカなメルセンヌ素数を使うと良いとか、基数はランダムなほうが良いとか、色々ありますが、この記事ではそんな重要な話ではないので割愛です。（「安全で爆速なRollingHashの話」とかググると良いでしょう）

文字列全体のハッシュ値は以上のように計算できるわけですが、部分文字列のハッシュ値を切り抜きたくなることもあるでしょう。
例えば $s _ l s _ {l+1} s _ {l+2} ... s _ {r - 1}$ を切り抜くときは、以下のような値を導出したいわけです。

$b ^ {r - l} s _ l + b ^ {r - l - 1} s _ {l + 1} + b ^ {r - l - 2} s _ {l + 2} + ... + s _ {r - 1}$

長さが $r - l$ に変わったので、初項の基数の肩に乗る指数も $r - l$ になっています。
これを計算する方法としては、メモとして $s[0..i$ ]のハッシュ値を $i$ 番目とする配列( $memo$ とする)を持っておき、

$memo _ {r - 1} - memo _ {l - 1} b ^ {r - l + 1}$

とすることで可能です。お気持ちとしては、 $memo _ {l - 1}$ の $s _ {l - 1}$ の項の基数は $1$ で、上の式からもわかる通り $memo _ {r - 1}$ の $s _ {l - 1}$ の項の基数は $b ^ {r - l + 1}$ なので、基数を合わせて引き算すれば $l - 1$ 項目より前はゴッソリなくなりそうだなと思えそうです。

1点更新できるRolling Hash

先述のようなRolling Hashで1点更新を行うとすると、 $memo$ の再構築が必要です。
例えば、 $s _ 0$ を $t$ に変えたいとすると、 $s _ 0$ は $memo _ 0$ では $s _ 0$ として、 $memo _ 1$ では $bs _ 0$ として、 $memo _ i$ では $b ^ {N - 1 - i} s _ i$ として足されているので、それぞれを引いたうえで $t$ , $bt$ , $b ^ {N - 1 - i} t$ を足しなおす、などとしなくてはなりません。このままでは無理筋なので何とかしようと考えると、真っ先に思い浮かぶものにセグメント木があります。

セグメント木に乗せる方法は色々あるかもしれないですが、私が思いついた方法は、区間がカバーする部分文字列のハッシュ値と最高次の基数を乗せる方法です。

最下段の $i$ 番目のノードでは、 $s _ {i}$ 1文字分のハッシュ値と、最高次の基数 $1$ を持てば良いです。
内部のノードでは子ノードの値を用いて集約値を計算する必要がありますが、親と左右の子の(ハッシュ値、基数)のペアをそれぞれ $(H _ p, B _ p), (H _ l, B _ l), (H _ r, B _ r)$ と表すと、

$(H _ p, B _ p) = (H _ {l}B _ {r}b + H _ {r}, B _ {l}B _ {r}b)$

となります。左の子の最低次の基数は $1$ で、これを右の子の最高次の基数 $B _ r$ より次数1個分大きくしないといけないので、左の子のハッシュ値に $B _ {r}b$ をかけて右の子のハッシュ値と足せばよいです。

見てわかる通り演算は可換じゃないので、ちょっと具体的には思いつかないですが演算が可換なことを前提にした雑な実装をしていたりすると、破滅するかもしれないので気を付けたほうが良いでしょう。

これで1点更新可能なRolling Hashが出来たので、ABC331Fは撃破できます。

1点更新と反転ハッシュ取得可能なRolling Hash

これは簡単で、逆順のRolling Hashをもう1つ持てば良いです。ただ、反転は添え字でバグらせがちなので、できればデータ構造1つで殴りたいです。

これも簡単に解決可能で、セグ木のノード1つに正順序の計算結果と逆順序の計算結果の両方を持ち、逆順序の計算では先述の式の右辺の $l, r$ を反転させればよいです。
ようするに、こんな感じです。(modの計算はめんどくさいの省略です)

trait Monoid {
    fn id() -> Self;
    fn op(l: Self, r: Self) -> Self;
}

#[derive(Clone, Copy)]
struct Node {
    f: (u64, u64),
    r: (u64, u64),
}
impl Monoid for Node {
    fn id() -> Node {
        Node {
            f: (0, 1),
            r: (0, 1),
        }
    }
    fn op(l: Node, r: Node) -> Node {
        Node {
            f: (l.f.0 * r.f.1 * b + r.f.0, l.f.1 * r.f.1 * b),
            r: (r.r.0 * l.r.1 * b + l.r.0, r.r.1 * l.r.1 * b),
        }
    }
}

正順序のハッシュが欲しいときはNode.fを、逆順序のハッシュが欲しいときはNode.rを使えばよいです。

とはいっても構造体のサイズがバカでかくてちょっと嫌ですよね…計算で逆順を計算できたりするのかなーなどと考えていたりしますが、今のところ解決法は見つかっていません。
まあパフォーマンス的に若干微妙かもしれませんが、致命的なほどではないはずです。

ちなみに、ここまでやると回文判定もおまけで可能になります。正順序のハッシュ値と逆順序のハッシュ値が一致しているか確かめればよいです（それはそう）。

1点更新挿入削除と任意の範囲の反転が可能なRolling Hash

これが本題です。もうお察しかと思われますが、平衡二分木に乗せます。私はSplay Treeしか書けないので、それに乗せました。

本当に乗せるだけで終わりなのですが、実装が雑だと普通に使い物にならないレベルで激遅なので、多少実装の工夫が必要です。

雑にSplayしまくらない

Splay木はとりあえずSplayしておけば一応それっぽくは動くのですが、Rolling Hashでは更新がとにかく重いです。雑にSplayしまくるとその分コストになってのしかかるので、用法用量は適切にすべきでしょう。

update (eval) の中の乗算の回数をとにかく減らす

反転可能にしているがゆえに、正順序、逆順序のハッシュと基数を持っていると思いますが、これの更新は割とカオスになりがちです。
なので別で関数やメソッドに起こしてキレイにしたくなるものですが、それによって乗算が増えてしまうとまたこれがコストになります。

基数は2つ持つ必要はない

正順だろうが逆順だろうが、集約値の基数の最高次数は変わりません。
基数の更新のために乗算が増えますし、メモリも無駄なので、ノードで基数を2つ持つ必要はないです。これは1点更新と反転ハッシュ取得可能なRolling Hashでも同様です。

update (eval) の呼び出し回数を最適化する

これです。エッ！？平衝二分木の update, push (eval, propagate) のタイミングがわからないですって？フッフッフ…… #競技プログラミング - Qiita

実のところめちゃくちゃ重要で、これが一番性能への影響が強かったです。
部分木の回転の際、根が正しく集約値を持っていることが保証できるなら、新しい根には元の集約値をそのまま代入しても結果は変わりません。これによってupdate (eval) の呼び出し自体を減らすことができます。

私が実装した限り、update (eval) は最悪8回程度の乗算を必要とするので、これが丸ごと消えるのは大きいです。

雑にメモリ確保しない（未実装・未検証）

未検証なのですが、雑にメモリ確保しているとキャッシュミス連発でひどいことになっているかもしれないなーなどと考えたりしています。
回避法としては、グローバルに大きめのVecを確保して、そこにノードを固めて置いておくとかが考えられそうです。

とはいっても、RustだとグローバルにVecを確保すると必然的にthread_local!+RefCellやstatic+Mutexのお世話になるわけで、そのアクセスコストとどっちがマシなのよっていう疑問もあり、実装も面倒なので、まあこのままでいいかなとも思っています。

実装例

これです。

https://github.com/tayu0110/tayu-procon/tree/master/string/src/rolling_hash

あとがき

ちょっと最後の方駆け足で雑になっちゃいましたが、まああんまり細かく書いてもな...という話なので、勘弁してください。（ちゃんと書くとほぼSplay Treeの実装記録になってしまう）

最初はちょっと大きめの制約ですぐTLEしてしまうダメな子だったのですが、工夫すればするほどどんどん性能が良くなるライブラリは作っていてとても楽しいです。ダメな子ほどかわいがりたくなるというやつかもしれません。

記事中や実装例で嘘が書いてあるのを見つけた方は、ぜひお教えください。

競プロ備忘録

競プロerの備忘録

なんでもできるRollingHashを作りたい