Вычисление всех инфиксных продуктов для моноида / полугруппы

Question

Введение: продукты Infix для группы

Предположим, у меня есть группа

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?

Answer 1

Да, если G - это [[0, 1] ⊂ ℝ, *), то эту идею можно спасти, что позволит вычислять продукты в диапазоне времени за O(log n) (или, точнее, O(log z), где z число a в A с x(a) = 0).

Для каждого i вычислите произведение m(i) = x(0)*x(1)*...*x(i), игнорируя любые нули (поэтому эти продукты всегда будут отличны от нуля). Кроме того, создайте отсортированный массив Z индексов для всех нулевых элементов.

Тогда произведение элементов от i к j равно 0, если в диапазоне [i, j] есть ноль, а в противном случае m(j) / m(i-1).

Чтобы определить, есть ли ноль в диапазоне [i, j], можно выполнить двоичный поиск в Z для наименьшего значения>= i в Z и сравнить его с j. Вот где появляются дополнительные затраты времени O(log n).

Общий моноидный раствор

В случае, когда G является любым моноидом, можно выполнить предварительное вычисление n продуктов, чтобы сделать произведение произвольного диапазона вычислимым за время O(log(ji)), хотя это немного сложнее, чем в более конкретном случае выше.

Вместо того, чтобы предварительно вычислять префиксные продукты, вычислите m(i, j) для всех i, j, где j-i+1 = 2^k для некоторого k>=0, а 2 ^ k делит и i, и j. Фактически, для k=0 нам не нужно ничего вычислять, так как значения m(i, i+1) - это просто x(i).

Таким образом, нам нужно вычислить n/2 + n/4 + n/8 + ... всего произведений, что составляет не более n-1 единиц.

Можно построить произвольный интервал [i, j] из точки O(log_2(j-i+1)) из этих строительных блоков (и элементов исходного массива): выбрать самый большой строительный блок, содержащийся в интервале, и добавить уменьшающийся размер блоки по обе стороны от него, пока вы не доберетесь до [i, j]. Затем умножьте предварительно вычисленные произведения m(x, y) для каждого из строительных блоков.

Например, предположим, что ваш массив имеет размер 10. Например, я предположу, что моноид - это сложение натуральных чисел.

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.