Day 135-Q5 | Fenwick Tree上の二分探索（BIT Binary Search）

問題

初期状態で空の多重集合がある。$1$から$N$までの整数値のみを要素として持つ。次の3種類のクエリを$Q$個、順番に処理せよ。

1 x : 値$x$を1個追加する。
2 x : 値$x$を1個削除する（存在保証）。
3 k : $k$番目に小さい値を出力する。存在しなければ-1。

すべて$O(\log N)$で処理せよ（Fenwick Tree上の二分探索によるビット降下法を用いること）。

入力形式

N Q
query_1
...
query_Q

制約

$1 \le N,Q \le 2\times10^5$

クエリ1,2: $1\le x\le N$

クエリ3: $1\le k\le Q$

入出力例

入力例1

出力例1

1
3
3

概念図

ヒント（段階的開示）

ヒント1（方向性）

「$k$番目に小さい値」を求める操作は、頻度配列の累積和が初めて$k$に達する位置を探す問題と同じ。BITの二進木的な内部構造を利用すると、根から二分探索的に降りていくことができる。

ヒント2（アプローチ）

通常のBITのadd/sumに加え、find_kth関数を実装する。$N$以下の最大の2べきから始め、現在位置に$2^j$を足した位置の値がkより小さいならそこまで進んでkから引く、そうでなければ進まない、をビットを大きい方から試す。

ヒント3（誘導）

このロジックが正しく動くのは、tree[pos+2^j]が「区間$(\text{pos},\text{pos}+2^j]$の和」を正確に表しているというBITの内部構造そのものによる。

def find_kth(bit_tree, n, k):
    pos = 0
    for j in range(n.bit_length(), -1, -1):
        nxt = pos + (1 << j)
        if nxt <= n and bit_tree[nxt] < k:
            pos = nxt
            k -= bit_tree[nxt]
    return pos + 1

模範解答 (Python)

import sys


class FenwickBinarySearch:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)
        self.log_n = n.bit_length()

    def add(self, pos, val):
        while pos <= self.n:
            self.tree[pos] += val
            pos += pos & (-pos)

    def find_kth(self, k):
        pos = 0
        remaining = k
        for j in range(self.log_n, -1, -1):
            nxt = pos + (1 << j)
            if nxt <= self.n and self.tree[nxt] < remaining:
                pos = nxt
                remaining -= self.tree[nxt]
        result = pos + 1
        if result > self.n:
            return -1
        return result


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

    fbs = FenwickBinarySearch(N)
    out = []

    for _ in range(Q):
        t = int(data[idx]); idx += 1
        if t == 1:
            x = int(data[idx]); idx += 1
            fbs.add(x, 1)
        elif t == 2:
            x = int(data[idx]); idx += 1
            fbs.add(x, -1)
        else:
            k = int(data[idx]); idx += 1
            res = fbs.find_kth(k)
            out.append(str(res))

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


main()

Step-by-Step 解説

1BITの内部構造の再確認
ノードtree[i]は$i$の最下位ビットの大きさに応じて区間$(i-\text{lowbit}(i),i]$の和を保持している。

2二分探索への転用
find_kthは現在位置から$2^j$進んだ先までの和が残り必要数未満なら実際に進む、を二進数の桁を上から確定させる操作として行う。

3jの範囲
log_n=n.bit_length()として$2^{\log_n}\ge N$を保証し、nxt<=nで範囲外をスキップする。

4答えの復元
ループ終了後のposは「累積和がk未満である最大の位置」を表すので答えはpos+1。範囲外なら-1。

5addとの整合性
add(x,1)で追加、add(x,-1)で削除。通常の点更新BITと同一実装。

よくあるミス

ミス	原因	正しい書き方
find_kthの判定を<=にする	1つ多く進んでしまう	厳密に<で判定する
log_nをN未満に設定	最上位ビットを見落とす	n.bit_length()で十分大きいビット数を確保する
削除の存在保証を信じず余計なチェックを入れる	過剰実装	要求されたクエリのみ実装しガードレール原則を守る
kが要素数を超える場合の処理漏れ	find_kthがpos末尾到達でも-1にならないことがある	全要素数とkを比較するか、残りが正なら-1を返す判定を入れる
0-indexedと混同	add(x-1,...)のように誤ってオフセット	Fenwick Treeは1-indexedが自然。値xをそのまま位置として使う

次のステップ

発展: 値の範囲が$10^9$などBITの配列サイズに収まらない場合、座標圧縮または動的セグメント木との組み合わせを検討せよ。
発展2: 「値$x$未満の要素数」を求めるrank操作も実装し、find_kthと整合することを確認せよ。
次回予告: 次回のテーマは今後のセッションで選定

自己評価

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

Day 135-Q5 — Fenwick Tree上の二分探索（BIT Binary Search）

問題