区間クエリの手法は、問題文にある「何を更新するか」と「どの区間を何にまとめるか」で選びます。更新がなく、区間の合計を何度も求めるだけなら累積和。一点の値を加算して区間和を求めるならFenwick木。最大値・最小値や条件を満たす位置まで扱うならセグメント木が候補です。区間そのものを更新するなら、遅延評価セグメント木へ進みます。
先に結論：更新と集計を分けて考える
| 問題文で確認する条件 | まず考える手法 | 1回の処理の目安 | 追加メモリ |
|---|---|---|---|
| 更新なしで、区間の合計を繰り返し求める | 累積和 | 前計算後の問い合わせ O(1) |
O(N) |
| 一点に値を加え、区間の合計を求める | Fenwick木 | 更新・問い合わせ O(log N) |
O(N) |
| 一点を更新し、区間の最大値・最小値や条件成立位置を求める | セグメント木 | 更新・問い合わせ O(log N) |
O(N) |
| 区間を更新し、その後に区間を問い合わせる | 遅延評価セグメント木 | 問題の演算に応じて設計 | O(N)程度 |
この表は手法を機械的に決める規則ではありません。合計・最大値・最小値のどれを結合するか、更新が加算か代入か、答えが値なのか位置なのかを問題文で確かめてから選びます。このページではFenwick木とセグメント木の代表実装までを扱い、遅延評価と順序統計は別の境界として残します。
区間クエリの基本：半開区間を固定する
配列をPythonの0始まりで A[0], A[1], ..., A[N-1] と表し、区間を [l, r) と書きます。これは左端の l を含み、右端の r を含まない区間なので、要素数は r - l です。区間和は、累積和を prefix(k) = A[0] + ... + A[k-1] と定義すれば、prefix(r) - prefix(l) になります。
右端を含む問題の区間 [l, r] をこの形へ直すときは、右端を r + 1 にします。Fenwick木の代表コードとセグメント木の代表コードは、問い合わせの端点をこの半開区間で統一しています。入力が別の添字規則を採用する問題では、読み取った直後に変換し、内部で規則を混ぜないことが大切です。
- 更新の種類：一点への加算か、値の代入か、区間全体への更新か。
- 集計の種類：合計、最大値、最小値など、部分結果をどう結合するか。
- 答えの種類：集計値か、条件を満たす最初の位置か。
- 端点と単位元：空の部分結果を何として扱うか。
全走査が遅くなる理由
素朴な方法では、クエリのたびに A[l:r] を走査して合計や最大値を計算します。1回の区間が長ければ計算量は O(N) になり、Q回のクエリ全体で最悪 O(NQ) です。入力配列を除く追加メモリは O(1) ですが、クエリ数が多いと同じ要素を何度も読み直すことになります。
更新が一度もないなら、累積和をO(N)で作って各区間をO(1)で求めれば、全体はO(N + Q)です。一方で更新があると、更新位置より後ろの累積和を直し続ける必要があります。更新された部分だけに影響する情報を再利用するために、Fenwick木やセグメント木を使います。
一点加算と区間和ならFenwick木
Fenwick木は、配列の区間和を小さな部分和に分けて保存します。内部添字を1始まりにすると、ある位置の更新では i += i & -i で影響する部分和を上へ進み、先頭からの和では i -= i & -i で必要な部分和を集められます。したがって一点加算と半開区間の区間和を、どちらもO(log N)で処理できます。
Fenwick木の合計の単位元は0です。代表コードでは外部からの添字を0始まり、木の内部だけを1始まりとして扱います。初期配列を一つずつ加算して木を作るため、構築はO(N log N)、Q件の処理を含めた全体はO((N + Q) log N)です。木に使う追加メモリはO(N)です。
代表問題：AtCoder Library Practice Contest B
Practice2 Bの問題文（一点加算と区間和）では、クエリ種別0で位置への加算、種別1で半開区間の和を求めます。実装前に、種別0が代入ではなく加算であることと、区間の右端を含めないことを確認してください。詳しい考え方はPractice2 Bの公式解説（日本語）で照合できます。
import sys
def main():
input = sys.stdin.buffer.readline
n, q = map(int, input().split())
initial = list(map(int, input().split()))
bit = [0] * (n + 1)
def add(index, delta):
i = index + 1
while i <= n:
bit[i] += delta
i += i & -i
def prefix(end):
# [0, end) の合計
total = 0
i = end
while i > 0:
total += bit[i]
i -= i & -i
return total
for index, value in enumerate(initial):
add(index, value)
answers = []
for _ in range(q):
query_type, x, y = map(int, input().split())
if query_type == 0:
# A[x] に y を加算する
add(x, y)
else:
# [x, y) の合計
answers.append(str(prefix(y) - prefix(x)))
sys.stdout.write("\n".join(answers))
if __name__ == "__main__":
main()このコードの prefix(end) は要素番号 end の手前までを返します。したがってクエリ [x, y) は prefix(y) - prefix(x) です。更新値が負でも、合計の単位元0と半開区間の式は変わりません。
一点更新と区間最大・条件検索ならセグメント木
セグメント木は、配列を区間に分け、子区間の結果を親区間へ結合して保存します。最大値を扱う場合は親を左右の最大値にし、結合の単位元を -∞ とします。区間をO(log N)個程度のノードへ分解できるので、区間最大もO(log N)です。一点の値を代入したときは、その葉から根までの最大値を更新します。
最大値を保存しておくと、「指定位置以降で値が基準以上になる最初の位置」のように、条件を満たす区間を木の最大値で捨てながら探せます。Practice2 Jでは、公式の1始まりの位置 j を出力し、見つからない場合は N+1 を返します。実装内部で未発見を n と表す場合も、それは配列の有効範囲の外側を示す内部値であり、出力時に n+1 へ戻します。木の葉の数を2のべき乗にそろえ、余った葉には単位元を置きます。
代表問題：AtCoder Library Practice Contest J
Practice2 Jの問題文（一点更新・区間最大・条件成立位置）では、公式入力のクエリを次の意味で処理します。T=1 X V は A_X を V へ置き換える一点代入、T=2 L R は A_L から A_R までを両端を含めて調べる区間最大、T=3 X V は X <= j <= N かつ V <= A_j を満たす最小の1始まり位置 j の検索です。該当する位置がなければ N+1 を出力します。木の分割と検索の考え方はPractice2 Jの公式解説（日本語）で確認できます。
問題文の添字と端点を、入力直後に内部表現へ一度だけ変換します。更新の X は内部位置 X-1、閉区間 [L, R] は内部の半開区間 [L-1, R) です。条件検索の開始位置も X-1 とし、内部で見つけた位置 p は p+1 で公式の1始まりへ戻します。未発見を内部値 n で返すため、出力は n+1 となり、公式の N+1 と一致します。こうして、問題文の1始まり・閉区間と、コード内部の0始まり・半開区間を混ぜずに扱えます。
import sys
def main():
input = sys.stdin.buffer.readline
n, q = map(int, input().split())
initial = list(map(int, input().split()))
size = 1
while size < n:
size *= 2
neg_inf = -float("inf")
tree = [neg_inf] * (2 * size)
tree[size:size + n] = initial
for node in range(size - 1, 0, -1):
tree[node] = max(tree[node * 2], tree[node * 2 + 1])
def set_value(index, value):
node = size + index
tree[node] = value
node //= 2
while node:
tree[node] = max(tree[node * 2], tree[node * 2 + 1])
node //= 2
def range_max(left, right):
# 内部の半開区間 [left, right) の最大値。
left += size
right += size
result = neg_inf
while left < right:
if left & 1:
result = max(result, tree[left])
left += 1
if right & 1:
right -= 1
result = max(result, tree[right])
left //= 2
right //= 2
return result
def first_at_least(start, value):
# 内部の start 以降で、value 以上になる最初の0始まり位置。
# 見つからないときは内部番兵 n を返す。
def search(node, segment_left, segment_right):
if segment_right <= start or tree[node] < value:
return n
if segment_right - segment_left == 1:
return segment_left if segment_left < n else n
middle = (segment_left + segment_right) // 2
found = search(node * 2, segment_left, middle)
if found != n:
return found
return search(node * 2 + 1, middle, segment_right)
return search(1, 0, size)
answers = []
for _ in range(q):
query_type, x, y = map(int, input().split())
if query_type == 1:
# 公式の A_X = V。入力は1始まりなので内部ではX-1。
set_value(x - 1, y)
elif query_type == 2:
# 公式の閉区間[L, R]を内部の半開区間[L-1, R)へ変換。
answers.append(str(range_max(x - 1, y)))
else:
# 公式のX以降で最初の A_j >= V。未発見ならN+1。
position = first_at_least(x - 1, y)
answers.append(str(position + 1))
sys.stdout.write("\n".join(answers))
if __name__ == "__main__":
main()公式サンプルをそのまま追う
公式サンプルの入力を変換せず、このコードへそのまま渡します。
5 5
1 2 3 2 1
2 1 5
3 2 3
1 3 1
2 2 4
3 1 33
3
2
6初期配列は (1,2,3,2,1) です。最初の T=2 1 5 は A_1 から A_5 までを含むので最大値3になります。次の T=3 2 3 は j=2 の値2が基準3に届かず、j=3 の値3で初めて条件を満たすため3を返します。T=1 3 1 は加算ではなく A_3 を1へ置き換え、配列を (1,2,1,2,1) にします。その後の T=2 2 4 は (2,1,2) の最大値2です。最後の T=3 1 3 では末尾まで3以上の値がないため未発見となり、N+1=6 を返します。出力は 3,3,2,6 です。
コードでは、公式の T=2 2 4 を [1,4)、T=3 2 3 の開始位置を内部の 1 として扱います。内部の検索が n=5 を返した最後のケースは、出力時の position + 1 によって6になります。この対応があるため、公式入力の端点と出力の番兵を内部表現へ取り違えません。
構築はO(N)、一点代入・区間最大・条件成立位置の検索はそれぞれO(log N)です。木の配列は葉の数を含めてO(N)の追加メモリを使います。first_at_least は、区間の最大値が条件に届かない部分木を調べず、左部分木から順に探します。親の最大値が基準未満なら、その部分木には条件を満たす葉がないため、この枝刈りが成立します。
境界を確認する
L=R の区間最大は一要素だけを調べます。X=N の更新・検索では末尾の要素を内部位置 n-1 として扱います。T=3 で開始位置から末尾まで該当しなければ、内部番兵 n を公式の N+1 として出力します。値が0の配列でも、最大値の単位元 -∞ は0より小さいため、値0を正しく候補として残せます。更新直後の区間最大は、代入後に葉から根へ最大値を再計算するため、新しい値を反映します。
区間更新と順序統計を扱う境界
一点ではなく区間全体へ更新を行い、その後も区間クエリを続ける場合は、更新をすぐすべての葉へ反映せず、必要になったときに子へ伝える遅延評価が必要になります。次の題材としてPractice2 Lの問題文（区間更新と区間クエリ）とPractice2 Lの公式解説（日本語）を読み、更新の合成方法と単位元を別に設計してください。このページのコードは区間更新を実装していません。
「小さい順にk番目」「条件を満たす要素の順位」のような順序統計も、最大値の区間検索とは必要な情報が異なります。ここで示したコードだけで解けると約束せず、頻度の管理、座標圧縮、別の木の設計などを確認する専用の学習へ分けます。
実装で迷いやすい境界条件
| 確認する点 | このページでの扱い |
|---|---|
| 区間の端点 | Practice2 Bのコードは [l, r)。Practice2 Jの公式入力 [L, R] は両端を含み、コード内で [L-1, R) へ変換する。 |
| Fenwick木の更新 | Practice2 Bでは A[p] += x。現在値の代入ではない。 |
| セグメント木の更新 | Practice2 Jでは A[p] = x。加算にするなら問題の意味に合わせて変更する。 |
| 合計の単位元 | 0。空の合計を表す。 |
| 最大値の単位元 | -∞。余った葉や空の部分結果に使う。 |
| 検索で見つからない場合 | Practice2 Jの公式出力は N+1。コード内部の番兵 n を出力時に n+1 へ戻す。 |
| 区間更新が出てきた場合 | 遅延評価セグメント木へ分岐し、このページの実装を流用しない。 |
実装前にクエリを一行ずつ読み、更新の種類・区間の端点・返す値・存在しない場合の返り値をメモすると、木の内部添字と問題文の添字を混同しにくくなります。
前提確認から次の一問へ
入力・配列・ループなどの基本を確認したい場合はAtCoderカテゴリの基本記事を、標準ライブラリの確認が必要な場合はPython公式ドキュメントのitertoolsを参照してください。
まず、区間クエリの手法を直接使わない問題を前提確認として解きます。ABC235 C The Kth Time Queryの問題文とABC235 Cの公式解説は、値ごとに出現位置を前処理して参照する考え方を確認する題材です。Fenwick木やセグメント木の代表実装ではないので、主練習の段階には混ぜません。
| 段階 | 公式問題 | 練習する操作・観察 | 前提 | 確認する境界 |
|---|---|---|---|---|
| 最初に解く 手法タグ：Fenwick木 |
Practice2 B | 一点加算と半開区間の区間和。部分和を更新・再利用する。 | 配列の添字、累積和、[l, r) の読み方。 |
加算でなく代入、最大・最小、区間更新が出たら手法を見直す。 |
| 次に解く 手法タグ：セグメント木 |
Practice2 J | 一点代入、区間最大、条件を満たす最初の位置の検索。 | 区間分割、最大値の結合、単位元。 | 区間更新は遅延評価へ、k番目や順位は順序統計の学習へ分ける。 |
| 挑戦する 手法タグ：遅延評価セグメント木 |
Practice2 L | 区間更新と区間クエリで、更新をいつ子へ伝えるかを観察する。 | セグメント木の結合と一点更新の流れ。 | このページには実装を掲載しない。更新の合成と単位元を専用に設計する。 |
前提確認で「前処理した値を直接参照するだけ」と分かったら、Fenwick木を無理に足しません。Practice2 Bで一点加算と区間和の対応を固め、その後にPractice2 Jで結合演算と条件検索へ進みます。区間更新や順序統計が必要になった時点で、このページの代表コードの範囲を越えたと判断できます。
まとめ
更新がない区間和は累積和、一点加算と区間和はFenwick木、一点更新と最大値・最小値・条件成立位置はセグメント木から考えます。まず半開区間と更新種別を固定し、素朴なO(NQ)が制約に対して重いかを確かめます。そのうえでPractice2 Bの完全コードを動かし、Practice2 Jの一点更新・区間最大・位置検索へ進み、区間更新や順序統計は専用の設計へ分岐してください。
