Как реализовать многократный вывод суммы на промежутке массива и какая будет сложность

Что проверяют

Узнаёте ли вы задачу на префиксные суммы и можете ли обосновать сложность, а не просто назвать её. Главный уточняющий вопрос звучит так: а если между запросами элементы массива меняются? Тут ждут дерево Фенвика или дерево отрезков.

Как отвечать

Начните с наивного варианта: на каждый запрос пройти отрезок циклом. Это O(n) на запрос и O(n·q) в сумме, и при n и q порядка 10^5 получается 10^10 операций, что не укладывается ни в какой лимит.

Префиксные суммы решают это одним проходом. Заводите prefix := make([]int64, len(a)+1), где prefix[i+1] = prefix[i] + a[i], и тогда сумма на полуинтервале [l, r) равна prefix[r] - prefix[l].

• сложность: подготовка O(n), каждый запрос O(1), итого O(n + q) при дополнительной памяти O(n);
• полуинтервалы: они совпадают с семантикой срезов Go a[l:r], а лишний нулевой элемент в начале избавляет от проверки l == 0;
• тип суммы: int в Go на 64-битных платформах занимает 64 бита, но явный int64 снимает вопрос переносимости. Сумма 10^5 чисел до 10^9 в int32 переполняется молча, без паники.

Если массив меняется, префиксы пересчитывать дорого, O(n) на каждое обновление. Дерево Фенвика даёт O(log n) и на обновление, и на запрос, в нём два коротких цикла: i += i & -i при обновлении и i -= i & -i при запросе. Дерево отрезков тоже работает за логарифм, зато умеет минимум, максимум и отложенные операции на отрезке. Для матрицы та же идея превращается в двумерные префиксные суммы с формулой включения и исключения.

Когда запросов действительно много, узким местом становятся fmt.Scan и fmt.Println. Используйте bufio.NewReader и bufio.NewWriter и не забудьте Flush() в конце.

Где спотыкаются

Путают границы. Смешивают включительные и полуоткрытые интервалы, берут prefix[l-1] при l = 0 и получают панику index out of range.

Называют O(1) без оговорок. Честный ответ включает подготовку за O(n) и память, иначе интервьюер спросит, куда делась цена построения.

Предлагают префиксные суммы для изменяемого массива. При частых обновлениях решение деградирует до тех же O(n·q), что и наивный перебор.