У нас есть задача, о том как быстро считать суммы на отрезке l...r в статичном массиве a за асимптотику меньшую, чем O(n).
Разделим массив a на k блоков одинакового размера и предварительно посчитаем для каждого из них сумму элементов.
Теперь, отвечая на запрос, можно пройтись по элементам массива a и прибавить их к результату, также если один из блоков лежит внутри отрезка, то мы можем прибавить его сумму к результату и пропустить элементы этого блока.
Максимальное количество операций на запрос при таком алгоритме равно n / k + k, следовательно оптимальное k равно квадратному корню из n.