0

简介：一组中缀产品

假设我有一个小组

G = (G, *)

和元素列表

A = {0, 1, ..., n} ⊂ ℕ
x : A -> G

如果我们的目标是实现一个功能

f : A × A -> G

这样

f(i, j) = x(i) * x(i+1) * ... * x(j)

（我们不关心如果i>会发生什么j）

然后我们可以通过预先计算一个前缀表来做到这一点 

m(-1) = 1
m(i) = m(i-1) * x(i)

（1右侧表示 的单位G），然后实现f为

f(i, j) = m(i-1)⁻¹ * m(j)

这有效，因为

m(i-1) = x(0) * x(1) * ... * x(i-1)
m(j) = x(0) * x(1) * ... * x(i-1) * x(i) * x(i+1) * ... * x(j)

所以

m(i)⁻¹ * m(j) = x(i) * x(i+1) * ... * x(j)

经过充分的重新关联。

我的问题

如果 G 只是一个幺半群，而不是一个群，我们能否挽救这个想法，或者做一些不那么糟糕的事情？

对于我的特殊问题，如果我们可以做类似G = ([0, 1] ⊂ ℝ, *)的事情，即我们有来自单位行的实数，我们不能除以0？

4

1 回答 1

2

是的，如果 G 是 ([0, 1] ⊂ ℝ, *)，那么这个想法可以被挽救，从而可以在 O(log n) 时间（或更准确地说，O(log z) 其中 z是 A 中 x(a) = 0) 中 a 的数量。

对于每个 i，计算乘积 m(i) = x(0)*x(1)*...*x(i)，忽略任何零（因此这些乘积总是非零）。此外，为所有零元素构建索引的排序数组 Z。

如果在 [i, j] 范围内有零，则从 i 到 j 的元素的乘积为 0，否则为 m(j) / m(i-1)。

要查找范围 [i, j] 中是否有零，可以在 Z 中对 Z 中的最小值 >= i 进行二分搜索，并将其与 j 进行比较。这就是额外的 O(log n) 时间成本出现的地方。

一般幺半群解决方案

在 G 是任何幺半群的情况下，可以对 n 乘积进行预计算，以使任意范围乘积在 O(log(ji)) 时间内可计算，尽管它比上面更具体的情况有点复杂。

不是预先计算前缀乘积，而是计算所有 i, j 的 m(i, j)，其中对于某些 k>=0，j-i+1 = 2^k，并且 2^k 除 i 和 j。事实上，对于 k=0，我们不需要计算任何东西，因为 m(i, i+1) 的值只是 x(i)。

所以我们需要计算 n/2 + n/4 + n/8 + ... 总产品，最多是 n-1 个东西。

可以从这些构建块（和原始数组的元素）的 O(log_2(j-i+1)) 处构造任意间隔 [i, j]：选择包含在间隔中的最大构建块并附加减小的大小在它的任一侧阻塞，直到您到达 [i, j]。然后将每个构建块的预计算乘积 m(x, y) 相乘。

例如，假设您的数组大小为 10。例如，我假设 monoid 是自然数的加法。

i: 0  1  2  3  4  5  6  7  8  9
x: 1  3  2  4  2  3  0  8  2  1

2: ----  ----  ----  ----  ----
   4     6     5     8     3

4: ----------- ----------
   10          13

8: ----------------------
   23

在这里，第 2、4 和 8 行显示长度为 2、4、8 的对齐间隔的总和（如果数组的长度不是 2 的幂，则忽略剩余的位）。

现在，假设我们要计算 x(1) + x(2) + x(3) + ... + x(8)。

即 x(1) + m(2, 3) + m(4, 7) + x(8) = 3 + 6 + 13 + 2 = 24。

于 2016-04-11T08:19:10.340 回答