在次线性时间阵列更新最大总和subinteral当施加相邻换位 [英] Updating maximum sum subinteral in an array in sublinear time when an adjacent transposition is applied

问题描述

我寻求一些换位这个问题，似乎太难了，我只得到了一个答案这似乎不给保证渐近加速。因此，假设我们采用相邻换位的序列数字阵列（相邻换位交换两个相邻的号码），我们希望保持最高金额子区间的每个相邻换位后的溶液。每两个相邻的换位后，我们可以重复从头Kadane的线性时间解决整个阵列上。所以这是我想击败的。可这每相邻换位次线性的时间内完成，说，如果我们对大小为N的数组做N或N ^ 2个相邻换位，我们被允许做preprocessing只要摊销preprocessing时间次线性的整套应用换位的？

I asked this question for general transpositions and it seemed too hard, I only got one answer which didn't seem to give a guaranteed asymptotic speed-up. So suppose we apply a sequence of adjacent transpositions to a numeric array (an adjacent transposition swaps two adjacent numbers) and we want to maintain the solution of the maximum sum subinterval after each adjacent transposition. We could repeat Kadane's linear time solution from scratch on the entire array after every adjacent transposition. So that is what I want to beat. Can this be done in sublinear time per adjacent transposition, say if we do N or N^2 adjacent transpositions for an array of size N, and we are allowed to do preprocessing as long as the amortized preprocessing time is sublinear for the entire set of applied transpositions?

推荐答案

这答案介绍Kadane的，可以用来作为基础的算法有O（log n）的 - 时间更新了双头变体。这种变体是很有用的也是并行。

This answer describes a "double-ended" variant of Kadane that can be used as the basis for an algorithm with O(log n)-time updates. This variant is useful also for parallelization.

回想Kadane的算法维护两个量：最大（又名 max_so_far ），最大子阵之和 max_right （又名 max_ending_here ），从右边界扩展子数组的最大总和。双头Kadane计算两个量： max_left ，从左边的边界扩展子数组的最大总和，而 max_left_right 中，从左侧和右侧边界延伸的子阵列的最大总和（即，阵列的总和）。存储在以下结构信息。

Recall that Kadane's algorithm maintains two quantities: max (a.k.a. max_so_far), the maximum subarray sum, and max_right (a.k.a. max_ending_here), the maximum sum of a subarray that extends from the right boundary. Double-ended Kadane computes two more quantities: max_left, the maximum sum of a subarray that extends from the left boundary, and max_left_right, the maximum sum of a subarray that extends from the left and right boundaries (i.e., the sum of the array). Store this information in the following structure.

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

现在定的结果结构两个数组，我们可以计算其拼接结果结构。如果你了解Kadane的正确性证明应该很容易，我还没有搞砸了：）

Now given result structures for two arrays, we can compute a result structure for their concatenation. The correctness proof should be easy if you understand Kadane and I haven't screwed up :)

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;
}

有关完整性，为计算零和一元素的结果结构。

For completeness, compute a result structure for zero and one elements.

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;
}

现在，把所有这些结果的结构在段树。每当您更新值之一的叶，重新计算的结果为结构的祖先，并在根读出的最大字段。作为一个实际的优化，如果检测到recomputations的一个都没有效果，你可以跳过后续的该更新。

Now, put all of these result structures in a segment tree. Whenever you update one of the values at a leaf, recompute the result structures for its ancestors and read off the max field at the root. As a practical optimization, if you detect that one of the recomputations had no effect, you can skip the subsequent ones for that update.

这篇关于在次线性时间阵列更新最大总和subinteral当施加相邻换位的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！