0Pricing
Coding Interview Prep · レッスン

セグメント木: 構築とクエリ

範囲の min、max、sum を log n で求めます

「セグメント木: 構築とクエリ」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。

Fenwick tree の先へ

Fenwick tree は合計に適していますが、セグメント木なら最小値、最大値、最大公約数なども扱えます。区間クエリにおける柔軟な万能選手です。

区間を扱う木

各ノードは配列の区間を担当します。ルートは全体を覆い、子ノードは葉が1つの要素を持つまで区間を半分に分割します。

配列による格納

木はサイズ2nまたは 4n のフラットな配列に格納します。ノード1がルートで、ノード i の子は 2i と 2i+1 に置きます。

seg = [0] * (2 * n)

葉にデータを格納する

反復形式では、元の値は配列の後半、つまりインデックス n から 2n-1 に格納されます。

for i in range(n):
    seg[n + i] = a[i]

下から上へ構築する

各内部ノードは、2つの子のcombine結果です。n-1 から 1 まで埋めていけば、木全体の準備が整います。

for i in range(n - 1, 0, -1):
    seg[i] = seg[2*i] + seg[2*i+1]

結合操作

combine関数が木の動作を定義します。合計には plus、最小値には min、最大値には max を使います。ここを変更すればクエリを変えられます。

def combine(x, y):
    return min(x, y)

点を更新して上へ進む

1つの値を変更するには、葉を設定してからルートまで上へ進み、その途中で各親を2つの子から再計算します。

i += n
seg[i] = value
while i > 1:
    i //= 2
    seg[i] = combine(seg[2*i], seg[2*i+1])

半開区間をクエリする

区間クエリでは両端から走査し、境界にあるノードを答えに取り込みます。区間は半開区間で、l 以上 r 未満を表します。

反復クエリのループ

l と r を互いに近づけていきます。インデックスが奇数の境界にある場合は、ポインタを進める前にそのノードを答えへ取り込みます。

while l < r:
    if l & 1: res = combine(res, seg[l]); l += 1
    if r & 1: r -= 1; res = combine(res, seg[r])
    l //= 2; r //= 2

両端で対数時間

構築は O(n) で、更新とクエリはそれぞれO(log n)です。このバランスが、セグメント木を非常に柔軟なものにしています。

単位元に注意する

結果は演算の単位元から始めます。合計なら 0、最小値なら無限大、最大値なら負の無限大です。開始値を間違えると答えも間違います。

res = float('inf')

確認問題

反復形式の木では、元のデータはどこに格納されているでしょうか。

振り返り：柔軟な区間処理

セグメント木を構築しました。葉は後半に置き、親は子の combine として計算します。合計、最小値、最大値の更新とクエリを O(log n) で処理できます。🌳

よくある質問

「セグメント木: 構築とクエリ」レッスンは無料ですか？

はい。「セグメント木: 構築とクエリ」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。

「セグメント木: 構築とクエリ」で何を学びますか？

範囲の min、max、sum を log n で求めます ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Coding Interview Prepを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。

「セグメント木: 構築とクエリ」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCoding Interview Prepレッスンでコードを書いて実行できますか？

はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. 累積和のための Fenwick Tree
  2. BIT による転倒数
  3. セグメント木: 構築とクエリ
  4. 範囲更新の遅延伝播
← Coding Interview Prepに戻る