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

Question

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

Answer 1

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

回想一下，Kadane 的算法维护两个量:max(又名 max_so_far)，最大子数组和，以及 max_right(又名 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;
}

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