セグメント木でできることを整理する

実装方法ではなく使い方のメモです。 計算する区間の添字の流儀は AtCoder Library を参考にしています。

まだ整理できていないもの

• 双対セグメント木
• 2Dセグ木
• 永続セグメント木
• imos法？

フェニック木(Fenwick Tree, Bit Indexed Tree)

一点加算更新・区間加算 のクエリが処理できるデータ構造。

できることは限られているが、同じ処理をセグメント木や遅延セグメント木で行うときよりも高速に動作し、実装も比較的シンプル。

処理できるクエリ

$a = \{a_i\}_{i=0}^{n-1}$ を長さが $n$ で初期値が全て $0$ の配列とする。

1. (一点加算更新) インデックス $i$ と値 $x$ が与えられたとき、配列を $a_i \coloneqq a_i + x$ と更新する。計算量 $O(\log n)$
2. (区間加算) インデックスの組 $(l, r)$ が与えられたとき、区間 $[l, r)$ に対応する配列の要素の和 $\sum_{i=l}^{r-1} a_i$ を計算する。計算量 $O(\log n)$

具体例・例題

• AtCoder Library Practice Contest B - Fenwick Tree

セグメント木(Segment Tree)

一点更新・区間取得 のクエリが処理できるデータ構造。

処理できるクエリ

セグメント木で扱う値の集合は、モノイドである必要がある。 $S = (S, \cdot, e)$ をモノイド、 $a = \{a_i\}_{i=0}^{n-1}$ を長さが $n$ で初期値が全て $e$ の配列とする。

1. (一点更新) インデックス $i$ と値 $x \in S$ が与えられたとき、配列を $a_i = x$ と更新する。計算量 $O(\log n)$
2. (区間取得) インデックスの組 $(l, r)$ が与えられたとき、区間 $[l, r)$ に対応する配列の要素の(モノイドの)積 $\prod_{i=l}^{r-1} a_i$ を計算する。計算量 $O(\log n)$

また、$O(1)$ で $a_i$ の値を一点取得できる。

具体例・例題

• AtCoder Library Practice Contest J - Segment Tree

• (Fenwick Tree) モノイド $S$ の演算を加算 $+$ とすると、Fenwick Treeになる。$S = (\mathbb{Z}, 0, +)$ とすると、整数の配列のFenwickTree。一点更新/一点加算更新は適切に読み替える必要がある。

• (Range Minimum Query) $S=(\mathbb{Z} \cup \{\infty\}, \min, \infty)$ とおくと、区間取得として以下を実現する Range Minimum Query となる。

  • インデックスの組 $(l, r)$ が与えられたとき、区間 $[l, r)$ に対応する配列の要素の最小値 $\min_{i=l}^{r-1} \{a_i\}$ を計算する。

• (BitXor) AtCoder Beginner Contest 185 F - Range Xor Query $S=(\mathbb{Z}, \veebar, 0)$ とすると XOR が処理できる。

• (BitOr) $S=(\mathbb{Z}, \lor, 0)$ とすると OR が処理できる。

• (区間加算・一点取得) セグメント木を利用して、区間加算・一点取得のクエリを処理できる。

  1. (区間加算) インデックスの組 $(l, r)$ と値 $x$ が与えられたとき、区間 $[l, r)$ に対応する配列の要素に $x$ を加算する。つまり、$i \in [l, r)$ に対して $a_i = a_i + x$ と更新する。
  2. (一点取得) $a_i$ の値を取得する。

  これは、前項との差分の数列 $b_i$ に対してモノイド $S = (\mathbb{Z}, 0, +)$ を考慮したセグメント木を作成して管理する、という考え方になる。区間加算については $b_l = b_l + x, b_r = b_r - x$ と 一点取得・一点更新を2回実施し、一点取得に対しては、$\sum_{k=0}^{i}b_k$ を求めるため、区間 $[0, i+1)$ の区間取得を実施すれば良い。(imos法の考え方と似ている)

遅延セグメント木(Lazy Segment Tree)

通常のセグメント木の一点更新は点を含む全ての区間の値を更新するので、区間更新の計算量が多い。 そのため二分木を二つ使って区間取得操作や二度目の更新操作の時まで値の更新を遅延させる。

これにより、区間更新・区間取得 のクエリが処理できる。

処理できるクエリ

遅延セグメント木でもセグメント木と同様に管理する値の集合がモノイドであることを仮定する。 さらに遅延セグメント木では、値の更新処理のクエリも二分木を使って蓄積管理していく対象でもある。 よって、二種類のモノイド構造を考えることになる。

• (セグメント木上に乗せるデータ) モノイド $S = (S, \cdot_S, e_S)$
• (遅延伝播させるデータ) モノイド $X = (X, \cdot_X, e_X)$

さらに、更新処理を行うモノイド $X$ が 更新される側のモノイド $S$ との関係を考えるために、

• モノイド $X$ の モノイド $S$ に対する 右作用 $* : S \times X \rightarrow S$

が定義されているとする。このとき、

1. (区間更新) インデックスの組 $(l, r)$ が与えられたとき、区間 $[l, r)$ に対応する配列の要素に $x$ を作用させる。つまり、$i \in [l, r)$ に対して $a_i = a_i * x$ と更新する。計算量 $O(\log n)$
2. (区間取得) インデックスの組 $(l, r)$ が与えられたとき、区間 $[l, r)$ に対応する配列の要素の(モノイドSに定義された)積 $\prod_{i=l}^{r-1} a_i$ を計算する。計算量 $O(\log n)$

の二つのクエリが処理できる。$a_i$ の値を一点取得する場合はセグメント木とは違い $O(\log n)$ かかる。

具体例・例題

• (セグメント木) セグメント木は遅延セグメント木で次のように表現できる。
  • $S = (S, \cdot_S, e_S)$ をセグメント木で用いているモノイドとする。
  • $X = \{id_S\} \cup \{f_t: S \rightarrow S, s \mapsto t, t\in S\}$ という $S$ から $S$ への写像からなる集合を考え、$\cdot_X$ は写像の合成、 $e_X = id_S$ とすると、$(X, \cdot_X, e_X)$ はセグメント木の代入に対応するモノイドとなる。
  • セグメント木では一点更新・区間取得であったが、遅延セグメント木に上の構造を入れると区間更新・区間取得ができるようになる。
• (区間アフィン更新・区間取得) AtCoder Library Practice Contest K - Range Affine Range Sum
  計算対象は整数列。(正確には $p=998244353$ とした時の $(\mathbb{Z}/p\mathbb{Z}, +, 0)$ を考えている)
  1. インデックスの組 $(l, r)$ と値 $b, c$ が与えられたとき、区間 $[l, r)$ に対応する配列の要素をアフィン変換する。つまり、 $i \in [l, r)$ に対して $a_i = b \times a_i + c$ と更新する。
  2. インデックスの組 $(l, r)$ が与えられたとき、区間 $[l, r)$ に対応する配列の要素の和 $\sum_{i=1}^{r-1}a_i$ を計算する。

$b' \times (b \times a + c) + c' = bb' \times a + (b'c + c')$ だから、$X=(\mathbb{Z} \times \mathbb{Z}, \cdot, (1,0)), (b', c') \cdot (b, c) = (bb', b'c + c')$ と定義することで表現できる。

• (区間最大値更新・区間取得) 競プロ典型 90 問 029 - Long Bricks（★5）
  更新操作は最大値を区間取得 -> 区間代入操作の組み合わせで実現できる。$S = (\mathbb{N}, \max, 0)$ で、$X$ はセグメント木の具体例で考えたものと同じ。
  1. インデックスの組 $(l, r)$ と値 $b, c$ が与えられたとき、区間 $[l, r)$ に対応する配列を次のように更新する。$i \in [l, r)$ に対して $a_i = \max_{i=l}^{r-1} a_i + 1$ と更新する。
  2. インデックスの組 $(l, r)$ が与えられたとき、区間 $[l, r)$ に対応する配列の要素の最大値 $\max_{i=l}^{r-1} a_i$ を計算する。
• (区間更新・区間転倒数取得) AtCoder Library Practice Contest L - Lazy Segment Tree 0と1からなる数列 $A$ に対し、
  1. インデックスの組 $(l, r)$ と値 $b, c$ が与えられたとき、区間 $[l, r)$ に対応する配列を次のように更新する。$i \in [l, r)$ に対して $a_i = 1 - a_i$ と更新する。
  2. インデックスの組 $(l, r)$ が与えられたとき、区間 $[l, r)$ に対応する配列の要素の転倒数を計算する。
• (並び替え) AtCoder Beginner Contest 237 G - Range Sort Query

参考

• プログラミングコンテストチャレンジブック pp.153-172

• セグメント木を徹底解説！0から遅延評価やモノイドまで

• セグメント木 [いかたこのたこつぼ]

• Range Add Query (RAQ)を図でわかりやすく解説

• 双対セグメント木という概念について - うさぎ小屋

• 遅延評価セグメント木 [いかたこのたこつぼ]

• AC Library - Lazy Segtree

• モノイド作用付きモノイド, 遅延セグメントツリー

• 数列 - 遅延伝播セグメントツリー (遅延セグ木)

• chuka231’s blog: Segment Tree problems in Atcoder

• セグメント木で使える演算子 segment tree, lazy 〃(自分用メモ) - perogram

• モノイド - Wikipedia