セグメント木を使う

競技プログラミングに慣れ親しんでいる方なら、セグメント木というデータ構造について、一度は聞いたことがあるでしょう。この記事は、セグメント木の構造を理解する必要はないが、使い方を知っておきたいという方のために書かれています。
この記事では、まずセグメント木について紹介し、それからセグメント木を実際に使う際の技法について紹介します。

セグメント木とは

セグメント木は、固定長配列にいくつかの操作を加えたデータ構造です。セグメント木は、基本的には以下の操作を時間計算量 $O(\log n)$ ですることができます。

• $i$ 番目の要素に $x$ を代入
• $i$ 番目の要素を取得
• $l$ 番目の要素から $r$ 番目の要素のモノイド積^[1]を計算

ここで、モノイドを知らない方もいるかもしれませんので、モノイドについて紹介します。

モノイド

モノイドは、実数や複素数の足し算や掛け算、文字列の連結といった、集合とその演算をまとめたもの（代数的構造）のうち、ある性質を持つものです。モノイドは以下の $4$ つの特徴を持ちます。

• ある集合が対象になる
  • 整数の足し算なら整数が対象、文字列の連結なら文字列が対象です。
  • 異なる集合に対する演算^[2]はモノイドではありません。
• 閉じている
  • 言い換えると、定義域と値域が同じであるということです。
  • 例えば、自然数の足し算は、どうやっても答えは自然数になるので、閉じています。
  • 逆に、自然数の引き算は、答えが自然数でなくなること^[3]があるので閉じていません。
• 結合法則が成り立つ
  • 例えば、足し算なら $(a + b) + c = a + (b + c)$ となります。
  • 逆に、例えば整数に対する演算 $*$ を $a * b = 10a + b$ と定義すると、結合法則が成り立ちません。
• 単位元が存在する
  • 単位元とは、ある集合に対する演算 $*$ があったとき、どのような $x$ に対しても $e * x = x * e = x$ となるような要素 $e$ のことです。
  • 言い換えると、なにかと演算しても答えが変わらないものが単位元です。
  • 例えば、足し算では $0$ 、掛け算では $1$ 、文字列の連結では空文字列が単位元です。

モノイドの例

モノイドは膨大な量がありますが、ここではその一例を紹介します。

• 自然数、整数、有理数、実数、複素数、行列、多項式、有限体の足し算、掛け算
• 自然数の最大公約数（ただし、 $\gcd(0, n) = \gcd(n, 0) = n$ とする場合）、最小公倍数
• 最大値・最小値
• ビット列や集合の論理積、論理和、排他的論理和
• 文字列の連結
• $(a, b), (c, d)$ を正整数のペアとしたとき、 $(a, b) * (c, d) = (a \times 10^d + c, b + d)$

これらは、いずれも上に述べた性質を満たしていることが証明できます。

セグメント木と類似のデータ構造の比較

ここでは、セグメント木と配列や累積和を比較します。

固定長配列との比較

固定長配列は、以下の操作を時間計算量 $O(1)$ でできるデータ構造です。

• $i$ 番目の要素に $x$ を代入
• $i$ 番目の要素を取得

セグメント木と比べると、固定長配列にはモノイド積を計算する機能がありません。

累積和との比較

累積和（正確には、累積和を入れた配列）は、以下の操作を時間計算量 $O(1)$ でできるデータ構造とみなすことができます。

• $1$ 番目の要素から $r$ 番目の要素までのモノイド積を計算

累積和はモノイド積の左端が固定されています。ただし、群（モノイドのうち、逆元を持つもの）の場合は任意の区間のモノイド積を計算できます。
また、累積和は更新ができません。累積和の構造を考えると、更新によって整合性が破壊されたとき、整合性を修正するために要素数に比例する計算量がかかることがわかります。

セグメント木の使い方

以上のように、競技プログラミングにおいて頻繁に使われる基本的なデータ構造とセグメント木の機能の違いがわかりました。
ここでは、セグメント木を競技プログラミングにおいてはどのように使えるかを説明します。

初歩: 累積和の代用として利用する

セグメント木は、多少計算量が悪化しますが、累積和と同様の操作が可能です。よって、累積和の代用として使うことができます。
このような使い方をしても意味はあまりありませんが、セグメント木が初めての方は慣れるためにしておいても悪くないでしょう。

基本: 更新ができる累積和

セグメント木と累積和の違いは、途中で更新ができることです。
累積和だとできないような、更新と計算の両方が必要なクエリも、セグメント木なら答えることができるでしょう。

応用: いもす法

セグメント木を使っていもす法^[4]を行うと、いつでも結果を求めることができます。

例題

問題文

$N$ 要素の整数からなる配列があります。はじめ、配列の要素はすべて $0$ です。
以下の $Q$ 回のクエリを処理してください。

• $1\ l\ r\ x$: $l$ 番目から $r$ 番目の要素すべてに対し、 $x$ を加算する。
• $2\ i$: $i$ 番目の要素を表示する。

制約

• $1 \le N, Q \le 2 \times 10^5$
• $1 \le l \le r \le N$
• $|x| \le 10^9$
• $1 \le i \le N$

解説

$N + 1$ 要素のセグメント木を用意します。
クエリ $1$ が来たとき、セグメント木の $l$ 番目に $x$ を加算し、 $r + 1$ 番目に $-x$ を加算します。
クエリ $2$ が来たとき、セグメント木の $1$ 番目から $i$ 番目までの和を求めます。

応用: 平面走査

筆者の理解が足りないため、後日理解したら書くつもりです……。
参考までに平面操作が使える問題を例題として置いておきます。

Advanced Imos 制約変更版

$N$ 要素の整数からなる配列があります。配列の $i$ 番目の要素を $a_i$ とします。はじめ、 $a_i = A_i$ です。
$Q$ 個のクエリを処理したあとの配列を求めてください。
$j$ 番目のクエリでは、整数 $l_j, x_j, y_j$ が与えられるので、 $k = l_j, l_j+1, \ldots, N$ に対して、 $a_k$ を $x_j a_k + y_j \bmod 998244353$ で置き換える。

制約

• $1 \le N, Q \le 2 \times 10^5$
• $0 \le A_i \lt 998244353$
• $1 \le l_j \le N$
• $0 \le x_j, y_j \lt 998244353$

おわりに

セグメント木は、非常に汎用性が高いデータ構造です。
配列の使い方が何通りも存在するように、セグメント木の使い方も何通りもあります。
ここに書いていないけれど、便利な使い方もたくさんあるでしょう。
セグメント木の便利な使い方を探究してみてください。楽しいと思います。

また、セグメント木には双対セグメント木・遅延セグメント木・Segment Tree Beatsといった進化系のようなものも存在し、これらを使わないと解けないような問題もあります。
これらについてはここでは書きませんが、解説記事もたくさんあるので、読んでみるのも面白いでしょう。

脚注

1. あるモノイド（後述）に対して定義された演算を、複数の要素に対して適用した結果のことです。

2. 例えば、文字列の繰り返しの演算を $\text{文字列} * \text{整数}$ と定義したとき、これはモノイドではありません。

3. $1-2=-1$ など。

4. 数列を差分で管理することで、区間に対する作用を $O(1)$ でする方法。詳しくは https://imoz.jp/algorithms/imos_method.html 。