Day 145-Q3 | 簡潔ビットベクトル

問題

長さ $N$ の01文字列（ビット列）が与えられる。以下の2種類のクエリに答えよ。

`R i`：区間 $[0, i)$（0-indexed）に含まれる1の個数を出力せよ（`rank(i)`）。
`S k`：$k$ 番目（1-indexed）の1が出現する位置（0-indexed）を出力せよ（`select(k)`）。存在しない場合は `-1`。

ただし、以下の階層的ブロック前計算（Jacobson方式）を用いて `rank` を実装せよ。

ビット列を大きさ $B_1 = \lceil \log^2 N \rceil$ の「大ブロック」に分割し、各大ブロック開始位置までの1の個数（大ブロック前方和）を保持する。
各大ブロックをさらに大きさ $B_2 = \lceil \log N / 2 \rceil$ の「小ブロック」に分割し、大ブロック内での小ブロック開始位置までの1の個数（相対前方和）を保持する。
`rank(i)` は「大ブロック前方和」＋「小ブロック内相対前方和」＋「小ブロック先頭から$i$までのポップカウント」の和として計算する。

`select` は `rank` に対する二分探索で実装してよい。

入力形式

N Q
B
query_1
:
query_Q

制約

$1 \le N \le 200000$

$1 \le Q \le 200000$

クエリの $i$: $0 \le i \le N$

クエリの $k$: $1 \le k \le N$

入出力例

入力例1

出力例1

`10110100`の[0,5)区間には1が3個(位置0,2,3)。3番目の1は位置5。1は全部で4個なので5番目は存在せず-1。

概念図：階層的ブロック構造

ヒント（段階的開示）

ヒント1（方向性）

全体の累積和配列を前計算すれば`rank`は$O(1)$になるが、追加領域が$O(N\log N)$ビット必要になり簡潔（$o(N)$追加ビット）とは呼べない。ビット列を階層的に区切って前計算することで、テーブルサイズを情報理論的下限に近づけつつ$O(1)$クエリを実現する。

ヒント2（アプローチ）

「大ブロック」前方和は値域$O(N)$で$O(\log N)$ビット、個数$N/\log^2N$個 → 全体$O(N/\log N)$ビットで$o(N)$。「小ブロック」は大ブロック内の相対位置（値域$O(\log^2N)$）だけ保持すればよく$O(\log\log N)$ビット、個数$N/\log N$個 → 全体$O(N\log\log N/\log N)$ビットでこれも$o(N)$。最後の「残り」はポップカウントで直接数える。

ヒント3（誘導）

B1 = max(1, int(math.ceil(logn ** 2)))
B2 = max(1, int(math.ceil(logn / 2)))
big = [0] * (N // B1 + 2)
small = [0] * (N // B2 + 2)
acc_big = acc_small = 0
for i in range(N):
    if i % B1 == 0:
        big[i // B1] = acc_big
        acc_small = 0
    if i % B2 == 0:
        small[i // B2] = acc_small
    bit = 1 if bits[i] == '1' else 0
    acc_big += bit
    acc_small += bit

大ブロックと小ブロックの境界を跨ぐたびに`acc_small`をリセットする点に注意する。

模範解答 (Python)

import sys
import math

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    Q = int(data[idx]); idx += 1
    bits = data[idx].decode(); idx += 1

    logn = math.log2(N) if N > 1 else 1.0
    B1 = max(1, int(math.ceil(logn ** 2)))
    B2 = max(1, int(math.ceil(logn / 2)))

    num_big = N // B1 + 2
    num_small = N // B2 + 2
    big = [0] * num_big
    small = [0] * num_small

    acc_big = 0
    acc_small = 0
    for i in range(N):
        if i % B1 == 0:
            big[i // B1] = acc_big
            acc_small = 0
        if i % B2 == 0:
            small[i // B2] = acc_small
        if bits[i] == '1':
            acc_big += 1
            acc_small += 1
    big[N // B1] = acc_big if N % B1 == 0 else big[N // B1]

    def rank(i):
        if i <= 0:
            return 0
        if i >= N:
            i = N
        big_idx = i // B1
        r = big[big_idx]
        small_idx = i // B2
        small_start = small_idx * B2
        r += small[small_idx]
        for p in range(small_start, i):
            if bits[p] == '1':
                r += 1
        return r

    total_ones = rank(N)

    def select(k):
        if k <= 0 or k > total_ones:
            return -1
        lo, hi = 0, N
        while lo < hi:
            mid = (lo + hi) // 2
            if rank(mid + 1) >= k:
                hi = mid
            else:
                lo = mid + 1
        return lo

    out = []
    for _ in range(Q):
        t = data[idx].decode(); idx += 1
        v = int(data[idx]); idx += 1
        if t == 'R':
            out.append(str(rank(v)))
        else:
            out.append(str(select(v)))

    print('\n'.join(out))

main()

Step-by-Step 解説

1階層構造の設計
大ブロック幅$B_1=\lceil\log^2N\rceil$、小ブロック幅$B_2=\lceil(\log N)/2\rceil$とする。

2前方和テーブルの構築
1回のスキャンで大ブロック境界に到達するたびに`big`配列へ記録し`acc_small`をリセット、小ブロック境界では`small`配列へ相対値を記録する。$O(N)$の前計算。

3rank(i)のO(1)計算
「大ブロック前方和」＋「小ブロック内相対前方和」＋「小ブロック先頭から$i$までのポップカウント」の3項の和。ポップカウント部分は$O(\log N)$幅に収まるためハードウェアでは定数時間になる。

4select(k)の二分探索実装
`rank`の単調性を利用し`rank(mid+1)>=k`となる最小の`mid`を二分探索で求める。真に$O(1)$にするにはClark's select structureなど別構造が必要。

5領域計算量の確認
`big`は$O(N/\log N)$ビット、`small`は$O(N\log\log N/\log N)$ビット、いずれも$o(N)$で元の$N$ビットに対し漸近的に無視できる追加領域。

よくあるミス

ミス	原因	正しい書き方
`rank(N)`が範囲外アクセスになる	大ブロック配列末尾の境界チェックがない	配列を余裕を持って確保し(+2)、$i$が$N$を超えないようclampする
小ブロックの相対和を大ブロックごとにリセットし忘れる	累積和をグローバルに1本しか持たない設計	大ブロック境界に到達するたびに`acc_small=0`にリセットする
`select`の二分探索範囲を1-indexed/0-indexedで混同する	`rank(mid)`と`rank(mid+1)`の意味を取り違える	`rank(i)`は$[0,i)$の半開区間であることを明確にする
単純な累積和配列($O(N\log N)$ビット)を使い「簡潔」と誤称する	簡潔データ構造の定義($o(N)$追加ビット)を理解していない	階層的ブロック分割で追加領域を$o(N)$に抑えることが核心
ポップカウント区間の端点が1個分ずれる	`range(small_start, i)`の境界を誤る	`rank(i)`は$[0,i)$なので`small_start`から`i`(含まない)までを数える

次のステップ

発展: Clark's select structureを実装し、`select`も真に$O(1)$にせよ。
次回予告: Nagamochi-Ibarakiのスパース化（K-辺連結性証明書の構築）

自己評価

完全理解おおむね理解要復習

Day 145-Q3 — 簡潔ビットベクトル（Succinct Rank/Select・Jacobsonの階層的ブロック前計算）

問題