Всем добрый вечер. Вопрос касается алгоритмов.
Есть последовательность чисел, например:
4 8 1 9
Нужно быстро (быстрее, чем за n) вычислять сумму чисел, расположенных левее i-го числа, причем только тех, которые строго меньше его. Например, для 9 эта сумма равна 13, а для 1 в моем примере — 0. Как это можно сделать? Долго думал, но ничего особенно не пришло в голову... Задача связана с деревом отрезков, но как его здесь применить я не знаю.