Range Sum Query

Q: Что такое массив префиксных сумм?

Массив, в котором каждый элемент равен сумме всех значений перед данной позицией: prefix[i] = nums[0] + ... + nums[i-1] , где prefix[0] = 0 . Ты строишь его за один проход, а затем сумма любого диапазона [left, right] равна prefix[right+1] - prefix[left] .

Q: Какова временная сложность запросов суммы диапазона с использованием префиксных сумм?

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

Q: Что, если массив может измениться между запросами?

Тогда массив префиксных сумм — неподходящий инструмент, потому что одно обновление сдвигает все последующие суммы и требует O(n) для пересчёта. Дерево Фенвика или дерево отрезков обрабатывает и обновление, и сумму на отрезке за O(log n) .

ЛегкоПрефиксные суммы

+10

Вам дан массив целых чисел nums, который никогда не меняется, и список queries. Каждый запрос — это пара [left, right] индексов с отсчётом от 0, и он запрашивает сумму nums[left] + nums[left+1] + ... + nums[right], включая оба конца. Верните ответы в том же порядке, что и запросы.

Функция

sumRange(nums: integer-array, queries: integer-2d-array) → integer-array

numsinteger-array: массив целых чисел, одинаковый для каждого запроса
queriesinteger-2d-array: диапазоны для суммирования, каждый — пара [left, right], где left ≤ right
Возвращаетinteger-array: сумма каждого диапазона, по одной на запрос, в порядке запросов

Ограничения

1 ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
1 ≤ queries.length ≤ 1500
0 ≤ 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]
Пояснение: Сумма всего массива равна 18, двух последних значений — 1 + 8 = 9, только индекса 0 — 2, а индексов с 1 по 2 — 7 + 1 = 8.

Дополнительный вопрос

Если числа образуют сетку и в каждом запросе нужно найти сумму чисел в прямоугольнике, как расширить префиксные суммы, чтобы отвечать на каждый запрос за постоянное время?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Один диапазон — это цикл, но каждый запрос может охватывать большую часть массива, поэтому отдельное суммирование каждого диапазона повторяет одни и те же сложения. Один раз просуммируй весь массив в префиксные суммы, и для каждого диапазона останется выполнить одно вычитание.

Сложите каждое значение диапазона

Верно, но не успевает на самых больших тестах

Идея

Для каждого запроса складывайте nums[left] и все значения до nums[right] включительно в общую сумму. Это правильный подход, потому что он считывает каждое значение в диапазоне, а для одного запроса лучше сделать нельзя. Запрос может охватывать до n значений, поэтому обработка q запросов требует до n × q сложений: 1.5 × 10^7 при n = 10^4 и q = 1500, причём почти все они повторяются.

Алгоритм

Создай пустой список ответов.
Для каждого запроса [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] получаем [0, 3, 1, 6, 7, 3, 9].

Диапазон [left, right] — это сумма всех значений до индекса right включительно минус сумма всех значений до индекса left: prefix[right+1] - prefix[left]. Для [1, 4] это prefix[5] - prefix[1] = 3 - 3 = 0. Начальный 0 позволяет использовать ту же формулу для диапазона, начинающегося с индекса 0. За один проход из n сложений строится массив, а каждый запрос требует всего одного вычитания.

Алгоритм

Создайте 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 вместо 1.
Создание массива prefix той же длины, что и nums, так что prefix[i] включает nums[i]. Тогда для диапазона, начинающегося с 0, понадобится prefix[-1], что выходит за границы массива, а Python молча читает последний элемент.
Остановка цикла полного перебора при i < right. Включены оба конца диапазона, поэтому сумма для [3, 3] будет равна нулю.
В Lua и R, где отсчёт начинается с 1, запрос с индексами от 0 [left, right] охватывает элементы от nums[left+1] до nums[right+1], и индексы префиксной суммы сдвигаются таким же образом.

Частые вопросы3

Что такое массив префиксных сумм?

Массив, в котором каждый элемент равен сумме всех значений перед данной позицией: 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) всего.

Что, если массив может измениться между запросами?

Тогда массив префиксных сумм — неподходящий инструмент, потому что одно обновление сдвигает все последующие суммы и требует O(n) для пересчёта. Дерево Фенвика или дерево отрезков обрабатывает и обновление, и сумму на отрезке за O(log n).

def sumRange(nums, queries):
    # Напишите код здесь

Тест #1

Тест #2

Аргументы

nums = [3, -2, 5, 1, -4, 6]
queries = [[0, 2], [1, 4], [3, 3]]

Ожидаемый вывод

[6, 0, 1]