得到左半积和右半积的绝对差最小的元素

Question

我想找到给定数组中的元素（n个元素），这样左半积和右半积之间的绝对差最小

(abs(arr[0]*arr[1]*...arr[x]-arr[x+1]*arr[x+2]...arr[n]))

这个问题还会定期更新数组的值“m”次。我想得到O（m log n）中所有查询的答案。在

我尝试过一种方法，它需要O（n*m）时间，但由于TLE错误而无法工作。在

Answer 1

我想到的唯一方法是：

这么大的数的乘法很难。在

我们可以把这个藏起来

log10(A[1]A[2]...*A[x])- log10(A[x+1]A[x+2]..*A[n])
log10(A[1])+log10(A[2])+..+log10(A[x])-log10(A[x+1])+log10(A[x+2])+..+log10(A[n])

现在这些结果可以存储在两倍。在

由于abs（（A[1]A[2]…*A[x]）—（A[x+1]A[x+2].*A[n]）应最小化， 这个方程将遵循三元搜索的规则。在

因此，在三元搜索的每一次迭代中，我们都需要

log(A[1])+log(A[2])+..+log(A[x])
and
log(A[x+1])+log(A[x+2])+..+log(A[n])

由于有一些更新，我们需要一个数据结构来查找它们的 像分段树一样复杂。在

因此，对于每个查询，总体复杂度将是log（n）*log（n）。在