はじめに
Atcoderの典型90問の遅延評価セグメントツリーの実装のgindex (特に補数操作) が分からなかったので考えてみた。
元問題: Long Bricks
躓いた部分
# https://github.com/ryusuke920/kyopro_educational_90_python/blob/main/solve_python/029.py
# l34 ~ l48
def gindex(self, l, r):
l += self.num
r += self.num
lm = l >> (l & -l).bit_length()
rm = r >> (r & -r).bit_length()
while l < r:
if l <= lm:
yield l
if r <= rm:
yield r
r >>= 1
l >>= 1
while l:
yield l
l >>= 1
セグメントツリーを知らない僕はこのインデックス取得関数の意味が分からなかった。セグメントツリーについて調べてみたところ (Segment Tree のお勉強(2)) 、どうやら底辺のクエリを指定した時に、対応する上方の区間を出力するイテレータとして機能しているようであった。
コードでは、区間[l, r)とし、上図のピンク色のブロックを順に出力するための関数であると考えられる。以下、コードの上からレビューする。
1. lm = l >> (l & -l).bit_length() について
rm = r >> (r & -r).bit_length() も同様。そもそも、x & -x は何を表しているのだろうか？2の補数とは？2の補数の計算方法と表現範囲をわかりやすく解説！1の補数との違いは？ によると、x & -x は、xを２進数で表したものと、そのビットを反転させて、1を足したもののビット積である。以下4ビットの場合の例を挙げる。
- 例 x = 1 の時
xは0001、-xは負の数なので4ビット目は1。3ビット目を1に2ビット目を1に、1ビット目を0に反転させて1110。これに1を加えて、1111。各ビット位が共に1である部分に着目して、x & -xは0001。よって、10進数に戻すと x & -x = 1
同様に
- x = 2 の時
xは0010, -xは1110, x & -x は0010。よって、x & -x = 2。 - x = 3 の時
xは0011, -xは1101, x & -x は0001。よって、x & -x = 1。 - x = 4 の時
xは0100, -xは1100, x & -x は0100。よって、x & -x = 4。 - x = 5 の時
xは0011, -xは1101, x & -x は0001。よって、x & -x = 1。 - x = 6 の時
xは0110, -xは1010, x & -x は0010。よって、x & -x = 2。 - x = 7 の時
xは0111, -xは1001, x & -x は0001。よって、x & -x = 1。 - x = 8 の時
xは0100, -xは1100, x & -x は0100。よって、x & -x = 8。
ビットの反転操作により、0と1の値が反転してしまうが、その後に1が加わるため、繰り上がりが起こり、反転前と同じ位で1になるような場所が生まれる。一般化すると、ある数 x をビット表記をした時に、右側から数えて初めて1になるような位が右からN番目の位であるとする。これを反転させた時、N番目の数は0となり、N番目より右側は1が連続し、N番目より左側は各位反転された数が連続する。これに1を加えると、繰り上がりが発生しN番目より右側は0となり、N番目は1となりここで繰り上がりが止まる。したがって、元の数のビットと比較するとN番目の位の数のみが共に1となる。よって、x & -x = 2 ^ (N-1) である。
「ビット表記をした時に、右側から数えて初めて1になるような位が右からN番目の位である」ような数は、10進数において、[奇数]× 2^(N-1) の形で表せられる数である。x & -x = 2 ^ (N-1) より、x & -x は x を奇数と2の累乗数で因数分解した時の2の累乗数を表している。
再びlm = l >> (l & -l).bit_length()に戻って考える。(l & -l).bit_length() はl & -l のビット長、つまり上の説明で言うところのN-1である。N-1 だけ l のビットを右にシフト (>>) するということは、2^(N-1)で割ることと同義であり、lm は[奇数]× 2^(N-1)と因数分解したときの[奇数]を表している。言い換えると l を2で割っていって最初たどり着く奇数である。
2. while l < r:及びwhile l:
yieldというのはreturn同様返り値の出力であるが、yieldはイテレータとして働き、呼び出され代入をする度にwhile文が回転し新しい値を出力する。if l <= lm: という条件により、無駄な出力を防いでいる。
上図のように、左側に (l) については奇数を、右側 (r) については、偶数を出力しなくてはならないはずである (l:45,23,3 r:38,18,8)。これについては、イテレータを受け取った後に -1 など処理することで帳尻を合わせている。
最後に
これからも遅延セグ木について詰まったら記事に追加していく。