Рассмотрим эту таблицу, в которой хранятся значения двух переменных stock A и B в каждый момент времени:
A B
day 1 10 0
day 2 0 10
day 3 7 7
day 4 7 7
Мы хотим ответить на такие вопросы, как:
Какое максимальное значение было достигнуто переменной A в заданном диапазоне дней?
Каково максимальное значение, полученное с помощью суммы переменных A и B в заданном диапазоне дней?
Однако реальная таблица может содержать миллиарды строк и множество переменных. Чтобы быстрее получать ответы, мы планируем предварительно вычислить сводную таблицу с меньшей степенью детализации по времени.
Проблема в том, что наивного вычисления максимума по новой временной гранулярности для A и B по отдельности недостаточно для ответа на второй вопрос. Например:
Max-A Max-B
day 1&2 10 10
day 3&4 7 7
Мы упустили тот факт, что максимум A + B достигается за дни 3 и 4.
Мы можем добавить новый столбец Max-(A+B) в сводную таблицу. Но если будет много разных переменных, мы столкнемся с комбинаторным взрывом. Сводная таблица может оказаться больше исходной!
Существует ли алгоритм/структура данных для эффективного хранения таких предварительно вычисленных максимумов таким образом, чтобы мы могли задавать вопросы о произвольных комбинациях переменных, избегая при этом комбинаторного взрыва? Я предполагаю, что он мог предположить некоторые закономерности в данных и попытаться использовать их — за счет некоторой общности.
