algorithm - 计算函数求和的高效算法

Question

我们得到 N 点，形式为 (x,y)，我们需要计算以下函数:

F(i,j) = ( | X[i] - X[j] | ) * ( | Y[i] - Y[j] | )

计算所有有序对 (i,j) 的 F(i,j) 的总和

N <= 300000

我正在寻找一个O(N log N) 的解决方案。

我最初的想法是按 X 对点进行排序，然后使用 BIT，但我无法制定明确的解决方案。

Answer 1

我有一个使用 O(N log(M)) 的解决方案时间和O(M)内存，其中 M是 Y 范围的大小.这与您的想法相似。

首先对点进行排序，使得 X坐标在增加。

让我们写A对于 (X[i] - X[j]) * (Y[i] - Y[j]) 的总和对于所有对 i > j这样 Y[i] > Y[j] , 和 B对于所有对的相同表达式的总和 i > j这样 Y[i] < Y[j] .

总和A + B可以在O(N)中轻松计算时间，最终答案可以从A - B算出.因此足以计算A .

现在创建一个二叉索引树，其节点由 [a, b) 形式的区间索引与 b = a + 2^k对于一些 k . (不是一个好句子，但你知道我的意思，对吧？)根节点应该覆盖区间[Y_min, Y_max]。 Y 的可能值.

对于由 [a, b) 索引的任何节点和任何 i , 让f(a, b, i)是以下多项式:

f(a, b, i)(X, Y) = sum of (X - X[j]) * (Y - Y[j]) for all j such that j < i and Y[j] < Y

它的形式是P * XY + Q * X + R * Y + S , 因此这样的多项式可以用四个数字 P, Q, R, S 来表示.

现在以 i = 0 开头, 你可以计算出 f(a, b, i)(X[i], Y[i]) .从i至 i + 1 ，你只需要更新那些间隔 [a, b)包含 Y[i] .当您到达 i = N , A 的值计算得出。

如果你负担得起O(M)内存，那么这应该可以正常工作。