Я пытаюсь понять ограничения функции комбинации диапазонов, которая может работать с разреженным столом. Из проведенного мною исследования функция комбинации диапазонов f (x, y) должна быть:
Ассоциативная, т. Е. F (a, f (b, c)) = f (f (a, b), c) для всех a, b, c
Идемпотент для выполнения запросов диапазона O (1).
Если свойство идемпотента не выполняется, вы все равно можете выполнять запросы диапазона, но в O (log (n)), а не в O (1), поэтому важно знать, является ли функция комбинации идемпотентной или нет .
Мне не удалось найти правильное определение того, как бинарная идемпотентная функция определяется для математических функций. Большинство примеров идемпотентных функций онлайн для тривиальных унарных математических функций, таких как f (x) = | x | или f (x) = 1 * x. Мне интересно узнать, как доказать / определить бинарные идемпотентные функции для немного более сложных математических функций, таких как:
- f (a, b) = a * b, не идемпотентный
- f (a, b) = min (a, b), идемпотент
- f (a, b) = (a * b) / b, идемпотент
для одинарных случай функции, можно просто применить функцию f (x) к выходу снова и снова и убедиться, что ответ остается прежним, например, f (f (f (x))) = x. Однако, когда у вас есть функция двоичная , это становится менее очевидным, поскольку есть два входа, но только один выход. Одним из возможных способов определения идемпотентности бинарной функции может быть проверка того, что f (a, b) = f (f (a, b), b) и f (a, b) = f (a, f (a, б)) для всех а, б, но я не уверен, что это правильный подход к проблеме или что она хорошо обобщает.
Любой совет приветствуется. Здесь - моя редкая реализация таблицы, если вам интересно.