我们得到 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,但我无法制定明确的解决方案。
最佳答案
我有一个使用 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)
内存,那么这应该可以正常工作。
关于algorithm - 计算函数求和的高效算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31537010/