algorithm - 范围内整数的乘法

Question

A 是一个最多包含 10 ^{5 个}整数的数组。

我们必须以 log(N) 复杂度对这个数组进行 2 种操作（其中，N= A中的元素数）。

操作 1，给定v，i，j我们必须将v添加到A[k] (i<=k<=j)。

操作 2，给定i & j计算( A[i] * A[i+1] * A[i+2] * .... * A[j] ) % M。（M 是一个素数，并且对于所有操作都是相同的）。

将进行近 10 ⁵次操作。

如果在 log(N) 中不可能，那么执行操作的最佳复杂度是多少？

Answer 1

由于看起来您必须访问范围内的所有元素[i, j]，因此复杂性取决于该范围的线性大小，

Answer 2

ji 可能在 N 的数量级上，您必须更改它们中的每一个。正如保罗所说，这使得任何比 O(N) 更快的算法都是不可能的。K 不是问题的参数，它只是一个变量，因此 Bidhan 的答案中的 log(K) 没有意义。

现在，如果问题不是关于时间复杂度的问题，而是关于大规模并行操作树的高度（例如你在 CUDA 上的），那么，如果有足够多的线程，那么在 O( 1) 由于所有操作的独立性，O(log(N)) 中的操作 2 乘以 mod M 对相邻元素（需要 100000/2 个线程），然后是相邻结果对等，直到得到答案。

然而，这不是问题所在。除非进行大规模并行计算，否则无论您如何执行，每个操作的复杂性都是 O(N)。