はじめに $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の追加領域で実現します。 読み込み 書き込み 範囲書き込み 全体書き込み 範囲書き込みアルゴリズム 大まかなア
![文字列の範囲書き込みを効率的に行うアルゴリズム - Qiita](https://cdn-ak-scissors.b.st-hatena.com/image/square/07fc86d059681293a117816e7dfef6e10284e63d/height=288;version=1;width=512/https%3A%2F%2Fqiita-user-contents.imgix.net%2Fhttps%253A%252F%252Fcdn.qiita.com%252Fassets%252Fpublic%252Fadvent-calendar-ogp-background-7940cd1c8db80a7ec40711d90f43539e.jpg%3Fixlib%3Drb-4.0.0%26w%3D1200%26mark64%3DaHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZ3PTk3MiZoPTM3OCZ0eHQ9JUU2JTk2JTg3JUU1JUFEJTk3JUU1JTg4JTk3JUUzJTgxJUFFJUU3JUFGJTg0JUU1JTlCJUIyJUU2JTlCJUI4JUUzJTgxJThEJUU4JUJFJUJDJUUzJTgxJUJGJUUzJTgyJTkyJUU1JThBJUI5JUU3JThFJTg3JUU3JTlBJTg0JUUzJTgxJUFCJUU4JUExJThDJUUzJTgxJTg2JUUzJTgyJUEyJUUzJTgzJUFCJUUzJTgyJUI0JUUzJTgzJUFBJUUzJTgyJUJBJUUzJTgzJUEwJnR4dC1hbGlnbj1sZWZ0JTJDdG9wJnR4dC1jb2xvcj0lMjMzQTNDM0MmdHh0LWZvbnQ9SGlyYWdpbm8lMjBTYW5zJTIwVzYmdHh0LXNpemU9NTYmcz03MDcyYWI2YmEwZmZkNjc0YmVjMmYyOWYwM2E3MzZlOA%26mark-x%3D120%26mark-y%3D96%26blend64%3DaHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZoPTc2Jnc9OTcyJnR4dD0lNDBrZ290byZ0eHQtY29sb3I9JTIzM0EzQzNDJnR4dC1mb250PUhpcmFnaW5vJTIwU2FucyUyMFc2JnR4dC1zaXplPTM2JnR4dC1hbGlnbj1sZWZ0JTJDdG9wJnM9ODQxMjdkYTBkMjhhZDIzMmJiYmViNzE4OGU1ZDhiMjE%26blend-x%3D120%26blend-y%3D500%26blend-mode%3Dnormal%26s%3D40a25bddea1e9726905871235ab47824)