遅延評価セグメント木

むずいけど、まずは単純な「整数と区間MIN」などから実装していくと慣れてくる。

概要

（通常の）セグメント木: 一点更新・区間取得
遅延評価セグメント木: 区間更新・区間取得

参考

遅延評価セグメント木をソラで書きたいあなたに - hogecoder
- 通常のセグ木を理解してから、遅延セグ木では新しくどういうことができるようになるかを図で把握しやすい
SegmentTreeに載る代数的構造について - Qiita
- 記号的な説明がわかれば、セグ木、双対セグ木、遅延セグ木に要求される性質とその理由がまとまっている
AtCoder LibraryのLazy Segtreeの使い方 - ARMERIA
- AtCoder Library に遅延セグ木が実装されているので、そこから勉強を広げていきたい人向け

実装にまつわる留意点

カスタマイズ性の高さ

一口に遅延評価セグメント木といっても実装には自由度がある。

区間MINならこっちの方が書きやすいけど区間和ならこっち、みたいな細かな実装の違いがあり、各解説サイトではどういう前提を敷いているのか、注意しないといけない。

再帰・非再帰

再帰の方がわかりやすいが、特にPythonなどインタプリタ言語では非再帰の方が高速。

data[i]にlazy[i]は反映済みか

dataを集約値の配列、lazyを遅延評価用の配列とする。

同じindexのdataの値に、lazyが反映済みの実装と、まだ反映させてない実装がある。

別に他の部分の実装によって何とでも変わりうるが、一般的には以下みたいな違いがある。

反映済みの場合
- 更新時は、作用素をdataに反映させ、さらに（子を持つノードの場合）lazyに合成しておく
- 取得時は、既に反映済みの値が入っているので参照はdataだけでよい
- 末端ノードにlazyは不要
反映させない場合
- 更新時は、作用素をlazyに合成するだけ
- 取得時は、その都度dataにlazyを反映させる

ちゃんとは比較していないが、よほど取得クエリより更新クエリの方が多いことが事前にわかってない限り、反映させておく実装の方がいいかな。

作用素 $F$ が可換・非可換

たとえば区間和で、ある $i$ を含む区間に対して「3足され、5足され、7足され」という情報が、$i$ の頭上の様々なノードに貯まっていく。

|---------- 7 ----------|
|---- 5 ----|-----------|    [2,4) に 3
|-----|- 3 -|-----|-----|    [0,4) に 5
|--|--|--|--|--|--|--|--|    [0,8) に 7 が足された
  0  1  2  3  4  5  6  7

ここから実際に、たとえば $i=3$ の値が今いくつなのかを求める際には、上から遅延評価分を押し込むように反映させていく。

|-----------------------|
|--- 12 ----|---- 7 ----|    7を下ろす
|-----|- 3 -|-----|-----|
|--|--|--|--|--|--|--|--|

|-----------------------|
|-----------|---- 7 ----|    12を下ろす
|-12--|-15 -|-----|-----|
|--|--|--|--|--|--|--|--|

|-----------------------|
|-----------|---- 7 ----|    15を下ろす
|-12--|-----|-----|-----|
|--|--|15|15|--|--|--|--|

この $3,5,7$ といった作用素を合成（今回は足し算）するにあたり、$3+5+7$ でなく $3+7+5$ などと順番を入れ替えても正しく求まるよ、というのが「可換」。

遅延評価という名の通り、区間にまとめて足し込んだ作用素は、いつかは下に反映させなければならない（まぁクエリが来なければしなくていいけど）。その際、作用素が可換だとサボれる部分がある。

更新時
- 更新前に、上から順に、溜まっている遅延評価分を反映し、子に伝播させる（★）
- 更新後に、下から順に、再計算する
取得時
- 取得前に、上から順に、溜まっている遅延評価分を反映し、子に伝播させる

ここで、$F$ が可換なら、更新前の評価（★）を省け、若干の高速化に繋がる。
一方、非可換なら省けず、先に作用した分を評価しきってから更新を行う必要がある。

遅延データ
|-----------------------|
|-----3-----|-----------|    [2,3) に 1
|-----|--2--|-----|-----|    [2,4) に 2
|--|--|-1|--|--|--|--|--|    [0,4) に 3 がこの順で足された
  0  1  2  3  4  5  6  7 

■さらに [2,4) に 4 を足したい

可換の場合
|-----------------------|    いきなり足してしまってOK。
|-----3-----|-----------|    意味合いとしては  1+(2+4)+3 となり、
|-----|--6--|-----|-----|    実際に作用させた順とは異なっているが、
|--|--|-1|--|--|--|--|--|    可換なので問題なし。

非可換の場合（非可換で単純な例が思いつかないのでここでは足し算で説明）
|-----------------------|
|-----------|-----------|    更新前に3を下ろして合成してから...
|--3--|--5--|-----|-----|
|--|--|-1|--|--|--|--|--|

|-----------------------|
|-----------|-----------|    [2,4) に 4 を足す。
|--3--|--9--|-----|-----|    これで意味合いとしては 1+(2+3+4) となり、
|--|--|-1|--|--|--|--|--|    実際に作用させた順と一致している。
  0  1  2  3  4  5  6  7

整数の足し算、かけ算、XOR、MIN、MAX、GCD、LCMなどメジャーどころは可換。
行列の積などは非可換。

解説サイトでは注意してどちらを前提としているのか見る必要がある。

更新が加算か上書きか

これは遅延セグ木に限らず普通のセグメント木でも注意を要するところだが、更新が既存の値を使うのかどうかで実装が変わってくる。

上書きの場合、少しテクニカルな書き方が必要となる。

作用素 $F$ がどうなるか考える。

「一律 $X$ に上書きされました」という情報を持つ
合成は順番が大事（非可換）であり、一番後に作用したもののみが有効
遅延セグ木に載るものの条件より、恒等写像（既存の要素に影響を及ぼさない値）の存在が必要
- 意味合い的には「何にも上書きされていないフラグ」
- 実装としてはタプル化してbool値を持たせるか、「絶対に $X$ になり得ない値」を決めてそれで代用する

その上で、mappingとcompositionは、以下のようになる。

S mapping(F f, S s): fが上書きフラグFalseならsをそのまま返し、それ以外ならfを反映させた値を返す
F composition(F f, F g): 作用順はg→fとする。fが上書きフラグFalseならg、それ以外ならfを返す

参考
- AtCoder LibraryのLazy Segtreeの使い方 - ARMERIA
  - 「区間更新操作の恒等写像」の章

作用が区間長に依存するか、する場合いつ反映させるか

区間和を管理するセグメント木で、$[0,10)$ に一律 $2$ を加算したとき、区間 $[0,8)$、$[8,10)$ を表すノードの値はそれぞれいくつ増えるか。当然、「作用させる値×区間長」なので $16, 4$ となる。

作用素が同じ $2$ でも区間長によってdataに反映する値が変わってくるような演算の場合、区間長をどう取得していつ反映させるかで複数の実装がある。
dataには最終的に反映させた値が必要として、

lazyに入れる段階で、区間長倍しておく
- lazyを子に伝播させるとき、半分にする必要がある
lazyでは1マスあたりの値で管理しておき、dataに作用させる段階で反映させる

$F$ が整数とは限らない汎用的な実装にするには、前者の方法では「$F$ を整数倍する処理」や「$F$ を半分にする処理」を定義する必要があるので、後者に分がある。

作用素を決める段階で、「区間全体に作用する集約値を計算しやすい」かつ「子に伝播させやすい」情報が何かを考えて決めるとよい。

だが、その中でも区間長をどこから取得するかについて複数ある。

要素 $S$ に持たせる
- $S$ を構造体やタプルで表現して、自身の長さの情報も持たせる
- AtCoder Libraryの使用例で使われている
- もともと載せたい値が整数など単純な値だった場合、タプル化によるメモリ増加や、合成の際に毎回新規タプルを生成するコストが発生する
mapping()の引数に与える
- 区間長はindexから簡単に計算できる。とはいえ、毎回わずかな計算コストは発生する
- MIN,MAXなどは区間長が必要ないのに引数に与えなければならないので、上記が完全に無駄なコストとなる

また、MIN,MAXなどは区間長が必要ないので、汎用性のない（たとえばMINに決め打った）実装ではわざわざ考慮していないことも多い。考慮すると定数倍遅くなるし。

このあたりの方針が、問題によってもどの方法がいいか変わってくることもあるのか、割と統一されてない。

実装例

速度よりカスタマイズ性優先した、各関数を外部注入する形。

非再帰、作用素は非可換でも可、区間長はmapping時に反映（第3引数に区間長を入れる）。

型が2種類出てきてややこしいので、タイプヒンティングをしっかり目に。（実行上は意味ないが、IDEが対応してれば警告が出る）

Python3

from typing import TypeVar, Callable, Sequence

TypeS = TypeVar('TypeS')
TypeT = TypeVar('TypeT')


class LazySegmentTreeInjectable:
    def __init__(
            self,
            n: int,
            operation: Callable[[TypeS, TypeS], TypeS],
            mapping: Callable[[TypeS, TypeT, int], TypeS],
            composition: Callable[[TypeT, TypeT], TypeT],
            e_factory: Callable[[], TypeS],
            id_factory: Callable[[], TypeT], ):
        n2 = 1 << (n - 1).bit_length()
        self.offset = n2
        self.operation = operation
        self.mapping = mapping
        self.composition = composition
        self.e_factory = e_factory
        self.id_factory = id_factory
        self.data = [e_factory() for _ in range(n2 << 1)]
        self.lazy = [id_factory() for _ in range(n2 << 1)]

    @classmethod
    def from_array(
            cls,
            arr: Sequence[TypeS],
            operation: Callable[[TypeS, TypeS], TypeS],
            mapping: Callable[[TypeS, TypeT, int], TypeS],
            composition: Callable[[TypeT, TypeT], TypeT],
            e_factory: Callable[[], TypeS],
            id_factory: Callable[[], TypeT], ):
        ins = cls(len(arr), operation, mapping, composition, e_factory, id_factory)
        data = ins.data
        op = ins.operation
        data[ins.offset:ins.offset + len(arr)] = arr
        for i in range(ins.offset - 1, 0, -1):
            l = i << 1
            data[i] = op(data[l], data[l + 1])
        return ins

    def _propagate(self, i):
        data = self.data
        lazy = self.lazy

        if i < self.offset:
            l = i << 1
            r = l + 1
            lazy[l] = self.composition(lazy[l], lazy[i])
            lazy[r] = self.composition(lazy[r], lazy[i])

        k = self.offset >> (i.bit_length() - 1)
        data[i] = self.mapping(data[i], lazy[i], k)
        lazy[i] = self.id_factory()

    def _recalculate(self, i):
        if i >= self.offset:
            return
        l = i << 1
        r = l + 1
        k = self.offset >> i.bit_length()
        l_dat = self.mapping(self.data[l], self.lazy[l], k)
        r_dat = self.mapping(self.data[r], self.lazy[r], k)
        self.data[i] = self.operation(l_dat, r_dat)

    def _get_overhead_indices(self, l, r):
        """ l, r are already added offset """
        result = []
        l0 = (l // (l & -l)) >> 1
        r0 = (r // (r & -r)) >> 1
        while l0 != r0:
            if l0 > r0:
                result.append(l0)
                l0 >>= 1
            else:
                result.append(r0)
                r0 >>= 1
        while l0:
            result.append(l0)
            l0 >>= 1
        return result

    def apply(self, l: int, r: int, x: TypeT):
        lazy = self.lazy
        cp = self.composition

        l += self.offset
        r += self.offset
        rc_indices = self._get_overhead_indices(l, r)

        for i in reversed(rc_indices):
            self._propagate(i)

        while l < r:
            if l & 1:
                lazy[l] = cp(lazy[l], x)
                l += 1
            if r & 1:
                r -= 1
                lazy[r] = cp(lazy[r], x)
            l >>= 1
            r >>= 1

        for i in rc_indices:
            self._recalculate(i)

    def query(self, l: int, r: int) -> TypeS:
        data = self.data
        lazy = self.lazy
        op = self.operation
        mp = self.mapping

        l += self.offset
        r += self.offset
        rc_indices = self._get_overhead_indices(l, r)

        for i in reversed(rc_indices):
            self._propagate(i)

        res_l = self.e_factory()
        res_r = self.e_factory()
        k = 1
        while l < r:
            if l & 1:
                res_l = op(res_l, mp(data[l], lazy[l], k))
                l += 1
            if r & 1:
                r -= 1
                res_r = op(mp(data[r], lazy[r], k), res_r)
            l >>= 1
            r >>= 1
            k <<= 1

        return op(res_l, res_r)

    def debug_print(self):
        i = 1
        while i <= self.offset:
            print(self.data[i:2 * i])
            i <<= 1
        print('--------')
        i = 1
        while i <= self.offset:
            print(self.lazy[i:2 * i])
            i <<= 1
        print()

目次