Несложная задача на структуры данных, но с некоторыми подводными камнями, которые могут помочь избегать ошибок в будущем. Читаем условие: Уже из приведённого примера следует, что надо складывать два самых маленьких числа. Это же следует и из логики: если большое число участвует в нескольких операциях сложения, то в каждой из них за это число надо будет заплатить. То есть надо стараться чаще использовать маленькие числа (ведь количество операций сложения всегда будет равно N - 1). Отсюда получаем,...

Задача на структуры данных, которую можно решить каким-нибудь из деревьев или sqrt-декомпозицией. Я же хочу показать ещё один вариант sqrt-декомпозиции (как метода, а не структуры данных). Давайте читать условие: Простое решение заключается в том, чтобы каждый раз перестраивать индекс. Такое точно не пройдёт по времени. Идея sqrt-декомпозиции заключается в том, чтобы перестраивать индекс лишь каждые N шагов. А между перестройками хранить историю изменений и получать ответ, просматривая и индекс, и накопленную историю...