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

問題

非負整数からなる長さ $N$ の数列 $a_1,\dots,a_N$ に対し、$Q$ 個のクエリを処理せよ。

• 1 i x: $a_i$ に $x$（非負整数）を加算
• 2 X: $a_1+\dots+a_k \ge X$ となる最小の $k$ を出力（存在しなければ $-1$）

入出力例

5 4
1 2 3 4 5
2 6
1 1 10
2 6
2 100

3
1
-1

初期累積和 1,3,6,10,15 → k=3。更新後 11,13,16,20,25 → k=1。総和25なので100は達成不可。

概念図: 上位ビットから貪欲に降りる探索

ヒント

LOG = n.bit_length()
def find(x):
    pos, rem = 0, x
    for level in range(LOG, -1, -1):
        nxt = pos + (1 << level)
        if nxt <= n and tree[nxt] < rem:
            pos = nxt
            rem -= tree[nxt]
    return pos + 1  # n を超えたら -1

模範解答

import sys

def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    q = int(data[idx]); idx += 1
    a = [0] + [int(x) for x in data[idx:idx + n]]; idx += n

    tree = [0] * (n + 1)

    def update(i, x):
        while i <= n:
            tree[i] += x
            i += i & (-i)

    for i in range(1, n + 1):
        update(i, a[i])

    LOG = n.bit_length()

    def find(x):
        pos = 0
        rem = x
        for level in range(LOG, -1, -1):
            nxt = pos + (1 << level)
            if nxt <= n and tree[nxt] < rem:
                pos = nxt
                rem -= tree[nxt]
        pos += 1
        return pos if pos <= n else -1

    out = []
    for _ in range(q):
        t = data[idx]; idx += 1
        if t == b'1':
            i = int(data[idx]); idx += 1
            x = int(data[idx]); idx += 1
            update(i, x)
        else:
            x = int(data[idx]); idx += 1
            out.append(str(find(x)))

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

solve()

計算量: 構築 $O(N)$、各クエリ $O(\log N)$、全体 $O((N+Q)\log N)$。

Step-by-Step 解説

Step 1: 通常の BIT 構築・点更新

標準の Fenwick Tree の update で加算値を反映。

Step 2: tree[i] が担う区間の性質

tree[i] は区間 $(i-\text{lowbit}(i), i]$ の和。この構造がビット降下探索の土台になる。

Step 3: 上位ビットからの貪欲降下

pos=0 から出発し、level を大きい方から動かして、区間和が残り目標 rem 未満ならジャンプする。厳密な <（未満）判定が境界を飛び越さないポイント。

Step 4: 答えの確定

pos は「累積和が x 未満である最大の添字」。答えは pos+1、$N$ を超えたら $-1$。

よくあるミス

次のステップ

• 発展問題: BIT上二分探索を使った動的 MEX 計算
• 発展問題: 座標圧縮後の「$k$番目に小さい生存要素」クエリ

自己評価