https://www.youtube.com/watch?v=de28y8Dcvkg&list=PL6Wui14DvQPySdPv5NUqV3i8sDbHkCKC5&index=6

Префиксные суммы

задача - чему равна сумма элементов на полуинтервале [L, R)

решение - подсчитать массив префикс сум длиной n + 1, где префиксмус будет хранить сумму всех чисел из nums с индексами от 0 до k - 1

# строим массив префиксных сумм как префикс до этого + предыдущий элемент
prefixsum[i] =  prefixsum[i - 1] + nums[i - 1] # O(N)

# префиксов array должен быть длиньше чем сам массив 

Как найти сумму на отрезке [L, R) ? Мы просто берем разницу между prefixes[R] - prefixes[L]

Почему обычно отрезок это полуинтервал? Для того, чтобы избежать проблемы обращения по правому краю.

# RSQ через префиксные суммы 
def rsq(nums, l, r):
	prefixes = [0] * (len(nums) + 1) # нам нужен последний элемент 
	for i in range(1, len(nums) + 1):
			prefixes[i] = nums[i - 1] + prefixes[i - 1]
	return prefixes[r] - prefixes[l]

TASK 1.

Дана последовательность чисел длиной N и M запросов. Сколько нулей на полуинтвервале от [L, R)?

Идея - считать не суммы, а кол-о нулей в префиксе.

def count_zeros(nums, l, r):
	prefixes = [0] * (len(nums) + 1)
	for i in range(1, len(nums) + 1):
	
			prefixes[i] = prefixes[i - 1] + not nums[i - 1]
	return prefixes[r] - prefixes[l]

TASK 2.