セグメント木とは

以前、フェニック木を PHP で作成しましたが、今回は、その親戚のようなデータ構造の「セグメント木」について、 PHP で実装してみようと思います。

セグメント木は、フェニック木と同様に、ある範囲の情報を高速に求めることができるデータ構造です。 フェニック木が、主に区間和を対象とするのに対し、セグメント木は、「モノイド」という条件を満たす情報を、対象とします。
区間和は、モノイドの条件を満たすので、フェニック木でできることは、基本的にセグメント木でもできます。
その意味では、セグメント木の方が比較的自由度が高いデータ構造といえます。

セグメント木を使うだけなら、「モノイド」という言葉自体は、覚える必要がないのですが、以下で説明するように、その条件をある程度知っておくと、とても便利に扱えます。

内部のデータの置き場所を想像するのが難しい反面、区間和の他にも、区間内の最大値や、区間内の最小値、区間内の文字列の結合など、さまざまな用途に使える、比較的応用の効きやすいデータ構造です。

実装

実装したものがこちら：

<?php
// ## segment tree
class SegmentTree {
    public array $tree;
    public int $n;
    public Closure $func;
    public mixed $e;
    public function __construct (array $arr, Closure $func, mixed $e) {
        $this->func = $func;
        $this->e = $e;
        $size = count($arr);

        $this->n = 1;
        while($this->n < $size) {
            $this->n <<= 1;
        }
        // tree も 0-index
        $this->tree = array_fill(0, 2 * $this->n, $this->e);
        for($i=0; $i<$size; $i++) {
            $this->tree[$this->n - 1 + $i] = $arr[$i];
        }
        for($i=$this->n-2; $i>=0; $i--) {
            $this->tree[$i] = ($this->func)(
                $this->tree[2*$i+1],
                $this->tree[2*$i+2]
            );
        }
    }
    public function update(int $idx, mixed $x):void {
        $idx += $this->n - 1;
        $this->tree[$idx] = $x;
        while($idx > 0) {
            $idx = intdiv($idx - 1, 2);
            $this->tree[$idx] = ($this->func)(
                $this->tree[2*$idx+1],
                $this->tree[2*$idx+2]
            );
        }
    }
    // [$a, $b) 半開区間であることに注意する
    public function query(int $a, int $b): mixed {
        return $this->query_recurse($a, $b, 0, 0, $this->n);
    }
    private function query_recurse(int $a, int $b, int $k, int $l, int $r): mixed {
        if($r <= $a || $b <= $l) {
            return $this->e;
        }elseif($a <= $l && $r <= $b) {
            return $this->tree[$k];
        }else{
            $mid = intdiv($l + $r, 2);
            $ar = $this->query_recurse($a, $b, 2 * $k + 1, $l, $mid);
            $br = $this->query_recurse($a, $b, 2 * $k + 2, $mid, $r);
            return ($this->func)($ar, $br);
        }
    }
}

// 使い方 - min がほしい場合
$arr = [1, 4, 9, -1];
$func = fn(int $a, int $b) => min($a, $b);
$e = PHP_INT_MAX;
$seg = new SegmentTree($arr, $func, $e);
$seg->update(3, 5);
echo 'seg 木: '.$seg->query(1, 3).PHP_EOL;

基本的な特徴

セグメント木も、2分木の構造をしています。親から、2つの子を持ち、それぞれの子もまた、2つの子（親から見れば孫）を持ちます。

この構造により、自分の子要素の範囲に、必要な範囲が含まれているかを再帰的に判定できるようになり、計算量が削減されるという仕組みです。

上記の実装例では、 update($index, $x) というメソッドで、 $index 番目のデータを $x に更新し、 query($a, $b) というメソッドで、 [$a, $b) の半開区間（ $a 以上 $b 未満）の情報を取得します。

いずれも、計算量は O(log N) です。

初期化時に渡す引数

PHP では、 class の初期化時に __construct というメソッドを実行するのですが、セグメント木では、初期配列の他に、関数 $func と、 単位元となる $e を渡します。
この2つは、前述のモノイドに関係するものです。

モノイドについて

モノイドでは、ある計算処理 ▲ があったとき、以下の条件を満たします。

• 処理は、どこからやっても結果は同じになる
  • (A ▲ B) ▲ C === A ▲ (B ▲ C)
• しかし、処理する方とされる方を入れ替えられるとは限らない
  • A ▲ B !== B ▲ A
• 処理する方でも、される方でも、常に結果が変わらない単位元 e が存在する
  • A ▲ e === e ▲ A === A

モノイドの例1: 足し算

たとえば、足し算は、どこから足しても結果は同じです。
(1 + 2) + 3 === 1 + (2 + 3)

また、足す数と、足される数を入れ替えても結果は同じです。 （よって、2番目の条件より、足し算の方が厳しいです）
1 + 2 === 2 + 1

足し算の単位元は、 0 です。
0に何を足しても、足されても、その数になります。
$A + 0 === 0 + $A === $A

モノイドの例2: 最小値

最小値についても考えてみましょう。

どの順番で最小値を求めても、結果は同じです。
min(min(1, 2), 3) === min(1, min(2, 3))

また、最小値の比較順を変えても、結果は同じです。 （よって、足し算と同じく、最小値も、より厳しい条件です）
min(1, 2) === min(2, 1)

最小値の単位元は、 プラスの無限大 です。 PHP の int 型の場合、便宜的に PHP_INT_MAX を使うことが多いと思います。
min($A, PHP_INT_MAX) === min(PHP_INT_MAX, $A) === $A

モノイドの例3: 文字列の連結

2番目の条件を満たすゆるい条件として、文字列の連結処理があります。

連結処理を、たとえば以下のような関数であらわしてみます。

$join = fn(string $a, string $b) => $a . $b;

どの順番で処理をしても、結果は同じです。
$join($join('A', 'B'), 'C') === $join('A', $join('B', 'C')) === 'ABC'

結合の順序を入れ替えると、違う文字になりえます。
$join('A', 'B') === 'AB'
$join('B', 'A') === 'BA'

結合処理の単位元は、空文字 '' です。
$join('A', '') === $join('', 'A') === 'A'

PHP で関数を引数に渡したい場合の注意点

PHP では、関数の引数に関数やメソッドを渡したい場合、ちょっと注意が必要です。

他の（たとえば JavaScript のような）プログラミング言語の場合、その関数名を渡せば、そのまま処理をしてくれます。

function mymin (func) {
    return func(1, 2);
}
const result = mymin(Math.min);

PHP の場合は、 callable （文字列や配列など）にして、渡す必要があります。

function mymin($func) {
    return $func(1, 2);
}
$result = mymin('min');

関数名の文字列や、class メソッドの場合は、 [ClassName::class, 'method_name'] のような配列などが必要になります。

これは、 PHP 特有の歴史的経緯によるものです。
詳しくは、 PHP 第一級オブジェクト 関数 などで検索すると、詳しい解説が出てくると思います。