はじめに
$T[1 \ldots N]$の文字列の任意の範囲$(j, k)$の要素に指定した文字$c$を書き込む（$T[i] \leftarrow c$ for $j \leq i \leq k$)、文字列の範囲書き込み問題を考えます。
例：領収書の都合の悪い部分を黒塗りにする
愚直に行えば$k-j+1$個の要素の書き込みが必要、かつ範囲長の最大は$N$なので$O(N)$時間かかります。
範囲書き込みが稀であれば問題ありませんが、頻繁に起こる場合はこの書き込みにかかる時間がボトルネックになってしまいます。ここでは読み書きにかかる時間を少し犠牲にし、範囲書き込みをより高速にかつ省領域に行えるアルゴリズムをご紹介します。
正確には各操作を以下の時間で文字列$T$に加え$N-1$bitsの追加領域で実現します。
| 読み込み | 書き込み | 範囲書き込み | 全体書き込み |
|---|---|---|---|
| $O(\log N)$ | $O(\log N)$ | $O(\log N)$ | $O(1)$ |
範囲書き込みアルゴリズム
大まかなアイディア
大雑把なアイディアを説明するとセグメント木（知らない方はこちらを参照）で$T$の範囲要素の書き込み状態を管理します。ここでセグメント木の各葉は$T$の各要素に対応します。各部分木の葉全てが範囲書き込みで同じ文字に書き込まれている場合、その部分木の頂点をマークし、その時の書き込み文字を一緒に覚えておきます。このようにすることで全ての要素を実際に書き込むこと無く、書き込んだことにします。
セグメント木の表現
より具体的なお話しをします。
セグメント木の各内部ノード$u$は$flag$の1-bit持ち、$flag=1$の場合$u$の部分木は全て範囲書き込みで書き込まれているものとします。また、書き込まれた要素はその部分木の最左の葉に対応する$T[i]$に保存します。
以下の例ではセグメント木と、$T$の実際の状態、そしてこのデータ構造が表す文字列$T'$の状態を表しています。
空白の箇所は任意の値です。
ここで$T[1 \ldots 4]$、$T[5 \ldots 6]$の範囲がそれぞれマークされており、それぞれの最左の葉に$\mathrm{a}$が保存されています。一方$T[7]$、$T[8]$はマークされておらず、それぞれ$\mathrm{b}$、$\mathrm{a}$が保存されています。
このことからこのデータ構造が表す文字列は$T'=\mathrm{aaaaaaba}$となります。
またセグメント木の性質から以下のことが言えます。
- セグメント木の内部ノードは$N-1$個あるため、$N-1$ bitsで表現可能（葉は$flag$を持つ必要なし）
- セグメント木の高さは$O(\log N)$
- 各親子間の移動は$O(1)$で実行可能
- 部分木の最左要素へのアクセスは$O(1)$で実行可能。
各操作の実現
上記の表現上で各操作を如何に実現するかを説明します。
読み込み
$T[i]$を読む:
セグメント木のrootから順に辿り、$T[i]$に相当する葉まで遷移します。
途中でマークされたノード$u$に到達した場合、$T[i]$は範囲書き込みされているので、その書き込み文字である部分木$u$の最左要素を返します。
マークされたノードに到達せずに$T[i]$に相当する葉まで到達した場合には$T[i]$を返します。
高さ$O(\log N)$のセグメント木をrootから葉に辿るので計算時間は$O(\log N)$です。
書き込み
$T[i] \leftarrow c$:
セグメント木のrootから順に辿り、$T[i]$に相当する葉まで遷移します。
その際、途中でマークされたノード$u$に到達した場合には、それ以後辿った子ノードの$flag$を0にセットし、また辿らなかった子ノードを全てマーク（$flag$を1にセットし、最左要素を元々範囲書き込みで設定されていた値にセット）します。
$T[i]$に到達した後は$T[i] \leftarrow c$で書き込みを行います。
このようにすることで、既に範囲書き込みが行われている箇所の変更を最小限にとどめつつ所望の書き込みを行います。
木を辿る過程の各マーク操作は定数個の$flag$の書き換え、かつ最左要素へは$O(1)$でアクセスできるので、全体で$O(\log N)$時間で書き込み操作が完了します。
例：全体が$\mathrm{a}$の状態から$T[7] \leftarrow c$の書き込みを行う。
範囲書き込み
$T[i] \leftarrow c$ for $j \leq i \leq k$:
基本的に書き込み操作とほぼ同じです（そもそも書き込みは範囲書き込みの特殊ケースなので）。
範囲書き込みのためにマークしなくては行けない部分木の数は$O(\log N)$です。この部分木は$T[j]$と$T[k]$までのパスで囲まれた木になります。ですので、$T[j]$と$T[k]$に至るまでは書き込み操作と同様に、既に範囲書き込みが行われているマークノードを最小限に変更しつつ、新しく書き換える部分木をマークしていきます。
書き込みと同様計算時間は$O(\log N)$時間です。
例：全体が$\mathrm{a}$の状態から$T[i] \leftarrow b$ for $2 \leq i \leq 6$の書き込みを行う。
$T[2]$と$T[6]$に至るパスに囲まれた部分木、$T[2]$、$T[3 \ldots 4]$、$T[5]$、$T[6]$の書き込みを行う。
全体書き込み
$T[i] \leftarrow c$ for $ 1\leq i \leq N$:
範囲書き込みと同様の操作で実現します。特別に項目を分けたのはこの全体書き込みだけを扱った問題も存在するからです。全体書き込みの場合木を辿る操作が必要ない（rootノードをマークするだけ）なので、計算時間は$O(1)$時間です。
おわりに
今後の課題ですが、各種操作は工夫すれば$O(\log N)$から$O(\log \log N)$当たりに改善できるのではと思っています。しかし、具体的な方針などは全く考えていません。元気がある人はぜひ取り組んでみて下さい。