1. 質問
長さ n の動的な度数分布表があります。各位置の値は頻繁に増加し、システムは累積和、区間和を計算し、累積重みの k 番目の単位が含まれる位置を特定する必要があります。O(log n) での点更新と累積和クエリを持つ Fenwick Tree（Binary Indexed Tree）を実装し、単純な累積和配列やセグメント木と比較してください。
2. 制約と明確化事項
- 内部的には 1-based のインデックス付けを使用します。パブリック API は 0-based の位置を受け取っても構いませんが、変換は正確に 1 回だけにします。
- 更新は差分（デルタ）または新しい値との差分とします。負の値が許可されるかどうかを明記してください。
- 順位は 1 から始まります。重み付き選択は、すべての重みが非負であり、合計が少なくとも
kである場合にのみ定義されます。 - まずはシングルスレッドの構造について説明してください。並行更新にはロックやシャーディングが必要であり、通常の整数書き込みが一貫したスナップショットを形成するとは想定できません。
3. コアのアイデア
エントリ i は、長さが lowbit(i) = i & -i である連続区間の合計を格納します。累積和クエリは lowbit を繰り返し引き、点更新は lowbit を繰り返し加算するため、それぞれ O(log n) 個の配列要素にアクセスします。区間和は 2 つの累積和の差です。初期配列が既知の場合、各値をその親インデックスに伝播させることで O(n) で構築できます。
4. 参照実装
class Fenwick:
init(values):
tree = [0] * (len(values) + 1)
for i from 1 to len(values):
tree[i] += values[i - 1]
parent = i + lowbit(i)
if parent < len(tree):
tree[parent] += tree[i]
add(index0, delta):
i = index0 + 1
while i < len(tree):
tree[i] += delta
i += lowbit(i)
prefixSum(index0Exclusive):
total = 0
i = index0Exclusive
while i > 0:
total += tree[i]
i -= lowbit(i)
return total
rangeSum(left0, right0Exclusive):
return prefixSum(right0Exclusive) - prefixSum(left0)重み付き選択では、最も高いバイナリステップから探索します。候補インデックスに移動しても累積和が k 未満のままである場合、そのステップを採用してその合計を k から減算します。最終的なインデックスに 1 を加えたものが、順位 k を含む位置になります。これには累積和が単調増加であることが必要であり、負の重みがある場合には直接使用できません。
5. 計算量とトレードオフ
Fenwick Tree は O(n) の配列を使用します。点加算、累積和、重み付き選択は O(log n) であり、線形構築は O(n) です。セグメント木よりもコンパクトで定数倍が小さいことが多いですが、区間最小値、複雑な区間更新、リッチなセグメントメタデータではなく、可逆的な累積集約を自然に表現します。読み取り専用データの場合、単純な累積和配列は O(1) でクエリに応答します。Fenwick Tree は更新が頻繁に行われる場合に価値を発揮します。
6. 検証とオブザーバビリティ
- 空、要素数 1、最後のインデックスのケースを含むランダムな入力で、すべての
add、prefixSum、およびrangeSumを単純な配列と比較します。 - すべてゼロ、非常に大きな重み、合計が
kと完全に一致する場合、範囲外のk、および無効なインデックスをテストします。 - 線形構築を反復的な点加算とクロスチェックし、内部配列とクエリ結果の両方を比較します。
- 重み付き選択のために非負のランダムな重みを生成し、すべての
kについてプレフィックス境界を確認します。負の重みの入力は別途拒否します。
7. よくある間違い
- 0-based と 1-based のインデックスを混同し、位置 0 がスキップされたり、最後の位置でオーバーフローしたりする。
i & -iが最下位のバイナリブロックを抽出することを説明せずに、単なる否定のトリックとして扱う。- 累積和が単調でなくなるにもかかわらず、負の値で重み付き選択を使用する。
- 更新パスに沿って差分を加算するのではなく、ツリーノードを新しい値で上書きしてしまう。
8. 面接の評価ポイント
lowbit と区間カバー範囲を説明しているか
候補者は、各ノードがどの連続区間を格納しているか、およびクエリと更新がなぜ lowbit のジャンプに従うのかを説明できる必要があります。
境界エラーのない実装を作成しているか
回答は内部で 1-based のインデックスを維持し、空の配列、無効な位置、半開区間を適切に処理し、配列の末尾を超えてアクセスしないようにする必要があります。
計算量と構築法を導出しているか
候補者はクエリ、更新、選択のコストが O(log n) であること、線形構築が O(n) であることを示し、累積和配列やセグメント木との境界条件を比較できる必要があります。
重み付き選択の前提条件を認識しているか
回答では非負の重みと単調な累積和を前提条件とし、完全一致、オーバーフロー、大きな数値の境界をテストする必要があります。