📚

【C#データ構造】Segment Treeで区間最小値を高速に求める

2026/05/26に公開

 はじめに配列の一部分だけを見て「この範囲の最小値は？」と何度も聞かれる問題があります。
毎回その範囲を先頭から末尾まで調べると、範囲の長さが大きいほど時間がかかります。さらに、途中で値を書き換える操作も入ると、累積和やSparse Tableだけでは扱いにくくなります。
そこで使いやすいのが Segment Tree です。この記事では、区間最小値を求める例で、Segment Treeの考え方とC#実装を整理します。

 Segment Treeとは？Segment Treeは、配列を区間ごとに分けて、各区間の答えを木として持つデータ構造です。
たとえば区間最小値なら、木の各ノードに「その区間の最小値」を保存します。親ノードの値は、左右の子ノードの最小値から計算できます。
できることの例は次の2つです。

Query(l, r): 半開区間 [l, r) の最小値を求める

Update(index, value): index 番目の値を書き換える
どちらも O(log N) で処理できます。

 図解配列の長さを2のべき乗にそろえ、葉に元の値を置きます。親には子の最小値を入れます。
たとえば [1, 4) の最小値を知りたいとき、必要な区間だけを拾います。全部の要素を1つずつ見るのではなく、すでに計算済みの区間の値を使うのがポイントです。

 どんなときに使うかSegment Treeは、次のような問題でよく使います。
配列の値が途中で更新される
区間の最小値、最大値、合計などを何度も求める
クエリ数が多く、毎回線形探索すると間に合わない
Fenwick Treeも更新と区間和に強いですが、Segment Treeは「最小値」「最大値」「gcd」などにも自然に使えます。どの演算を持たせるかを変えられるところが便利です。

 考え方Segment Treeでは、葉から上に向かって値を作ります。
区間最小値の場合、親ノードの値は次のように決まります。
親の値 = Min(左の子の値, 右の子の値)
更新するときは、まず葉の値を書き換えます。その後、親、さらにその親へと戻りながら最小値を再計算します。
ここで混乱しやすいのは、Query(l, r) の r が含まれないことです。C#の Substring や配列の範囲指定と同じように、この記事では半開区間 [l, r) として扱います。

 アルゴリズムの流れ
 構築配列長以上の2のべき乗を size とする
木を表す配列を十分大きく用意し、初期値を INF にする
元の配列を葉に入れる
下から上へ、左右の子の最小値を親に入れる

 更新更新したい位置に対応する葉を書き換える
親へ移動しながら、左右の子の最小値で再計算する

 区間取得
l と r を葉の位置に移す

l < r の間だけ見る

l が右側の子なら、その区間を答えに使って l++

r が右側の子なら、--r してその区間を答えに使う

l と r を親へ移動する
少し手続きが多く見えますが、「今見ている左右端から、答えに使える区間だけを拾って親へ進む」と覚えると整理しやすいです。

 C#での実装区間最小値に絞ったSegment Treeです。Query(l, r) は半開区間 [l, r) の最小値を返します。
using System;

public class SegmentTreeMin
{
    private const int Inf = int.MaxValue;
    private readonly int size;
    private readonly int[] data;

    public SegmentTreeMin(int[] values)
    {
        size = 1;
        while (size < values.Length)
        {
            size *= 2;
        }

        data = new int[size * 2];
        Array.Fill(data, Inf);

        for (int i = 0; i < values.Length; i++)
        {
            data[size + i] = values[i];
        }

        for (int i = size - 1; i >= 1; i--)
        {
            data[i] = Math.Min(data[i * 2], data[i * 2 + 1]);
        }
    }

    public void Update(int index, int value)
    {
        int node = size + index;
        data[node] = value;

        while (node > 1)
        {
            node /= 2;
            data[node] = Math.Min(data[node * 2], data[node * 2 + 1]);
        }
    }

    public int Query(int left, int right)
    {
        int answer = Inf;
        left += size;
        right += size;

        while (left < right)
        {
            if (left % 2 == 1)
            {
                answer = Math.Min(answer, data[left]);
                left++;
            }

            if (right % 2 == 1)
            {
                right--;
                answer = Math.Min(answer, data[right]);
            }

            left /= 2;
            right /= 2;
        }

        return answer;
    }
}

public class Program
{
    public static void Main()
    {
        int[] values = { 5, 2, 6, 3, 1, 7 };
        var seg = new SegmentTreeMin(values);

        Console.WriteLine(seg.Query(1, 4)); // values[1..4) = 2, 6, 3

        seg.Update(2, 0); // values[2] を 6 から 0 に変更
        Console.WriteLine(seg.Query(1, 4)); // 2, 0, 3

        Console.WriteLine(seg.Query(3, 6)); // 3, 1, 7
    }
}

 実行例上のプログラムを実行すると、次のようになります。
2
0
1
最初の [1, 4) では 2, 6, 3 の最小値なので 2 です。
その後、values[2] を 0 に更新したので、同じ [1, 4) の最小値は 0 になります。

 計算量要素数を N とします。
構築: O(N)
1点更新: O(log N)
区間最小値クエリ: O(log N)
メモリ: O(N)
単純に毎回範囲をすべて調べると、1回のクエリに O(N) かかることがあります。クエリ数が多い問題では、この差がかなり大きくなります。

 つまずきやすいポイントQuery(left, right) の right は含みません。Query(1, 4) なら、見るのは添字 1, 2, 3 です。
初期値には、最小値の邪魔をしない大きな値を入れます。今回なら int.MaxValue です。最大値を求めるSegment Treeなら、逆にかなり小さい値を初期値にします。
また、配列長が2のべき乗でなくても使えるように、内部では2のべき乗まで広げています。余った葉には INF を入れておけば、最小値に影響しません。

 まとめSegment Treeは、更新される配列に対して区間の答えを高速に求めるためのデータ構造です。
区間最小値では、各ノードに「担当区間の最小値」を持たせます。更新は葉から親へ、取得は左右端から使える区間を拾う、と考えると実装を追いやすくなります。
最初は添字の動きが難しく見えますが、[l, r) の半開区間で統一するとミスを減らせます。

 参考AtCoder Library - segtree
cp-algorithms - Segment Tree

はじめに

Segment Treeとは？

図解

どんなときに使うか

考え方

アルゴリズムの流れ

構築

更新

区間取得

C#での実装

実行例

計算量

つまずきやすいポイント

まとめ

参考

Discussion