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

Я попробую позже посмотреть, что там можно сделать.

x^2y^2+x^2z^2+y^2z^2-x^2yz-xy^2z-xyz^2>0
x^2y^2-x^2yz+x^2z^2-xyz^2+y^2z^2-xy^2z>0
x^2y(y-z) +z^2x(x-y)+y^2z(z-x) > 0
x^2y(y-z) +z^2x(x-y)+y^2z(z-y)+y^2z(y-x) > 0
допустим x>=y>=z
(x^2-yz)y(y-z) +(zx-yz)z(x-y) > 0

x^2 (y-z)^2 + (x-y) (x-z) yz >= 0 при x >= y >= z.