結合的な区間要約・区間分解・合成

概要

列の一部を毎回走査する代わりに、短い区間の結果を組み合わせて答えを作りたい。そのために、区間を分けても、元の順序で結合すれば同じ結果になるという性質を使う。ここではSegment Treeを通して、区間の分解と順序を保つ結合を学ぶ。何を要約すれば答えを作れるかの設計は、子単元の区間monoid要約で扱う。

考え方

括る位置を変えても、並び順は変えない

隣り合う区間の要約を結合する演算を ⊗\otimes とする。結合結果も同じ種類の要約になり、任意の要約 x,y,zx,y,z について

(x⊗y)⊗z=x⊗(y⊗z)(x\otimes y)\otimes z=x\otimes(y\otimes z)

が成り立つことを結合則という。これにより、左から一つずつ結合する代わりに、いくつかのまとまりを先に作って結合できる。また、左右のどちらにつないでも相手を変えない要約 ee、すなわち e⊗x=x⊗e=xe\otimes x=x\otimes e=x を単位元という。区間集約では空区間の要約に対応する。結合則と単位元を備えたこの仕組みをmonoid(モノイド)、列を元の順に結合して一つの値にする操作をfold(畳み込み)という。結合結果を区間積とも呼ぶ。

例えば文字列連結なら、a と bc をつなげても、ab と c をつなげても abc になる。単位元は空文字列 "" である。一方、ab と cd の順序を逆にすると cdab になってしまう。結合則で変えられるのは括る位置だけであり、左右を交換できる可換性とは別の性質である。

二分した区間の結果を保存する

列の長さを N≥1N\geq 1、要素を0始まりで a0,…,aN−1a_0,\ldots,a_{N-1} とする。全区間の結果を保存すると個数が二次的に増えるので、まず全体を半分ずつに分けた木の区間だけを保存する。これがSegment Treeである。

葉数を NN 以上の最小の2冪 PP に広げ、根の添字を1とする配列 tree を使う。葉 tree[P+i] には aia_i の要約を置く。余った葉には単位元を置く。この埋め草をpaddingという。内部節点 vv は、左の子を先にして次のように作る。

tree[v]=tree[2v]⊗tree[2v+1]\mathrm{tree}[v]=\mathrm{tree}[2v]\otimes\mathrm{tree}[2v+1]

葉に近い節点から計算すれば、各節点は担当区間を元順に結合した要約を持つ。一点の値を変更したときは、その葉を置き換え、親から根へ順に再計算する。変更位置を含む区間だけが変わるので、他の節点を触る必要はない。

順序を見るため、長さ7の列 a, b, c, d, e, f, g を文字列連結で扱ってみよう。以下は非実行の模型であり、実際に文字列を保存して高速化する実装例ではない。このとき P=8P=8 で、葉とそのすぐ上の要約は次のようになる。

担当区間葉の値親の要約
[0,2)[0,2)a, btree[4] = ab
[2,4)[2,4)c, dtree[5] = cd
[4,6)[4,6)e, ftree[6] = ef
[6,8)[6,8)g, ""tree[7] = g

ここで [l,r)[l,r) は位置 ll 以上、rr 未満の半開区間を表す。最後の葉の空文字列がpaddingである。さらに結合すると左半分は abcd、右半分は efg、根は abcdefg になる。余分な葉があっても、単位元なら実際の列の区間積を変えない。

左から取る区間と右から取る区間を分ける

問い合わせ区間を [l,r)[l,r)、0≤l≤r≤N0\leq l\leq r\leq N とする。木の節点を使って区間を飛び越せれば、一要素ずつ読む必要はない。ただし、分解した区間は左端側と右端側の両方から見つかる。そこで左側の累積 LL と右側の累積 RR をそれぞれ単位元で初期化する。

木上の左右の境界添字を p=P+l, q=P+rp=P+l,\ q=P+r とし、p<qp<q の間、次を繰り返す。

  1. pp が奇数なら、節点 pp は右の子である。左の兄弟は問い合わせ範囲の外なので、親ごと取ることはできない。この節点だけを取り込み、L←L⊗tree[p]L\leftarrow L\otimes\mathrm{tree}[p] として pp を1増やす。
  2. qq が奇数なら、範囲内の最後の節点 q−1q-1 は左の子である。その右の兄弟は範囲外なので、qq を1減らし、R←tree[q]⊗RR\leftarrow\mathrm{tree}[q]\otimes R とする。
  3. 両境界が偶数になり、残った節点は兄弟の対ごとにまとまる。p,qp,q をそれぞれ2で割って親の段へ進む。

終了したら L⊗RL\otimes R が答えである。上の列から [1,7)[1,7)、すなわち bcdefg を取得する経過を追おう。表の境界添字は各反復の開始時、累積 L,RL,R はその段で取り込んだ後の値である。追加区間は左側、右側の順に示す。

境界 (p,q)(p,q)追加区間(左/右)LLRR
(9,15)(9,15)[1,2)[1,2) / [6,7)[6,7)bg
(5,7)(5,7)[2,4)[2,4) / [4,6)[4,6)bcdefg

1段目では端を取り込んだ後の境界が (10,14)(10,14) なので、親の段では (5,7)(5,7) となる。2段目では (6,6)(6,6) となり、2で割った (3,3)(3,3) で終了する。最後に bcd と efg を結合して bcdefg を得る。

左側では元の列の左から右へ区間を見つけるため、LL の後ろへ足す。一方、右側では g の後に、その左隣の ef を見つけるため、RR の前へ足す。ここを逆にして g の後ろに ef を足すと、答えが bcdgef になる。和や最小値だけで試すと、この誤りに気づきにくい。

各反復で、元の問い合わせ区間は「LL に取り込んだ左部分・未処理の中央部分・RR に取り込んだ右部分」に、この順で分かれている。端の節点を取り込んでも重複や隙間はできず、中央部分を兄弟ごとに親へ移しても覆う範囲は変わらない。終了時には中央部分が空なので、選んだ節点区間は問い合わせ区間と一致し、L⊗RL\otimes R は結合則により元の列を順に畳み込んだ結果と一致する。

成立条件と計算量

各段で選ぶ節点は左右高々一つずつで、木の高さは ⌈log⁡2N⌉\lceil\log_2 N\rceil。したがって、一点更新と区間取得で行う結合は O(log⁡(N+1))O(\log(N+1)) 回である。葉の要約を用意した後、構築では P−1P-1 個の内部節点を計算する。N≤P<2NN\leq P<2N なので結合は O(N)O(N) 回となる。

一つの要約の大きさを ss、一回の結合に必要な時間の上限を TT とする。要約のコピーなどの費用も含めれば、構築は O(NT)O(NT)、一点更新・区間取得は各 O(Tlog⁡(N+1))O(T\log(N+1))、空間は O(Ns)O(Ns) である。葉の要約を作る費用は別に加える。s,Ts,T が定数なら、通常の構築 O(N)O(N)、各操作 O(log⁡N)O(\log N)(N≥2N\geq2)になる。上の文字列模型を実際の文字列コピーで実装すると、長い区間ほど要約も結合費用も増えるので、この定数の仮定は使えない。

空区間 [l,l)[l,l) では最初から p=qp=q で、何も取り込まず e⊗e=ee\otimes e=e を返す。N=1N=1 では P=1P=1 で内部節点はなく、全区間の取得も一点更新も定数回の処理で済む。非2冪長でもpaddingは単位元とし、問い合わせの右端は NN 以下に保つ。こうすれば、存在しない要素をデータとして扱わずに同じ手順を使える。

要約の設計と、ほかの区間分解への接続

ABC223 Fでは、文字列そのものの代わりに「括弧を数値化した区間の総和と、空の接頭辞を含む最小接頭辞和」を要約として持つ。公式問題の文字交換と部分括弧列の判定に対し、個別公式解説はこの二つの値を定数時間で結合し、二点の更新と区間取得で処理している(2026-10-24再照合)。必要な情報をどう選ぶかは区間monoid要約、括弧列の判定と結合式は問題本文へ進んで確認しよう。

同じ「区間を分ける」という見方でも、追加で使える性質や操作によって手法が変わる。

  • Sparse Tableは更新のない列で、さらに x⊗x=xx\otimes x=x という冪等性があるとき、重なりを許した二つの区間から答える。文字列連結や和は重複が答えを変えるので、この取得方法を使えない。
  • SWAGは末尾への追加と先頭からの削除で動く窓を、二つのstackに分けて集約する。結合則と単位元があればよく、逆元は不要だが、任意位置の更新や削除を扱う手法ではない。
  • 有限関数・作用の合成は、小さな状態集合上の操作を遷移表で要約する。先の操作を後の操作へ通す順序で結合を定義すれば、ここで学んだ区間取得に載せられる。一回の結合費用には、表の大きさを数える。
  • Segment Treeのcanonical区間分解では、ここで選んだような節点区間を使い、区間に対する制約などの対象物を節点へ配置する。ある一点に関わる対象物は、その葉から根までの経路上で取得できる。節点が持つ列の要約を結合する用途と、区間に関わる対象物を配置・取得する用途は区別する。後者の対象物にmonoid演算が必要とは限らない。

復習では、結合則・単位元を確かめた上で、分解した区間が元の列を過不足なく覆い、結合する順序も元どおりかを確認する。非可換な小例を一度手で追うと、左右の累積の向きを自分で再構成できる。

下位単元

問題一覧

この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

導入対象の目安: 水色(1200–1599)。結合則・単位元・順序を区間集約の共通言語として使う入口。

対象色の読み方は本書の読み方を参照してください。

概念上の親: データ構造と問い合わせ。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-monoid-segment-tree

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: なし。

このUnitを直接前提とする単元: なし。

このUnitでは扱わないもの

  • Fenwick Treeで保つ重み付き接頭辞統計。

根拠