Segment Tree の基本(1) 考え方

区間に対するクエリを高速に処理できるデータ構造 Segment Tree（セグメント木）の基本を復習したのでまとめます。
第一回は Segment Tree の考え方についてです。

なぜ Segment Tree が必要なのか

ある時系列の一次元データを分析する、というストーリーを考えます。 「ある時刻のアクセス数」「busy状態にあったサーバ数」「発電量」「ドル円」などお好きなものを想像してください。
上記のデータをまとめた配列 arr があるとします。 データは1秒ごとの値が全部で1年分、つまり配列のサイズは 60*60*24*365 = 31536000 とします。

• 1月1日 0時0分0秒 の値: arr[0]
• 1月1日 0時0分1秒 の値: arr[1]
• …

この情報に対する集計クエリを考えます。

単一データの取得

例えば20000番目の値なら、arr[20000] などで取得できるでしょう。

短い区間の合計

あるインデックスから1分間、つまり [L, L+60) の区間の合計を求めたいとします。 これは単純なforループで求めることができますね。

# Python
arr = [i%10 for i in range(31536000)] # ダミーデータ

def range_sum(L):
    _sum = 0
    for i in range(L, L+60):
        _sum += arr[i]
    return _sum

sum(arr[L:L+60]) のように書くこともできますが、こちらも内部的にループ処理が行われているので、本質的には同じことです。
区間の最小値や最大値などでも同様です。

長い区間の合計

開始・終了インデックスをどちらも自由に指定できるように拡張することを考えます。
forループで求めることはできますが、広い区間を指定された場合にはループ回数が多くなり、レスポンスが遅くなってしまうでしょう。
[0, 31536000) のクエリを大量に投げられると、詰まりそうです。

# Python
arr = [i%10 for i in range(31536000)] # ダミーデータ

def range_sum(L, R):
    _sum = 0
    for i in range(L, R): # (R - L) が大きい値の場合、ループ回数が多くなる
        _sum += arr[i]
    return _sum

Python実行環境のある方は、インタプリタで上記コードを読み込んでから range_sum を実行してみてください。
range_sum(0, 31536000) はどれくらい時間がかかるでしょうか。

ちなみに、このケースでは累積和を事前に計算しておくことで計算量を改善できます。

# Python
arr = [i%10 for i in range(31536000)] # ダミーデータ

# 事前に累積和を計算しておく（以降のクエリで使い回す）
def preprocess():
    cumulative_sum = [0]
    for val in arr:
        cumulative_sum.append(cumulative_sum[-1] + val)

# 累積和を使って区間の合計を効率よく求める
def range_sum(L, R):
    return cumulative_sum[R] - cumulative_sum[L]

より”難しい”クエリ

ここからは、より難しいクエリを考えてみます。

• arr が今後1年分の予測値であり、予測値の更新クエリも受け付けるとしたら？
  • 例えば 50000 番目の時刻に何らかのイベントが発生することになり、その時刻の値を更新する arr[50000] = 100 というクエリ
    • この場合、累積和を使った前処理は根本解決にならない （累積和配列の作り直しが重いため）
• 区間の合計値ではなく最大値（あるいは最小値）が欲しい、となったら？

このような、区間に対する取得のクエリに高速に（O(N)よりマシな計算量で）応えられるデータ構造が Segment Tree です。

Segment Tree

Segment Tree は、下記のクエリを高速に（O(logN)で）処理できるデータ構造です。

• ある区間 [L, R) に対する（特定の）演算クエリ
• 特定のインデックス i に対する更新クエリ

上の例で言えば、予測値の更新や任意区間の最大値取得クエリを O(logN) で処理できる、ということです。

Segment Tree の発想

毎回合計値を求める方式の問題点は、[L, R) が長い区間になるとループ回数が多くなってしまうことでした。

for i in range(L, R):
    val += arr[i]

長さ8の配列で図示すると

[0, 7) に対する合計取得は、7個の値の1つ1つ足していくという処理になります。

長い区間の合計処理が重いなら、区切られた区間の合計をキャッシュして高速化できそうです。

試しに前半と後半の区間の合計をキャッシュしてみると

[0, 7) というクエリに対しては、前半部分でキャッシュ活用することで足し上げる個数を削減できました。

さらに汎用的なキャッシュ構造があれば、様々な区間に対してキャッシュ活用ができるようになります。

Segment Tree の構造

先頭から2要素ずつをペアとして、その和をキャッシュしておきます。
さらに、先頭から2つの区間キャッシュをペアとして、その和をキャッシュしておきます。
さらにさらに… と繰り返したものが、Segment Tree （の合計演算版） です。

区間合計クエリの対応

[0, 7) なら、下図のように合計3つの要素を調べるだけで求められます。

更新クエリの対応

更新クエリでは、更新対象の要素が含まれる各区間を必要に応じて更新することになります。

arr[3] = 3 という更新の例を以下に示します。

Segment Tree のうれしい性質

• 合計値だけでなく、最小値や最大値など、様々な演算を扱える
  • 演算を表す関数をSegment Treeのコンストラクタに渡すような実装にすれば、汎用的に扱える
• 更新クエリに対応している
• 区間取得・更新の計算量がそれぞれ O(logN)

次のステップ

• 対応可能な演算の性質を深掘り
• 実装の工夫
• 区間更新クエリの対応
• 二次元への拡張