この O(n log n) アルゴリズムの説明をやり直します。
入力シーケンスの要素を 2D の点として解釈します。x 座標はインデックス、y 座標は値です。左下隅と右上隅が入力ポイントであるという制約に従って、最も多くの入力ポイントを含む四角形を探しています。通常のコンポーネント単位の半順序では、最適な四角形の左下隅が最小で、右上隅が最大です。
最小点と最大点を見つけるために 2 つの線形スイープを行います。前者によってキー付けされた整数値のセグメント ツリーを作成し、(i) キーの間隔を受け入れ、関連する値をインクリメント/デクリメントし、(ii) 最大値を計算する操作を行います。このアルゴリズムは、セグメント ツリーを使用して、各極小点と現在の極大点の間に (半順序に関して) 入力点がいくつあるかを追跡しながら、極大点を左から右に反復します。
左から右に移動するにつれて、最小ポイントと最大ポイントの両方が減少します。次に、極大点 (x, y) から次の極大点 (x', y') に移動するとします。x < x' および y' < y です。セグメント ツリーの値はどのように変化しますか? x < x' であるため、]x, x'] の x 座標を持つ点は、右上 (x, y) の長方形には属しませんが、右上 (x', y') の長方形に属する可能性があります。逆に、y' < y であるため、y 座標が ]y', y] の点は、右上 (x, y) の四角形に属する可能性がありますが、右上 (x', y') の四角形には属しません。他のすべてのポイントは影響を受けません。
----+ empty
|
----+---------+ (x, y)
removed |
--------------+-------+ (x', y')
| added |
| +----+
| | |
影響を受ける可能性のあるポイントを 1 つずつ調べて、セグメント ツリーを更新します。ポイントは x でソートされます。初期化中にコピーを作成して y でソートすると、影響を受ける可能性のあるポイントを効率的に列挙できます。時間の経過とともに、x 間隔は y 間隔と同様に対ごとに互いに素になることに注意してください。そのため、影響を受ける可能性のある各ポイントに対数時間を費やす余裕があります。x'' in ]x, x'] (この場合、y'' <= y' であることに注意してください) のような点 (x'', y'') が与えられると、最小点でセグメント ツリーをインクリメントする必要があります。その x 座標は ]inf, x''] にあり、y 座標は ]inf, y''] にあります。これは 1 次元に見えないかもしれませんが、実際には x 座標での順序と y 座標での順序が極小点に対して反対であるため、このキーのセットは間隔です。
Java の「魔法の」セグメント ツリー データ構造を次に示します。
public class SegmentTree {
private int n;
private int m;
private int[] deltaValue;
private int[] deltaMax;
private static int nextHighestPowerOfTwoMinusOne(int n) {
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return n;
}
public SegmentTree(int n) {
this.n = n;
m = nextHighestPowerOfTwoMinusOne(n) + 1;
deltaValue = new int[m];
deltaMax = new int[m];
}
private static int parent(int i) {
int lob = i & -i;
return (i | (lob << 1)) - lob;
}
private static int leftChild(int i) {
int lob = i & -i;
return i - (lob >>> 1);
}
private static int rightChild(int i) {
int lob = i & -i;
return i + (lob >>> 1);
}
public int get(int i) {
if (i < 0 || i > n) {
throw new IllegalArgumentException();
}
if (i == 0) {
return 0;
}
int sum = 0;
do {
sum += deltaValue[i];
i = parent(i);
} while (i < m);
return sum;
}
private int root() {
return m >>> 1;
}
private int getMax(int i) {
return deltaMax[i] + deltaValue[i];
}
public void addToSuffix(int i, int delta) {
if (i < 1 || i > n + 1) {
throw new IllegalArgumentException();
}
if (i == n + 1) {
return;
}
int j = root();
outer:
while (true) {
while (j < i) {
int k = rightChild(j);
if (k == j) {
break outer;
}
j = k;
}
deltaValue[j] += delta;
do {
int k = leftChild(j);
if (k == j) {
break outer;
}
j = k;
} while (j >= i);
deltaValue[j] -= delta;
}
while (true) {
j = parent(j);
if (j >= m) {
break;
}
deltaMax[j] =
Math.max(0,
Math.max(getMax(leftChild(j)),
getMax(rightChild(j))));
}
}
public int maximum() {
return getMax(root());
}
}