A是一个最多包含10个5个整数的数组。
我们必须在log（N）复杂度（其中，N=A中的元素数量）中对该数组进行2种操作。
操作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次5次操作。
如果在log（N）中不可能，那么执行操作的最佳复杂度是多少？
由于您似乎必须访问范围[i, j]中的所有元素，因此复杂性取决于该范围的线性大小
有可能j-i的数量级为N，您必须更改它们中的每一个。正如Paul所说，这使得任何比O（N）更快的算法都是不可能的。K不是问题的参数，它只是一个变量，因此Bidhan的答案中的log（K）毫无意义。
现在，如果问题不是关于时间复杂度本身，而是关于大规模并行运算树的高度（例如，CUDA上的树），那么，给定足够的线程，由于所有运算的独立性，人们将平凡地在O（1）中执行运算1，在O（log（N））中通过乘以相邻元素的mod M对来执行运算2（需要100000/2个线程），然后是成对的相邻结果，等等，直到得到答案。
然而，这不是问题所在。除非进行大规模并行计算，否则无论如何执行，每个操作的复杂性都是O（N）。