Челлендж) Есть некая ассоциативная бинарная функция f. Нам дан неменяющийся массив. Мы хотим уметь считать f на произвольном отрезке массива. Для этого можно предподсчитать f на некоторых отрезках и потом разбивать произвольный [L..R] на O(1) уже посчитанных отрезков. Челлендж: сколько отрезков предподсчитать? n^2 очевидно, nlogn несложно. Кто лучше?
UPD: Макс сразу сильно повысил градус,
теперь интересно только O(n α) и O(n).
UPD: Макс сразу сильно повысил градус,
теперь интересно только O(n α) и O(n).
Челлендж) Есть некая ассоциативная бинарная функция f. Нам дан неменяющийся массив. Мы хотим уметь считать f на произвольном отрезке массива. Для этого можно предподсчитать f на некоторых отрезках и потом разбивать произвольный [L..R] на O(1) уже посчитанных отрезков. Челлендж: сколько отрезков предподсчитать? n^2 очевидно, nlogn несложно. Кто лучше?
UPD: Макс сразу сильно повысил градус,
теперь интересно только O(n α) и O(n).
UPD: Макс сразу сильно повысил градус,
теперь интересно только O(n α) и O(n).
У записи 5 лайков,
1 репостов.
1 репостов.
Эту запись оставил(а) на своей стене Sergey Kopeliovich
