セグメント木

• プログラミングコンテストでのデータ構造 (スライド33～)
• セグメント木について - beet's soil

• 動画での解説
  • 【木マスター養成講座】4-1. Segment木ってなに〜？導入編【競プロかつっぱ】
  • 【木マスター養成講座】4-2. Segment木ってなに〜？なんかうまく区間取ってくる編【競プロかつっぱ】

区間に対する集約処理をするときによく使われる。
$a_1,a_2,...,a_n$ の配列に対し、以下を処理する。（一点更新・区間取得）

• $update(i,x)$ : $a_i$ を $x$ で更新する
• $query(l,r)$ : 区間 $[l,r) = a_l,a_{l+1},...,a_{r-1}$ の集約値を求める

「集約」には、身近な例では総和とか最小値とかがあてはまる。

どんな「$a_i$ の型」に対して、どんな「集約操作」を行うか、という（型, 操作）の組を、セグメント木は柔軟に変えられる。

たとえば前者が『整数全体の集合』なら、演算はたとえば以下のことが可能である。

• 区間和、区間積
• MIN, MAX
• 最小公倍数LCM、最大公約数GCD
• ビット演算 AND、OR、XOR

より厳密に定義しようとすると多少抽象的な話になる。

モノイド であればセグメント木で管理することができるとされている。 モノイドとは、例えば「整数全体」と「足し算」のように、ある要素の集合 $S$ とその上での二項演算 $\bullet$ の組合せ $(S, \bullet)$ の内、以下の条件を満たすものである。

• 結合律が成り立つ＝計算の順序を入れ替えてもいい
  • $(a \bullet b) \bullet c = a \bullet (b \bullet c)$
• 単位元が存在する
  • $S$ のどんな要素 $a$ に対しても影響を及ぼさない要素 $e$ が存在する
  • $a \bullet e = e \bullet a = a$

聞き馴染みが無くとも、足し算とかかけ算とか、割と身近なものでこの性質を満たすものは多い。

結合律が必要な理由については、セグメント木は以下のような形でまとまった区間を前計算して、必要な部分を掻い摘まんで集約するので、

|        1*2*3*4*5*6*7*8        |
|    1*2*3*4    |    5*6*7*8    |
|  1*2  |  3*4  |  5*6  |  7*8  |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |

↓ 2～6の集約値を求めるのに参照する箇所

|                               |
|               |               |    2 * (3*4) * (5*6)
|       |  3*4  |  5*6  |       |
|   | 2 |   |   |   |   |   |   |

ここでもし * の演算が結合率を満たさず $(((2*3)*4)*5)*6 \neq 2*(3*4)*(5*6)$ だと困ることが分かる。
結合律が成り立たない例としては、実数と冪乗が挙げられる。$\displaystyle (4^3)^2=4096, 4^{(3^2)}=262144$

単位元が存在しない例としては、自然数と足し算があげられる。（足し算は単位元が0だが、自然数に0は含まれない）
単位元の存在は初期値を埋めておくための実装上の問題。

だが、実は単位元は $S$ をちょっと拡張することで無理矢理作ることも出来て、 たとえばタプルにして「自身は単位元であるフラグ」を付け、それがTrueのものとの演算は常にもう片方を返すようにする、などで単位元と振る舞い的に変わらなくなる。
問題を解く上で絶対に $S$ はこの型でないといけない、なんてことは普通無いので、単位元はあまり気にしなくてよい。

構造が比較的単純なため、バリエーションもいくつかある。

• 一点更新・区間取得（基本）
• 区間更新・一点取得（双対セグメント木）
• 区間更新・区間取得（遅延セグメント木）
• 多次元化
• 永続化
  • 更新を加えたときに、後から遡って「時刻 $t$ での状態」を復元できる構造

区間更新・一点取得を行えるデータ構造。できることが通常のセグメント木と逆。

通常のセグメント木は、「更新は、一番下から上に遡上して状態を更新」「取得は、なるべく広い区間をまとめて取得」

【通常のセグメント木】
|       +       |    [更新]
|   +   |       |    +: i=3 を更新する際に更新が必要なノード
|   | + |   |   |
| | | |+| | | | |       一番下のノードから、真上のノードを順次更新
 0 1 2 3 4 5 6 7

|               |    [取得]
|       |   *   |    *: [1, 8)の集約値を取得するのに参照するノード
|   | * |   |   |
| |*| | | | | | |       2～3, 4～7 の部分は末端を参照しなくてよい
 0 1 2 3 4 5 6 7

双対は、操作も逆。

【双対セグメント木】
|               |    [更新]
|       |   +   |    +: [1, 8) を更新するときに更新するノード
|   | + |   |   |
| |+| | | | | | |       2～3, 4～7 の部分は末端を更新しなくてよい
 0 1 2 3 4 5 6 7

|       *       |    [取得]
|   *   |       |    *: i=3 を取得する際に参照するノード
|   | * |   |   |
| | | |*| | | | |       一番下のノードから、真上のノードに溜まった更新値を合成していく

可換性 とは、操作の順番を入れ替えても答えが変わらない性質。足し算やかけ算、MINやMAXなど、これが成り立つものは多い。

• $(a+b)+c=(a+c)+b$

モノイドの要件には入っていないので、セグ木に載せる上で必ずしも成り立っている必要は無い。
ただしもし非可換なら、通常のセグ木の場合、演算の左と右に来るものを取っ替えないように注意する必要がある。

通常のセグ木では注意するくらいで済むが、双対セグ木では、必要な実装がかなり変わってくる。
具体的に言うと、更新時、更新したいノードより上に溜まっているものがあれば、下まで押し込む必要がある。¹⁾

以下の例を考える。演算として + を使っているが、今はこれが可換性が成り立たない演算とする。

|               |    [更新]
|   5   |       |    [0, 4) に 5 が足された
|   | 3 |   |   |    [3, 4) に 1 が足された
| | | |1| | | | |    [2, 4) に 3 が足された
 0 1 2 3 4 5 6 7

この時、取得するときもこの更新順に合成しなければならない。たとえば $i=3$ に対しては $5+1+3$ としなければならない。
しかし、このまま下から合成すると $1+3+5$ となり、間違った答えとなる。

ここで、$5$ が足された後、より狭い範囲に対して更新操作があったら下まで押し込むようにすると、

|               |    [更新]
|   5   |       |
|   |   |   |   |    [3, 4) に 1 を足したい
| | | | | | | | |
 0 1 2 3 4 5 6 7

|               |
|       |       |    押し込む
| 5 | 5 |   |   |
| | | | | | | | |

|               |
|       |       |    押し込む
| 5 |   |   |   |
| | |5|5| | | | |

|               |    更新したいノードより上のノードに
|       |       |    溜まっている値が無くなったところで、
| 5 |   |   |   |    改めて [3, 4) に 1 を足す
| | |5|6| | | | |

|               |    
|       |       |    [2, 4) に 3 を足す
| 5 | 3 |   |   |    下の方に溜まっている値があるのは気にしなくてよい
| | |5|6| | | | |
 0 1 2 3 4 5 6 7

これで、$i=3$ を取得するときは下から順に合成していけばよくなる。
$6+3$ となるが、$6$ は $5+1$ をこの順に演算した結果なのでこれは $(5+1)+3$ であり、正しく求められている。

具体的にどこを押し込むか。
更新が必要なノードのうち、左端と右端の、真上一直線上のノードに溜まっている値は上から順に押し込むとよい。最大 $2 \log{N}$ 個。

|               v               |
|       v       |       v       |    [4, 13) を更新
|       |   u   |   u   |   v   |    u: 更新が必要なノード
|   |   |   |   |   |   | v |   |    v: 押し込みが必要なノード（上から順に）
| | | | | | | | | | | | |u| | | |
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5

区間の両端の真上一直線上のノードだけでいいのは、 「これより外のノードは、そもそも更新しないので関係ない」 「この間に完全に含まれるノードは、必ず一番上のノードで受け止められ、下のノードは更新されないので押し込む必要は無い」と思えばよい。

区間更新・区間取得ができる。上位互換だが、まぁ実装重くなるしバグも埋め込みやすくなるので、過不足の無いデータ構造を選ぶ。

• 遅延評価セグメント木

セグメント木を、機能を限定的にして実装を軽くしたものの1つに、Fenwick木（Binary Indexed Tree）がある。

• Binary Indexed Tree

セグメント木には、2つのindex（っぽい概念）が登場する。

• (1) updateやqueryで与えられる $a_i$ の $i$ を指すindex
• (2) 二分木を1つの配列で表現する実装において、その配列上のindex

      １
     /  \
   ２    ３     ←(2)
  / \    / \
４  ５  ６  ７
||  ||  ||  ||    対応
a1  a2  a3  a4  ←(1)

indexは、0始まりか1始まりかを意識する必要がある。

プログラム全般的には、多くの言語で配列の添字が0-indexなのでそれに倣うことが多いが、 特に(2)の二分木の実装では、1-indexにした方が都合が良い。

2進数にしたとき、深さと桁数が一致する。また、子のindexを右bitshiftすると親になるので、親子を辿るindexの計算が簡潔になる。

        0001
       /   \
    0010   0011
    / \     / \
0100 0101 0110 0111

• 2019/11 get_min() を、indexとbit演算を使った書き方に変更（速度up）

整数と区間最小値

class SegTreeMin:
    """
    以下のクエリを処理する
    1.update:  i番目の値をxに更新する
    2.get_min: 区間[l, r)の最小値を得る
    """

    def __init__(self, n, INF):
        """
        :param n: 要素数
        :param INF: 初期値（入りうる要素より十分に大きな数）
        """
        n2 = 1 << (n - 1).bit_length()
        self.offset = n2
        self.tree = [INF] * (n2 << 1)
        self.INF = INF

    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.offset
        self.tree[i] = x
        while i > 1:
            y = self.tree[i ^ 1]
            if y <= x:
                break
            i >>= 1
            self.tree[i] = x

    def get_min(self, a, b):
        """
        [a, b)の最小値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        result = self.INF

        l = a + self.offset
        r = b + self.offset
        while l < r:
            if r & 1:
                result = min(result, self.tree[r - 1])
            if l & 1:
                result = min(result, self.tree[l])
                l += 1
            l >>= 1
            r >>= 1

        return result

書き方がシンプルになり人によってはアレンジしやすくなる一方、Python、PyPyでは相対的に遅くなるため非推奨。

整数と区間最小値

class SegTreeMin:
    """
    以下のクエリを処理する
    1.update:  i番目の値をxに更新する
    2.get_min: 区間[l, r)の最小値を得る
    """

    def __init__(self, n):
        """
        :param n: 要素数
        """
        self.n = n
        # nより大きい2の冪数
        n2 = 1
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [float('inf')] * (n2 << 1)

    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.n2
        self.tree[i] = x
        while i > 1:
            self.tree[i >> 1] = x = min(x, self.tree[i ^ 1])
            i >>= 1

    def get_min(self, a, b):
        """
        [a, b)の最小値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        return self._get_min(a, b, 1, 0, self.n2)

    def _get_min(self, a, b, k, l, r):
        """
        [a, b)の最小値を得る内部関数
        :param k: 現在調べている区間のtree内index
        :param l, r: kが表す区間の左右端index [l, r)
        :return: kが表す区間と[a, b)の共通区間内での最小値。共通区間を持たない場合はINF
        """
        if r <= a or b <= l:
            return float('inf')
        # [a,b)が完全に[l,r)を包含するならtree[k]で更新
        if a <= l and r <= b:
            return self.tree[k]
        # 一部だけ範囲内なら2つに分けて再帰的に調査
        m = (l + r) // 2
        return min(
            self._get_min(a, b, k << 1, l, m),
            self._get_min(a, b, (k << 1) + 1, m, r)
        )

# --------------------------
st = SegTreeMin(30)
st.update(10, 5)
st.update(20, 4)
print(st.get_min(5, 15)) # => 5
print(st.get_min(5, 25)) # => 4
st.update(11, 3)
print(st.get_min(5, 25)) # => 3

（単位元、演算）を外部から与えられるようにして柔軟性を持たせた形。ただし実行速度は多少悪くなる。

モノイドは可換でなくてもOK（のはず）。

Python3

class SegmentTreeInjectable:
    def __init__(self, n, e_factory, operator):
        """
        :param n: 要素数
        :param e_factory: func() -> S 単位元を生成する関数
        :param operator: func(S, S) -> S 親ノードが子ノード同士を合成する関数
        """
        n2 = 1 << (n - 1).bit_length()
        self.offset = n2
        self.data = [e_factory() for _ in range(n2 << 1)]
        self.op = operator
        self.e = e_factory

    @classmethod
    def from_array(cls, arr, e_factory, operator):
        """ 既存の配列から生成 """
        ins = cls(len(arr), e_factory, operator)
        ins.data[ins.offset:ins.offset + len(arr)] = arr
        for i in range(ins.offset - 1, 0, -1):
            lch = i << 1
            ins.data[i] = operator(ins.data[lch], ins.data[lch + 1])
        return ins

    def update(self, i, x):
        """ Aiをxに上書き更新 """
        # 上書きでなくて加算などで更新したい場合は、get_point() で現在値を取得して呼び出し元で行う
        data = self.data
        op = self.op
        i += self.offset
        data[i] = x
        while i > 1:
            i >>= 1
            lch = i << 1
            data[i] = op(data[lch], data[lch + 1])

    def get_point(self, p):
        return self.data[p + self.offset]

    def get_range(self, l, r):
        """ [l, r) の値を得る """
        data = self.data
        op = self.op
        result_l = self.e()
        result_r = self.e()

        l += self.offset
        r += self.offset
        while l < r:
            if l & 1:
                result_l = op(result_l, data[l])
                l += 1
            if r & 1:
                r -= 1
                result_r = op(data[r], result_r)
            l >>= 1
            r >>= 1

        return op(result_l, result_r)