半群の区間積クエリについて

はじめに

「半群の区間積クエリ」とは、「半群の列 $a_1, \dots, a_n$ が与えられる。区間積 $a_L a_{L+1} \cdots a_R$ を求める（オンライン）クエリに答えよ」という問題です。区間和、区間最小値などがその代表例です。競技プログラミングでもよく目にする問題ですね。私はセグメント木を整備してそれで満足していました。

（・8・）.｡oO

• セグ木が万能だし速いし、それでよくない？
• ブロック分割しまくるとか聞くけど、面倒そう
• よく $\langle O(n), O(\alpha(n)) \rangle$ とかオーダーだけ言及されるけど何なん？ Union Find 使うの？

ですが、ふと調べていくうちにいくつか個人的な発見があったのでそれを記事にします。あくまで個人的な模索なので、体系的な文書などがあればぜひ教えてください。

半群の区間積クエリ

もう一度問題を書いておきましょう。

• 半群の元の列 $a_1, \dots, a_n$ が与えられる
• $L,R$ が指定されるので区間積 $a_L \cdots a_R$ を求めるクエリに答える

私のような学習者の立場からすると、どうしてもセグ木、スパーステーブルなど個々のデータ構造に意識が向きがちです。ですが、ここではまず次の問題を考えましょう。
そもそも、区間積クエリを解けるデータ構造とは何か？

区間積クエリを解けるデータ構造とは？

区間積クエリをデータ構造で解くときは、

• $D$: 部分区間の集合を固定する
• $D$ の各元、つまり区間に対して、区間積を前計算して記録する
• クエリ $L,R$ が与えられたとき、区間 $[L,R]$ をいくつかの $D$ の元を使って表示して、前計算の結果を掛け合わせる

としますよね。有名なデータ構造をこの視点で見ると次のようになります。

データ構造	$D$ の元	区間の表示
セグメント木	二分木の形	$\log n$ 個の交わらない区間の和
disjoint sparse table	中央から累積和（分割統治）	$2$ 個の交わらない区間の和
sparse table	長さ 2 ベキの区間	$2$ 個の（交わる）区間の合併
累積和	端から累積和	$2$ 個の区間の差

データ構造の実装という意味では、以下の内容は重要です。

• $D$: 部分区間の集合について、前計算のしやすさ
• $D$: 部分区間の集合について、前計算へのアクセス時間（前計算データをどう保持するか）
• 区間 $[L,R]$ を具体的に $D$ の区間の和で表すアルゴリズム

しかしここでは、上記の内容はすべてうまくいくという都合の良いモデルを採用しましょう。このモデルでの区間積クエリのデータ構造の本質は区間の集合 $D$ のみとなり、以下の組み合わせ論的問題が本質的です。

メインテーマ

【メインテーマ】
部分区間の集合 $D$ をうまくとって、任意の区間を $D$ の元の少ない個数の和で表せるようにしたい。 $D$ の要素数はできるだけ少ないほうがうれしい。どうとればよいか？

（個人的には、そもそもこの問題に帰着できるということ自体、このモデル化により初めて気づいたことでした。）

さらに「少ない個数の和」を定量的にします。これが区間積クエリのメインとなる問題です。

【メインテーマ２】
部分区間の集合 $D$ をうまくとって、 ${1,2,\dots,n}$ の任意の部分区間を $D$ の元 $k$ 個以下の和（交わらない）で表せるようにしたい。そのような $D$ のうち、要素数の最小値を $S_k(n)$ とおく。 $S_k(n)$ を求めよ。

このように定式化すると、以下のような内容を分析できるようになります。

• 任意の $k$ について $S_k(n)$ が有限か？もしそうならクエリ $O(1)$ は無理、
• クエリ $k$ とメモリ $S_k(n)$ のトレードオフ（両方を小さくすることはできない）
• 逆に $k$ と $S_k(n)$ のバランスをとったらどうなるか？

さて、実はこの問題にはオーダーの意味では答えが知られています。つまり、よい $D$ の構成から得られる $S_k(n)$ の上界と、数学的に得られる $S_k(n)$ の下界のオーダーとが一致しています。たとえば、スパーステーブルは $k=2$ のアルゴリズムとしては最善で、構築に $O(n \log n)$ かかるのも仕方がないことがわかります。また、$k=4$ とするだけで構築 $O(n \log^{*} n)$ という実用上ほぼ線形オーダーが得られることもわかります。ここからはそれを紹介しましょう。

上界（よい構成）について

本節の内容は以下の参考文献に基づいています。

Alon, N., Schieber, B.: Optimal preprocessing for answeringon-line product queries. Technical Report TR 71/87, Tel-AvivUniversity (1987)

Seidel のスライド: Understanding the inverse Ackermann function
http://cgi.di.uoa.gr/~ewcg06/invited/Seidel.pdf

（以下の論文は読めてない）
Yao, A.C.-C.: Space-time tradeoff for answering range queries (extended abstract). In: Proceedings of ACM Symposium on Theory of Computing, pp. 128–136 (1982)

$k=1$ の場合は、明らかにすべてを前計算する必要があるので $S_1(n) = n(n+1)/2$ です。
$k$ が一般の場合の基本戦略は分割統治法です。

k=2 の場合

区間を２つずつに分ける分割統治法です。
いま区間 $[L,R)$ についての問題を解きます。真ん中 $M = (L+R)/2$ から左右に累積和をのばしたものを前計算します。すると、「$M$ をまたぐ区間」についてはこれら２つの区間の和で書けます。書けないのは「$[L,M)$ に含まれる区間」と「$[L,M)$ に含まれる区間」です。こうしてサイズが半分の問題２つに帰着できました。

文章で長々書きましたが、じつはこれ、 disjoint sparse table そのものです！（想像していたより自然に出てきたのでびっくりしました。）

さてこの再帰から、以下の式が得られます。
$$
S_2(n) \le 2n + S_2(n/2)
$$
この式を解いて、$S_2(n) \le 2n \log_2 n$ がわかります（以下の一般論からわかります）。

分割統治法から得られる不等式

ここからは、サイズ $n$ の問題をブロックサイズ $f(n)$ の問題 $n/f(n)$ 個に分割している様子をイメージしてください。
以下の定理が重要です（証明は帰納法によります）。

$f$ を $f(n) < n$ をみたす関数とする。
$$
T(n) \le an + \frac{n}{f(n)} T(f(n))
$$
が任意の $n$ について成り立つとき、
$$
T(n) \le an f^{*}(n)
$$
が成り立つ、ここで $f^{*}(n)$ は $f^{*}(n) = 1 + f^{*}(f(n))$ として再帰的に定義される関数で、つまり「$f( \cdots f(f(n))) < 1$ となるまで何回かかるか？」を意味する。

とくに $k=2$ のときは $f(n) = n/2$ となるので $f^{*}(n) = \log_2 n$ となります。
この例のように、おおむね $f$ に比べて $f^{*}$ は増え方が遅くなります。

k が一般の場合

サイズ $n$ の問題を、ブロックサイズ $f(n)$ の問題 $n/f(n)$ 個に分割します。$f(n)$ はあとで決めます。

ブロックをまたぐ長いクエリについては、真ん中の「ブロックすべてを使う部分」と左右両端の「ブロックの一部のみ使う部分」に分けて計算することにします。「ブロックの一部のみ使う部分」はすべて前計算することにします。するとクエリを $k$ 個以下の区間の和で計算するために、

「左端」＋「ブロックを単位とする $k-2$ 個以下の区間」＋「右端」

とすればよいです。ここで「ブロックすべてを使う部分」は、「ブロックを単位とする、 $k-2$ に対応するデータ構造」を使って前計算します。よってこのパートはサイズと $k$ 両方が小さい問題に帰着できました。

残るのは各ブロックにおさまる区間だけなので、サイズの小さな問題に帰着できました。

この再帰で必要な前計算は

• $n/f(n)$ 個のブロックに $k-2$ のデータ構造を使う: $S_{k-2}(n/f(n))$ 個
• 各ブロックの仕切りから左右に累積和を伸ばす: $2n$ 個 であり、残りはサイズ $S_k(f(n))$ の問題 $n/f(n)$ 個なので、式 $$ S_k(n) \le 2n + S_{k-2}(n/f(n)) + \frac{n}{f(n)}S_k(f(n)) $$ を得ます。ここから $K$ に応じて適切な $f(n)$ を決めていきます。

k=3 のとき

定理を使うために、 $S_{1}(n/f(n))$ を線形オーダーにさせたいので $f(n) = \sqrt{n}$ と設定します。すると
$$
S_3(n) \le 3n + \frac{n}{f(n)}S_3(f(n))
$$
となり、定理から
$$
S_3(n) \le 3n f^{*}(n) = 3n \log \log n
$$
がわかります。

さて、 $f(n) = \sqrt{n}$ としたので、$k=3$ に対応するこのデータ構造は平方分割を再帰的に繰り返します。このデータ構造は sqrt tree として知られています。

k が一般の偶数のとき

次の式が成り立ちます。
$$
S_{2k}(n) \le 2kn f(n) \implies S_{2k+2}(n) \le (2k+2)n f^{*}(n).
$$
証明の概略としては、仮定の式 $S_{2k}(n) \le 2kn f(n)$ の $f(n)$ とブロック分割の関数 $f(n)$ を一致させることで、分割統治法の不等式から帰納的に成り立ちます。

この式を繰り返し使うと、数学的帰納法により、
$$
S_{2k}(n) \le 2kn \log^{* \dots *}(n)
$$
が証明できます。

$k$ が一般の奇数のときは略します（同様の手法が使えます）。

メモリとクエリのバランスをとると逆アッカーマン関数が出る

ここまで $k$ を定数としてきましたが、$n$ に応じて $k$ を増やすことにします。
$\alpha(n)$ を、$\log^{* \dots *}(n) \le 2$ となる最小のスターの個数と定めます（これが本質的に逆アッカーマン関数と同程度の関数となる）
ここで $k = \alpha(n)$ とすると $S_{2\alpha(n)}(n) \le 2\alpha(n)n$ となります。
つまり構築 $O(\alpha(n)n)$ クエリ $O(\alpha(n))$ となります。

メモリ線形

また、メモリは線形で抑えることもできます。あらかじめブロックサイズ $\alpha(n)$ のブロックに分割しておいて、はみ出た部分は愚直でもクエリのオーダーは変わりません。$n/\alpha(n)$ 個のブロックに対して上記のアルゴリズムを構築します。

雑談

そもそも $k=3$ での $\log \log n$ も増加が極めて遅いし、なんなら $k=4$ のときに出てくる関数 $\log^{*}(n)$ は、テトレーションの逆関数になるのでほぼ定数です。具体例でみてみましょう。 $\log^{*}$ は $\log$ を何回取ったら $1$ になるかという関数だったので、 $2^{65536} \to 65536 \to 16 \to 4 \to 2 \to 1$ より $\log^{*}(2^{65536}) = 5$ とわかります。

そもそもアッカーマン関数の定義が、積、テトレーション、その繰り返し... という階層を対角線状に見てます。 関数の階層が上がることと、その逆関数にスターが増えることがだいたい対応してます。なので逆アッカーマン関数はこの階層のいかなる関数の逆関数よりも漸近的に小さくなるということで、並みの想像では追いつかないですね。

下界について

ここでは簡単に示せる $K=2$ のときの証明を書いておきます。
一般的な状況での証明はたとえば以下の参考文献にあります。

Hu, X., Tao, Y., Yang, Y., & Zhou, S. (2018). Semi-Group Range Sum Revisited: Query-Space Lower Bound Tightened. Algorithmica, 80(4), 1315-1329.

k=2 のときの証明

長さ $1,3,7,15, \dots$ の区間はそれぞれ $n,n-2,n-6, n-14, \dots, $ 個。つまり合計 $n \log n$ に比例する個数の区間がある。いま $k=2$ なので、これらの区間すべてが $2$ 個以下の区間に分割されるので、そのうち長いほうに注目する。このとき同じ区間は高々 $2$ 回しか現れない（というのも、異なる長さの区間から切り出された２つの区間は、そもそも長さが一致することはない。あとは、切り出された区間が左端か右端かのどちらかなので出現は高々 $2$ 回）。よって $n \log n$ に比例する個数の区間がどうしても必要になる。

構築 O(n) クエリ O(1) のアルゴリズムについて

上で見た通り、「半群の区間積クエリ」の問題設定では、計算量の上限と下限が一致していて、とくに構築 $O(n)$, クエリ $O(1)$ のアルゴリズムは存在しません。ところで、RMQ では構築 $O(n)$, クエリ $O(1)$ のアルゴリズムがある、という噂を聞きますが、これって矛盾してませんか？
いいえ、矛盾してないのです。つまり、構築 $O(n)$ クエリ $O(1)$ のアルゴリズムは半群の性質以外の何かを使っているということです。つまりそこに注目してアルゴリズムを眺めるのが吉。

構築 $O(n)$ クエリ $O(1)$ のアルゴリズムの戦略としては以下が一般的なようです。

• 列をブロックサイズ $(\log n)/2$ のブロック $2n/(\log n)$ 個に分割する。
• ブロックをまたぐクエリは、$2n/(\log n)$ 個のブロックについて (disjoint) sparse table で処理
  • この部分はいつでも $\langle O(n), O(1) \rangle$（$k=2$ のデータ構造で十分構築が高速になる）
• ブロック内（小さい区間）のクエリを、なんとかして $O(1)$ で処理
  • この部分で各演算の特殊性を使う

こうして「任意の半群でうまくいくパート」と「問題の特殊性を使うパート」にアルゴリズムを分けることができました。あとは、ブロック内のクエリを問題の特殊性をどう使って処理するかの具体例を見てみましょう。

• $\pm1$ RMQ（隣り合う要素の差が $\pm1$）
  • 小さいサイズのブロックのパターンが十分小さいので、事前に全列挙、前計算できる
  • 各マスが増える、減るの２パターンなので、サイズ $(\log n)/2$ のブロックのパターン $2^{(\log n)/2} = \sqrt{N}$ 通りを全列挙する
  • 参考文献 https://www.topcoder.com/thrive/articles/Range%20Minimum%20Query%20and%20Lowest%20Common%20Ancestor
  • ちなみに「小さいサイズを全列挙」することで高速化する例としては、 level ancestor problem や, 4人のロシア人の方法などがある
• RMQ
  • スライド最小値的なアイデアとビット演算で頑張る
  • 参考文献１ https://qiita.com/okateim/items/e2f4a734db4e5f90e410
  • 参考文献２ https://noshi91.hatenablog.com/entry/2018/08/16/125415

前計算の計算グラフ

さて、ここまでは計算側に都合の良いモデルを考えていました。ここでは無視していた「 $D$ の各元に対して、区間積を前計算して記録する」の部分に焦点を当てます。

たとえば累積和のデータ構造では $x_1, x_1x_2, x_1x_2x_3, \dots$ を計算しますが、これらを個別に計算する人はいません。もちろん（累積和の名前通り）計算結果を再利用して効率よく計算します。この計算過程をグラフにしたものを、ここでは「前計算グラフ」と呼びましょう（ここだけの用語です）。前計算グラフは DAG となり、前計算は DAG 上の DP とみなすこともできます。例えば累積和とセグメント木に対応する計算グラフは下図のようになります。

つまり、さきほどの都合のよいモデルでは集合 $D$ がデータ構造の本質だと思っていましたが、前計算込みで考えると $D$ と計算グラフの組が本質であるといえます。

区間乗算全点取得問題

さて章が切り替わったところで、新しい問題を考えましょう。区間乗算全点取得とは、以下のような問題です。

• $M$を可換モノイドとする。（「初期値」があると嬉しいので半群でなくモノイド）
• 初期状態では $a_0 = \cdots = a_{n-1} = 1$ である。($1$ はモノイドの単位元。)
• 「$a_L, \dots, a_R$ に $x$ を掛ける」というクエリがいくつか与えられる。
• クエリを適用し終わったとき、列 $a_0, \dots, a_{n-1}$ の値を求めよ。

例えば「区間に数を足す」問題はこの問題の一例です。今回も具体的なデータ構造ではなく、そもそも区間乗算全点取得を解けるデータ構造とはどういうものか？を考えましょう。

区間乗算全点取得を解けるデータ構造とはどういうものか？

いきなりですが、区間乗算全点取得は以下のようにして解けます。

• $D$: 部分集合の集合を固定する
• 区間 $I$ に $x$ を掛けるというクエリが来たときは、区間の元すべてに掛け算する代わりに 　　$I = I_1 \cup I_2 \cup \dots \cup I_k$ と $D$ の元の（交わらない）和で書いて、「$I_i$ に $x$ を掛ける」という情報を覚えておく。
• クエリがすべて終わったあと、「後計算」により、各元への影響を計算する。

このように、区間乗算全点取得でも「うまい $D$ をとる」というメインテーマが現れます。

後計算の効率性について

せっかくクエリを効率化しても、後計算で $D$ の各元の影響を個別に計算するのは無駄な場合があります（累積和の場合と同様）。「後計算グラフ」を導入して、後計算グラフに沿ってDPをしていくと考えるのがよいです。

前計算と後計算の双対性

実は、「可換半群の区間積クエリ（のデータ構造）」と「可換モノイドの区間乗算全点取得（のデータ構造）」は、以下のような双対性が成り立ちます。

【双対性】
可換半群の区間積クエリの、前計算グラフこみのデータ構造 $D$ が与えられる。このとき、前計算グラフの辺の向きを反転させることで、可換モノイドの区間乗算全点取得の後計算グラフ込みのデータ構造が得られる。
また逆方向も同様。

たとえば累積和のデータ構造の前計算グラフを逆向きにすると、いもす法が得られます。また、後計算 $O(n \log n)$ クエリ $k=2$ のデータ構造は、(disjoint) sparse table の双対で作れます。原理的にはもちろん後計算 $O(n \alpha(n))$ クエリ $O\alpha(n)$ のデータ構造も双対性を使って作れます。

双対セグメント木について、もしくは双対性における一点更新と一点取得の対応

さて、競プロ界には「双対セグメント木」として知られているデータ構造があります。
https://kmyk.github.io/blog/blog/2019/02/22/dual-segment-tree/
命名者？の kimiyuki さんのページ（上のリンク）によると、双対セグメント木は「遅延セグメント木で作用素が乗るほうの木」と定義され、モノイドの区間乗算、１点取得を高速にこなせます。

実は双対セグメント木は、セグメント木の（本文章の意味での）双対になっています。さらに、「セグメント木」と「双対セグメント木」の双対性とみなされている「１点更新区間取得」と「区間更新１点取得」の対応についても双対性で説明できます。

つまり、区間積クエリ側の１点更新は「計算グラフについて、更新したい頂点からたどり着くノードすべての値を更新する」となります。一方で、区間乗算クエリ側の１点取得は「計算グラフについて、取得したい頂点にたどり着くノードすべての値を足す」となります。双対で計算グラフの辺の向きが逆になるので、頂点集合としては同じものをとってきています。まとめると、

【双対性】
「可換半群の１点更新、区間積（のデータ構造）」と「可換モノイドの区間乗算、１点取得（のデータ構造）」が双対である。

たとえば双対 Fenwick tree を本文章の意味での双対性を使って定義することができます。

注意

双対セグメント木は「遅延伝播」により非可換なモノイドの区間乗算も高速にこなすことができます。遅延伝播は上の双対性の観点からは説明できません（たぶん）。

区間に辺を張るテク

区間に辺を張るテクニックは、以下のように辺を張る大量の操作を捌くテクニックです。

• 頂点 $x$ から $L \le x \le R$ をみたす各頂点 $y$ に辺を張る
• $L \le x \le R$ をみたす各頂点 $x$ から頂点 $y$ に辺を張る
• $L \le x \le R$ をみたす各頂点 $x$ から $L \le x \le R$ をみたす各頂点 $y$ に辺を張る

具体的な手法は、たとえば以下のツイートの説明が明瞭です。

セグ木の形にして区間に辺を張るテク
頂点 +N 個
辺 +N+ElogN 個 pic.twitter.com/Xrw5y9bq2Z

— 熨斗袋 (@noshi91) November 9, 2019

この構造自体面白いものですが、今回はやはり個別の構造にとらわれない議論をしましょう。

区間に辺を張るテクとはどういうものか？

区間に辺を張るテクとは、区間のすべての点に辺を張る代わりに、区間をいくつかの区間の和で書いて、そこに/そこから辺を張るというテクです。すなわち以下のように解けます。

• $D$: 部分集合の集合を固定する
• 頂点 $x$ から区間 $I$ に 辺を張るというクエリが来たときは、区間の元すべてに辺を張る代わりに 　　$I = I_1 \cup I_2 \cup \dots \cup I_k$ と $D$ の元の（交わらない）和で書いて、$I_i$ に $x$ から辺を張る
• 区間から点に辺を張る場合も同様
• 区間から区間に辺を張る場合は、区間を代表する超頂点を（上記引用ツイートのように）つくれば、やはり同様
• クエリがすべて終わったあと、「後計算」により、$D$ の元から各辺に効率的に辺を張る

こう書くと、もはやこれまでの話との類似性は明らかですね。つまり、「区間に辺を張るテク」は本質的にメインテーマの問題に帰着されます。具体的には、区間に辺を張るテクのグラフ構造として $D$ の前計算/後計算グラフそのものが使えます。この意味で「半群の区間積クエリ」と「区間に辺を張るテク」は同じ問題です。

まとめ

「半群の区間積クエリのデータ構造」についてメモリと計算量のトレードオフや、上界と下界のオーダーが一致することを見ました。

「半群の区間積クエリのデータ構造」、「区間乗算全点取得のデータ構造」、「区間に辺を張るテク」というテーマが、「（前計算グラフ付きの）部分集合の集合$D$をうまくとって、任意の区間を$D$の元の和で書く」という同じ問題（メインテーマ）を根っこに持っていることを確認しました。