Чому правильний алгоритм не проходить за часом

Першим бажанням в олімпіадній задачі часто стає звичайний перебір.

Потрібно знайти пару елементів — переберу всі пари. Потрібно перевірити відрізки масиву — перевірю кожен відрізок. На прикладах з умови все працює, відповідь правильна, можна відправляти.

А потім тести повідомляють, що чекати до завтра вони не збираються 😅

Наприклад, у масиві 200 000 елементів подвійний цикл може виконати близько 40 мільярдів операцій:

200 000 × 200 000 = 40 000 000 000

Логічно код може бути бездоганним. Але за відведену секунду він просто не встигне отримати результат.

Рішення зі складністю O(n log n) для того самого обсягу даних потребуватиме приблизно 3,6 мільйона кроків:

200 000 × log₂(200 000) ≈ 3 600 000

Відповідь та сама, але різниця у швидкості — у тисячі разів.

Те саме стосується пам’яті. Можна створити таблицю для всіх можливих пар і навіть правильно її заповнити. Але якщо вона не поміститься в доступну пам’ять, правильність уже нікого не врятує.

Тому обмеження в умові — це частина задачі. Вони підказують, чи можна використовувати перебір, чи доведеться шукати інший підхід.

Поступово звикаю перед написанням коду ставити додаткові запитання:

• скільки буде даних;
• які операції повторюються;
• що доводиться рахувати знову;
• чи можна один раз зберегти частину результату;
• чи існує структура даних саме для таких операцій.

Одне з таких запитань і привело мене до дерева Фенвіка.