让我重新解释一下这个O(n log n)算法。
将输入序列的元素解释为2D中的点，其中x坐标是索引，y坐标是值。我们正在寻找包含最多输入点的矩形，但要求左下角和右上角为输入点。在通常的分量偏序下，最佳矩形的左下角是最小的，右上角是最大的。
进行两个线性扫描以查找最小和最大点。创建一个整数值段树，以前者为键，具有接受键区间并增加/减少相关值的操作以及计算最大值的操作。该算法是通过从左到右迭代最大点，并使用段树跟踪位于每个最小点和当前最大点之间（相对于偏序）的输入点数来实现的。
随着我们从左向右移动，最小点和最大点都会下降。假设我们正在从一个最大点 (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 |
| +----+
| | |
我们逐个检查可能受影响的点，并更新线段树。点按x排序；如果我们在初始化过程中复制并按y排序，则可以有效地枚举可能受影响的点。请注意，随着时间的推移，x区间成对不相交，y区间也是如此，因此我们可以花费对数时间处理每个可能受影响的点。给定一个点(x'', y'')，使得x''∈]x,x']（注意，在这种情况下，y'' ≤ y'），我们需要在x坐标在]inf，x'']以及y坐标在]inf，y'']范围内的最小点处增加线段树。这看起来不是一维的，但实际上最小点的x坐标排序和y坐标排序是相反的，因此这组键是一个区间。同样，给定一个点(x''', y''')，使得y'''∈]y',y]（注意，在这种情况下，x''' ≤ x），我们需要减少一个键的值的区间。
以下是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());
}
}
