AIで解説 AtCoder攻略　Fenwick木・セグメント木

Fenwick木・セグメント木ページの位置づけ

項目	内容
必修度	重要
学習目安	標準〜発展
前提	配列・座標圧縮
対象問題	81問（推定値あり81問、未算出0問）

この記事のdifficulty区分は、問題を解く順番を決めるための目安です。AtCoderの公式なA〜F区分ではなく、取得できたdifficulty推定値を次の範囲に分けています。

学習目安	difficulty推定値	問題数
入門	difficulty < 0	10
標準	0〜799	19
標準〜発展	800〜1199	15
発展	1200以上	37
未算出	—	0

更新と区間問い合わせを、毎回の全走査から対数時間へ下げます。Fenwick木・セグメント木・遅延伝播・順序付き集合を、操作の種類で選びます。

問題ごとの細かな実装は異なりますが、最初に確認する条件は共通しています。

Fenwick木・セグメント木の見分け方

要素の更新と区間の合計・最大値を交互に処理する
クエリ数が多く、1回の全走査が間に合わない
区間を分割して部分結果を再利用できる

Fenwick木・セグメント木の実装前チェック

更新と問い合わせの計算量を表にする
半開区間か閉区間かを統一する
遅延値を子へ下ろすタイミングを確認する

先に確認する文法・ライブラリ

まずは必須Python文法で、入力・配列・条件分岐・ループなどの基本を確認してください。問題に合わせたキュー、ヒープ、二分探索などの選び方は標準ライブラリ・定石にまとめています。

代表問題で実装を確認する

最初の一問として、ABC235 C The Kth Time Query（公式解説）を解きます。値ごとに出現位置をリストへまとめておけば、K回目の位置を添字で取り出せます。クエリごとに配列全体を走査しません。

N, Q = map(int, input().split())
A = list(map(int, input().split()))
positions = [[] for _ in range(N + 1)]
for index, value in enumerate(A, start=1):
    positions[value].append(index)

for _ in range(Q):
    X, K = map(int, input().split())
    if len(positions[X]) < K:
        print(-1)
    else:
        print(positions[X][K - 1])

位置の前処理O(N)、各クエリO(1)で、全体O(N+Q)です。毎回左から数えるO(NQ)より効率的です。

Fenwick木・セグメント木の学ぶ順番

このページでは全件を一度に並べず、difficultyの推定値を目安に代表問題を段階分けしています。難易度が未算出の問題は、制約と出題意図を先に確認します。

まず解く

問題	公式解説	出題意図	difficulty
ABC353 A Buildings	公式解説	Official editorial intent is classified as first greater.	-1018
ABC286 A Range Swap	公式解説	指定された2区間の要素を入れ替える。	-640
ABC283 B First Query Problem	公式解説	Answer point-value queries and apply point additions to the array.	-578
ABC245 B Mex	公式解説	0からNまでの集合を確認し、最初に存在しない非負整数を出力する。	-523
ABC340 B Append	公式解説	Official editorial intent is classified as sequence append query.	-494

次に解く

問題	公式解説	出題意図	difficulty
ABC367 A Shout Everyday	公式解説	Official editorial intent is classified as shout range.	-492
ABC457 B Arrays	公式解説	Process the two arrays and answer each requested relation.	-478
ABC453 B Sensor Data Logging	公式解説	Log sensor events and answer range aggregate queries.	-442
ABC468 B Corridor Watch	公式解説	Sweep corridor intervals and detect when the watch is obstructed.	-388
ABC271 B Maintain Multiple Sequences	公式解説	Store multiple sequences and answer each sequence/index lookup directly.	-166

挑戦問題

問題	公式解説	出題意図	difficulty
ABC420 C Sum of Min Query	公式解説	公式Editorialの方針を range min query として整理する。	56
ABC366 C Balls and Bag Query	公式解説	Official editorial intent is classified as bag multiset query.	80
ABC411 C Black Intervals	公式解説	公式Editorialの方針を black interval sweep として整理する。	185
ABC235 C The Kth Time Query	公式解説	値ごとに出現位置リストを保存し、K番目の位置をリストからO(1)で参照する。	210
ABC442 D G. Swap and Range Sum	公式解説	Maintain range sums while applying swaps with a lazy/point-update structure.	276