セグメント木に変なものを乗せる

この記事は、「木 Advent Calendar 2023」の14日目です。
昨日の記事はそすうぽよさんの「木曜日」でした。
明日の記事は箱さんの「なにか書きます」です。

セグメント木

ご存知のとおり、セグメント木は大変便利なデータ構造です。配列と同じようなランダムアクセスによる要素の取得・書換えが $O(log⁡N)O(\log N)$ でできるほか、ある区間を選び二項演算を適用した結果を得る操作も $O(log⁡N)O(\log N)$ でできます。

しかし、そんなセグメント木にも大きな欠点があります。それは、要素と二項演算がモノイドの関係になっていなければ、正しい答えを得ることができない、ということです。

そこで、本記事では、変なものふたつについて、セグメント木に乗せたいときにどうすればよいかを show time.

変なものの一覧

$1010$ 進数

数字からなる長さ $NN$ の配列に対して、以下の二通りのクエリを処理しなければならない状況を想定してみます。

• $ii$ 番目の数字を $x (0≤x≤9)x\ (0 \le x \le 9)$ に置き換える。
• $ll$ 番目から $rr$ 番目の数字を $1010$ 進法表記の数とみなし、 $998244353998244353$ で割ったあまりを出力する。

直感的には、二項演算として $x∗y=10x+yx * y = 10x + y$ を採用すればよさそうに思えます。
しかし、これはうまくいきません。

なぜなら、これはモノイドが満たすべき性質である結合律を満たさないからです。
たとえば、 $(x∗y)∗z=100x+10y+z(x * y) * z = 100x + 10y + z$ ですが、他方で $x∗(y∗z)=10x+10y+zx * (y * z) = 10x + 10y + z$ となります。

そこで、 $ii$ 番目の要素は最初から $10N−i−110^{N - i - 1}$ をかけておき、二項演算としては $x∗y=x+y mod 998244353x * y = x + y \bmod 998244353$ を採用するとします。
こうすればモノイドになります。

$ii$ 番目の数字を $xx$ で置き換えるときは、セグ木の $ii$ 番目の要素に $10N−i−1x10^{N - i - 1} x$ を代入します。
$ll$ 番目から $rr$ 番目の数を取得するときは、その答えに $10r−N mod 99824435310^{r - N} \bmod 998244353$ を掛けます。

括弧列

長さ $NN$ の (, ) のみからなる文字列に対し、以下の二通りのクエリを処理しなければならない状況を想定してみます。

• $ii$ 番目の文字を $c (c∈{(,)})c\ (c \in \{\texttt{(}, \texttt{)}\})$ に置き換える。
• $ll$ 番目から $rr$ 番目の文字を括弧列として見たとき、「対応の取れた括弧列」であるか判定する。

この問題は、以下のようにして解くことができます。

• ( の値を $(0,1)(0, 1)$ とする。
• ) の値を $(1,0)(1, 0)$ とする。
• 二項演算を $(a,b)∗(c,d)=(a+max⁡{c−b,0},max⁡{b−c,0}+d)(a, b) * (c, d) = (a + \max\{c - b, 0\}, \max\{b - c, 0\} + d)$ とする。
• 値が $(0,0)(0, 0)$ になる文字列は「対応の取れた括弧列」である。

たとえば、 () の値は $(0,0)(0, 0)$ となり、 )( の値は $(1,1)(1, 1)$ となります。