Range Maximum-Sum Segment Query Problem
楽しみのために論文を読むことは面白い!
参照: Chen, K.Y., Chao, K.M.: "On the Range Maximum-Sum Segment Query Problem"
問題
the Range Maximum-Sum Segment Query Problem (RMSQ)
入力: 空でないnつの実数の列A = [a_1,a_2,...,a_n]。
クエリ: 2つの区間[i, j]と[k, l] (1≦i≦j≦n, 1≦k≦l≦n, i≦l)が入力される。全てのインデックスの組(x, y) (i≦x≦j, k≦y≦l) に対してS(x,y)が最大であるものを返す。答えをRMSQ(i,j,k,l)と呼ぶ。
ここで、S(x,y)は配列Aの部分和。
この問題が前処理O(n),クエリO(1)で解けることを示した論文である。
まず、特殊な場合を考える:
A Special Case of the RMSQ problem (SRMSQ)
入力: 空でないnつの実数の列A = [a_1,a_2,...,a_n]。
クエリ: 区間[i, j](1≦i≦j≦n)が入力される。全てのインデックスの組(x, y) (i≦x≦y≦j) に対してS(x, y)が最大であるものを返す。答えをSRMSQ(i, j)と呼ぶ。
ここで、A(x,y)は配列Aの部分列。
SRMSQ(i,j)をA(i,j)の"maximum-sum segment"と呼び、SRMSQ(1,n)をAのmaximum-sum segmentと呼ぶ。
SRMSQ(i,j) = RMSQ(i,j,i,j)であることは明らかである。
SRMSQを解くアルゴリズム
基本的な戦略として、配列Aの累積和c[・]を考える。c[0] = 0、c[i+1] = c[i] + A[i+1]と定義する。ここで、部分和A(l,r)はc[r]-c[l-1]と表されることに注意すると、c[r]を大きくしてc[l-1]を小さくするのが直感的に良さそうにみえる。
しかしこれを直接、たとえば「t[i] = l∈[1..i]でc[l-1]が最小のもの」として前処理してしまうと、クエリでt[i..j]のRMQで区間[t[r],r]を求めたとしてもt[r]<iの場合にどうしようもない。
そこで"good partner"p[・]というものを考える(定義は省く)。各jに対してp[j]を求め、m[j] = S(1, p[j])という累積和のものをRangeMaximumQueryで前処理しておく。
Lemma 4. インデックスが全てのに対してを満たすならば、はのmaximum-sum segmentとなる。
上記の定理はgood partnerが確かにgoodなpartnerであるということを示している。
Lemma 5. が上のインデックスのgood partnerであってp[j]<jとするならば、全てのに対して。
アルゴリズムではまずm[i..j]中の最大値の位置を求め、rとする。i≦p[r]の場合はLemma 4によりそれ[p[r],r]が答えである。
問題はp[r]<iのときどうするか。しかしgood partnerにはうまい入れ子構造が存在して:
Lemma 6. 全てのインデックスに対して、ということありえない。
この補題により、もしrを求めてp[r]<iであったなら、[i,r]と[r+1,j]に区間を分割することができる。なぜなら、もしその2つの分割された区間を横断するようなものが存在したならば、それはあるuに対して[p[u],u]であって、それと[p[r],r]が交差してしまってLemma 6に反するからである。(ここ微妙にわかってない)
[i,r]の部分。c[i-1..r-1]中の最小値の位置を求め、r1とする。[r1,r]が候補となる。右端をrに固定したならば左端のc[r1-1]を最小化したものが答えとなるのは基本的な戦略として書いた通りである。なぜr以外の右端を考えなくて良いかというと、Lemma 5によりc[r]以上のc[k]は存在しないからである。
[r+1,j]の部分。さらにm[r+1..j]中の最大値の位置を求め、r2とする。ここで、Lemma 6によりr[r2]はr以下にならず、よってi以下にもならないためr[r2]を確実に左端とすることができ、Lemma 4により[r[r2],r2]を答えとすることができる。
分割した区間の両方(r==jの場合は後者は存在しない)を解き、そのうち最大値を取るものが答えとなる。
RMSQを解くアルゴリズム
さて、実際にはSRMSQが解けたならば、RMSQはそれに少しコードを足すだけで解けてしまう。最初に、一般性を失わずにi≦kかつj≦lと仮定しておく。
まずj≦kの場合は簡単である。基本的な戦略は分離した(点で接していてもいい)2つの区間のSRMSQに対しては完全によく働く。つまり、(RMQ_min(c, i − 1, j − 1) + 1, RMQ_max(c, k, l))を出力する。
次にk<jの場合。アイデアはこれもまた区間(ペア)の分割である。3つの区間ペアに分割できる。
- ([k,j], [k,j])。つまり2つの区間の共通部分である。SRMSQを子呼び出しすればいい。
- ([i,k], [k,l])。分離しているので基本的な戦略通りでいい。
- ([k,j], [j, l])。これも分離しているので基本的な戦略を用いる。
上記の3つのもののうち最大値をとるものが答えとなる。なぜこの3つだけでよいかは絵を描けばわかる。どうやってもその3通り以外の正当な区間を取れないことがわかるだろう。
RMQは前処理O(n),クエリO(1)で解けるので、この問題も漸近的に最適に解ける。
実装
0-originにしている。一応ランダムテストされている。RMQは別途必要。