Range Sum Query
Тебе дан неизменяемый массив целых чисел nums и список queries. Каждый запрос — это пара [left, right] индексов, отсчитываемых от 0, и он запрашивает сумму nums[left] + nums[left+1] + ... + nums[right], включая оба конца. Верни ответы в том же порядке, что и запросы.
Функция
- numsinteger-array
- массив целых чисел, одинаковый для каждого запроса
- queriesinteger-2d-array
- диапазоны для сложения, каждый представляет собой пару [left, right], где left ≤ right
- Возвращаетinteger-array
- сумма для каждого диапазона, по одной на запрос, в порядке запросов
Ограничения
1 ≤ nums.length ≤ 104-104 ≤ nums[i] ≤ 1041 ≤ queries.length ≤ 15000 ≤ left ≤ right < nums.lengthдля каждого запроса[left, right]
Примеры
- Ввод
- nums = [3, -2, 5, 1, -4, 6]queries = [[0, 2], [1, 4], [3, 3]]
- Вывод
- [6, 0, 1]
- Пояснение
- Индексы от 0 до 2 содержат
3 + (-2) + 5 = 6. Индексы от 1 до 4 содержат-2 + 5 + 1 + (-4) = 0. Диапазон[3, 3]содержит единственное значение1.
- Ввод
- nums = [2, 7, 1, 8]queries = [[0, 3], [2, 3], [0, 0], [1, 2]]
- Вывод
- [18, 9, 2, 8]
- Пояснение
- Сумма всего массива равна
2 + 7 + 1 + 8 = 18, сумма двух последних значений —1 + 8 = 9, только индекс 0 —2, а индексы от 1 до 2 —7 + 1 = 8.
+14 скрытых тестов при отправке
Дополнительный вопрос
Теперь числа образуют сетку, и каждый запрос требует найти сумму в прямоугольнике, заданном двумя углами. Как расширить префиксные суммы, чтобы отвечать на каждый запрос за постоянное число операций?
Подсказки
Открывайте по одной. Каждая подсказывает чуть больше.
Многие запросы охватывают почти одни и те же значения. Какую работу можно выполнить один раз, прежде чем читать запросы?
Если бы ты знал сумму первых
iзначений для каждогоi, диапазон был бы разностью двух таких сумм.Создайте
prefixс помощьюprefix[0] = 0иprefix[i+1] = prefix[i] + nums[i]. Тогда каждый запрос[left, right]— этоprefix[right+1] - prefix[left].
Решение
Один диапазон — это цикл. Проблема в их количестве: каждый запрос может охватывать большую часть массива, поэтому отдельное суммирование каждого диапазона снова и снова повторяет одни и те же сложения. Один раз сложи всё в префиксные суммы, и каждый диапазон сведётся к одному вычитанию.
Сложите значения каждого диапазона
Верно, но не успевает на самых больших тестах
Идея
Обрабатывайте каждый запрос отдельно: задайте начальную сумму равной 0, прибавьте значения от nums[left] до nums[right] и сохраните результат. Для [1, 4] в [3, -2, 5, 1, -4, 6] это -2 + 5 + 1 + (-4) = 0.
Это корректно и для одного запроса — лучше сделать нельзя: нужно один раз прочитать каждое значение в диапазоне. Проблема в повторении. Запрос может охватывать до n значений, поэтому обработка q запросов требует до n × q сложений. При n = 10^4 и 1500 запросах, каждый из которых охватывает большую часть массива, это около 1.3 × 10^7 сложений, почти все из которых повторяют работу, выполненную для более раннего запроса.
Помимо списка ответов, алгоритм хранит одну сумму, поэтому дополнительное пространство составляет O(1).
Алгоритм
- Создай пустой список ответов.
- Для каждого запроса
[left, right]установиtotal = 0. - Прибавь
nums[i]кtotalдля каждогоiотleftдоrightвключительно. - Добавь
totalв список ответов и верни его после последнего запроса.
def sumRange(nums, queries):
answers = []
for left, right in queries:
total = 0
for i in range(left, right + 1):
total += nums[i]
answers.append(total)
return answersПрефиксные суммы
Идея
Пусть prefix[i] — это сумма первых i значений, причём для пустого начала prefix[0] = 0. Для [3, -2, 5, 1, -4, 6] получаем prefix = [0, 3, 1, 6, 7, 3, 9]. Каждая запись — это предыдущая запись плюс одно значение, поэтому для всего массива требуется n сложений.
Диапазон [left, right] — это сумма всех значений до индекса right включительно минус сумма значений до индекса left. То есть prefix[right+1] - prefix[left]. Для [1, 4]: prefix[5] - prefix[1] = 3 - 3 = 0. Для [0, 2]: prefix[3] - prefix[0] = 6 - 0 = 6. Начальный 0 позволяет обрабатывать диапазон, начинающийся с индекса 0, без отдельного случая.
Построение массива требует O(n) времени, а каждый запрос — одного вычитания, поэтому общая сложность составляет O(n + q) по времени и O(n) по дополнительной памяти. Ни одна префиксная сумма здесь не превышает 10^4 × 10^4 = 10^8, поэтому достаточно 32-битных целых чисел.
Алгоритм
- Создай
prefixдлиныn+1сprefix[0] = 0. - Для каждого
iот0доn-1задайprefix[i+1] = prefix[i] + nums[i]. - Для каждого запроса
[left, right]добавьprefix[right+1] - prefix[left]к ответам. - Верни ответы.
def sumRange(nums, queries):
# prefix[i] is the sum of the first i values, so prefix[0] = 0.
prefix = [0] * (len(nums) + 1)
for i, value in enumerate(nums):
prefix[i + 1] = prefix[i] + value
# nums[left..right] is the first right+1 values minus the first left values.
return [prefix[right + 1] - prefix[left] for left, right in queries]
Ловушки и крайние случаи
Почти все ошибки здесь связаны с индексом, который смещён на единицу.
- Вычисление
prefix[right] - prefix[left]. Приprefix[0] = 0это не учитываетnums[right], поэтому сумма на отрезке[3, 3]получается равной0вместо значения по индексу 3. - Создание
prefixтой же длины, что иnums, так чтоprefix[i]включаетnums[i]. Тогда для отрезка, начинающегося с0, требуетсяprefix[left-1], что выходит за границы массива, а в Python незаметно обращается к последнему элементу. Дополнительный начальный0устраняет этот особый случай. - Завершение перебора в лоб при
i < right. В отрезок входят оба конца. - Забывание о том, что в Lua и R отсчёт начинается с 1. Запрос с индексацией от 0
[left, right]охватывает там элементы сnums[left+1]поnums[right+1], и разность префиксных сумм смещается так же. - Использование 32-битной переменной для суммы, когда значения или длина массива растут. Здесь наибольшая сумма равна
10^8, но при значениях около10^9префиксная сумма быстро переполняется, поэтому безопаснее всего использовать массив с 64-битными числами.
Частые вопросы4
Что такое массив префиксных сумм?
Это массив, в котором каждая запись — это сумма всех значений до определённой позиции: prefix[i] = nums[0] + ... + nums[i-1], где prefix[0] = 0. Ты строишь его за один проход, а после этого сумму любого диапазона [left, right] можно вычислить одним вычитанием: prefix[right+1] - prefix[left].
Какова временная сложность запросов суммы на диапазоне с использованием префиксных сумм?
O(n) на построение массива префиксных сумм один раз, затем O(1) на запрос, то есть O(n + q) для q запросов. Прямое суммирование каждого диапазона требует до O(n) на запрос, то есть в сумме O(n·q).
Почему в массиве префиксов на один элемент больше, чем в nums?
Дополнительное prefix[0] = 0 обозначает пустое начало массива. Благодаря ему для каждого диапазона используется одна и та же формула, включая диапазоны, начинающиеся с индекса 0: prefix[right+1] - prefix[0]. Без него для left = 0 нужна отдельная ветка.
Что, если массив может измениться между запросами?
Тогда массив префиксных сумм — неподходящий инструмент, потому что одно обновление сдвигает все последующие суммы и требует O(n) операций для пересчёта. Дерево Фенвика или дерево отрезков обрабатывает и обновление, и сумму на отрезке за O(log n). Если массив никогда не меняется, обычные префиксные суммы быстрее и компактнее.
Похожие задачи
Задачи на те же идеи. Решите две или три, и приём запомнится.
Python
def sumRange(nums, queries):
# Напишите код здесьСлучай 1
Случай 2
Ввод
nums = [3, -2, 5, 1, -4, 6] queries = [[0, 2], [1, 4], [3, 3]]
Ожидается
[6, 0, 1]