arrays - 当应用相邻转置时，在次线性时间内更新数组中的最大和 subinteral

Question

我问了这个关于一般换位的问题，这似乎太难了，我只得到了一个似乎不能保证渐近加速的答案。因此，假设我们将一系列相邻转置应用于数值数组（相邻转置交换两个相邻数字），并且我们希望在每个相邻转置之后保持最大和子区间的解。我们可以在每个相邻的转置之后在整个阵列上从头开始重复 Kadane 的线性时间解。所以这就是我想要击败的。这可以在每个相邻转置的亚线性时间内完成吗，例如，如果我们对大小为 N 的数组进行 N 或 N^2 个相邻转置，并且只要摊销的预处理时间对于整个集合是亚线性的，我们就可以进行预处理应用转置？

Answer 1

此答案描述了 Kadane 的“双端”变体，可用作具有 O(log n) 时间更新的算法的基础。此变体对于并行化也很有用。

回想一下，Kadane 的算法维护两个量：max(aka max_so_far)，最大子数组和，和max_right(aka max_ending_here)，从右边界延伸的子数组的最大和。双端 Kadane 计算另外两个量：max_left，从左边界延伸的子数组的最大和，以及max_left_right，从左右边界延伸的子数组的最大和（即，数组的总和）。将此信息存储在以下结构中。

struct KadaneResult {
    int max;
    int max_right;
    int max_left;
    int max_left_right;
};

现在给定两个数组的结果结构，我们可以计算它们连接的结果结构。如果您了解 Kadane 并且我没有搞砸，那么正确性证明应该很容易:)

KadaneResult Combine(KadaneResult left, KadaneResult right) {
    KadaneResult both;
    both.max = maximum(left.max, right.max, left.max_right + right.max_left);
    both.max_right = maximum(right.max_right, left.max_right + right.max_left_right);
    both.max_left = maximum(left.max_left, left.max_left_right + right.max_left);
    both.max_left_right = left.max_left_right + right.max_left_right;
    return both;
}

为了完整起见，计算零和一元素的结果结构。

KadaneResult Zero() {
    KadaneResult zero;
    zero.max = 0;
    zero.max_right = 0;
    zero.max_left = 0;
    zero.max_left_right = 0;
    return zero;
}

KadaneResult One(int x) {
    KadaneResult one;
    one.max = maximum(0, x);
    one.max_right = maximum(0, x);
    one.max_left = maximum(0, x);
    one.max_left_right = x;
    return x;
}

现在，将所有这些结果结构放在一个段树中。每当您更新叶子中的一个值时，重新计算其祖先的结果结构并读取max根处的字段。作为一种实际的优化，如果您检测到其中一个重新计算没有效果，您可以跳过后续的更新。