Почему это работает
- prefix[j] — сумма первых j чисел. Числа с left по right — это первые right + 1 чисел без первых left, поэтому их сумма равна prefix[right + 1] − prefix[left].
- Лишняя ячейка prefix[0] = 0 — сумма пустого начала: запрос с индекса 0 вычитает её, и особый случай не нужен.
- Массив не меняется, поэтому таблица, построенная один раз, верна для всех запросов, а каждый запрос — два обращения, какой бы длинный ни был отрезок.
Сложность
init: время O(n) и память O(n) на n + 1 сумму. Каждый sumRange: время O(1), два обращения и вычитание.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗