PHP で遅延セグメント木を作る
目次：
遅延評価とは
遅延評価とは、文字通り評価を遅らせることです。
日常生活では、何かを後回しにすることは、あまり評価されないことですが、コンピュータの計算においては、常にその場で計算を完了させてしまうこと（即時評価）が、計算資源の無駄遣いになってしまうことがあります。
中途半端な状態であえて計算を止めておき、実際に値が必要なタイミングまで計算を遅らせることで、計算時間やメモリ空間を効率化できることがあります。
遅延評価セグメント木とは
今回実装した遅延評価セグメント木は、以前紹介したセグメント木に、遅延評価を付けたものです。
これにより、セグメント木では「1点更新、区間取得」しかできなかったものが、計算量は O(log N) のままで、「区間更新、区間取得」できるようになります。
つまり、更新作業で、毎回その区間全体を更新しきるのではなく、更新途中の状態を（$lazy という配列に）持たせておき、実際に値を出力するタイミングで計算の続きを行っています。
実装
実装したものがこちらです：
<?php
class LazySegTree {
public array $tree;
public array $lazy;
public int $n;
public Closure $func;
public mixed $e;
public Closure $mapping;
public Closure $comp;
public mixed $id;
public function __construct(
array $arr,
Closure $func,
mixed $e,
Closure $mapping,
Closure $comp,
mixed $id
) {
$this->func = $func;
$this->e = $e;
$this->mapping = $mapping;
$this->comp = $comp;
$this->id = $id;
$size = count($arr);
$this->n = 1;
while($this->n < $size) {
$this->n <<= 1;
}
$this->tree = array_fill(0, 2*$this->n, $this->e);
$this->lazy = array_fill(0, 2*$this->n, $this->id);
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],
);
}
}
private function eval(int $k, int $l, int $r): void {
if($this->lazy[$k] === $this->id) {
return;
}
$this->tree[$k] = ($this->mapping)($this->lazy[$k], $this->tree[$k], $r-$l);
if($r-$l > 1) {
$this->lazy[2*$k+1] = ($this->comp)($this->lazy[$k], $this->lazy[2*$k+1]);
$this->lazy[2*$k+2] = ($this->comp)($this->lazy[$k], $this->lazy[2*$k+2]);
}
$this->lazy[$k] = $this->id;
}
// [$a, $b) への更新であることに注意する
public function update(int $a, int $b, mixed $x):void {
$this->update_recurse($a, $b, $x, 0, 0, $this->n);
}
private function update_recurse(int $a, int $b, mixed $x, int $k, int $l, int $r): void {
$this->eval($k, $l, $r);
if($r <= $a || $b <= $l) {
return;
}
if($a <= $l && $r <= $b) {
$this->lazy[$k] = ($this->comp)($x, $this->lazy[$k]);
$this->eval($k, $l, $r);
} else {
$mid = intdiv($l + $r, 2);
$this->update_recurse($a, $b, $x, 2*$k+1, $l, $mid);
$this->update_recurse($a, $b, $x, 2*$k+2, $mid, $r);
$this->tree[$k] = ($this->func)($this->tree[2*$k+1], $this->tree[2*$k+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 {
$this->eval($k, $l, $r);
if($r <= $a || $b <= $l) {
return $this->e;
}
if($a <= $l && $r <= $b) {
return $this->tree[$k];
}
$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);
}
}
// ## 使い方
// 区間加算・区間最小値取得
$array = [0, 1, 2, 0, 3, 5, 0];
$func = fn($v1, $v2) => min($v1, $v2);
$e = PHP_INT_MAX;
$mapping = fn($f, $val) => $f + $val;
$comp = fn($f, $g) => $f + $g;
$id = 0;
$lst = new LazySegTree($array, $func, $e, $mapping, $comp, $id);
// [2, 5) に1追加
$lst->update(2, 5, 1);
var_dump($lst->query(2, 5)); // 1
ポイント解説
ベースとなるのは、以前紹介したセグメント木です。
初期配列（$array）を渡し、モノイドの関数（$func）と単位元（$e）を渡します。
違うのは、その先の部分です。
遅延評価される値（$lazy）どうしを合成させる関数として $comp を渡し、その遅延値を実際の値（$tree）にマッピングする関数として $mapping を渡します。
足し算の場合は、遅延値どうしも、それを実際の値に更新させるのも足し算なのでわかりやすいです。
内部的には、 eval というメソッドがあり、ここでその範囲の評価を行っていることが分かります。
たとえば、特定の範囲をひとつずつ（線形に）計算していれば要素の数だけ手間がかかります。
しかし、セグメント木では、各ノードが 1, 2, 4, 8, ... と、 2のべき乗の大きさを持つ「きれいな塊（区間）」としてデータを管理しています。
そのため、どんなに広い範囲であっても、それらを対数のステップ数（log(10万)でもたったの17回）で、まとめてスッパリと切り分けて、計算を一旦止める（遅延させる）ことができます。
実際に、ある特定範囲の結果が必要になったとき、はじめてその部分の計算の続きをやればよいわけです。
まとめ
コンピュータの計算は、人間と比べればとても早いものですが、桁が上がるにつれて、いずれ限界が来ます。
そのような大規模な計算時に、今不必要な計算をどうやって削減していくか、その方法のひとつが、遅延評価なのだと思います。
最後までお読みいただき、ありがとうございました。
何かお気づきの点がありましたら、 お問い合わせ ください。