AIで解説 AtCoder攻略　データ構造（range-queryへ統合・legacy）

データ構造ページの位置づけ

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

データ構造の見分け方

文法の意味が曖昧な場合は必須Python文法へ戻ります。ライブラリの使い方は標準ライブラリ・定石で確認します。

データ構造の学ぶ順番

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

まず解く

問題	公式解説	出題意図	difficulty
ABC283 B First Query Problem	公式解説	Answer point-value queries and apply point additions to the array.	-578
ABC453 B Sensor Data Logging	公式解説	Log sensor events and answer range aggregate queries.	-442
ABC271 B Maintain Multiple Sequences	公式解説	Store multiple sequences and answer each sequence/index lookup directly.	-166
ABC442 D G. Swap and Range Sum	公式解説	Maintain range sums while applying swaps with a lazy/point-update structure.	276
ABC462 C Not Covered Points	公式解説	Sort intervals and count integer points not covered by any interval.	282

次に解く

問題	公式解説	出題意図	difficulty
ABC278 C FF	公式解説	Store follows as ordered pairs and answer whether both directed pairs exist.	320
ABC199 C IPFL	公式解説	Handle swaps within or across halves with an offset flag, applying the offset only when needed.	436
ABC256 D G. Union of Interval	公式解説	区間を左端順に並べ、重なる区間を併合して出力する。	546
ABC314 D G. LOWER	公式解説	Apply lowercase updates to intervals and answer final character values.	585
ABC320 D G. Relative Position	公式解説	Propagate coordinate differences through a graph and answer relative positions.	873

挑戦問題

問題	公式解説	出題意図	difficulty
ABC330 E H. Mex and Update	公式解説	Maintain the mex of an array under point updates with counts and an ordered set.	1004
ABC466 E Range Flip	公式解説	Apply range flips and maintain the requested aggregate.	1027
ABC444 E H. Sparse Range	公式解説	Answer sparse range updates and minimum queries with a segment tree.	1107
ABC273 D G. LRUD Instructions	公式解説	Store walls by row and column and jump to the nearest wall for each LRUD command.	1119
ABC438 E H. Heavy Buckets	公式解説	Process heavy-bucket operations with lazy range updates and point queries.	1226

問題文を読んだら、まず「見分け方」のどれに当たるかを一行で記録します。当てはまらない問題は、別のページへ移す判断自体を復習材料にします。

データ構造の次に読むページ

累積和で区間と差を数える、ヒープとイベント掃引で順序を管理する、木と連結成分を走査する

この下書きは分類再編前の旧版です。区間更新・問い合わせは「Fenwick木・セグメント木」ページへ統合しました。公開対象外として保管します。

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

ABC283 B First Query Problem（公式解説）で、配列の一点参照と一点更新を確認します。

N = int(input())
A = list(map(int, input().split()))
Q = int(input())

for _ in range(Q):
    query = list(map(int, input().split()))
    if query[0] == 1:
        _, k = query
        print(A[k - 1])
    else:
        _, k, x = query
        A[k - 1] = x

各クエリをO(1)で処理するため、全体の計算量はO(Q)です。毎回配列全体を探し直さず、添字で直接アクセスします。