включает в себя два числа L и R (от 1
до N).Ответом на запрос является сумма чисел в массиве начиная с позиции номер L и заканчивая позицией номер R.
Вам необходимо ответить на все запросы.
Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Частичные суммы
Содержание
ЗадачаЗадан массив чисел A длинной N и M запросов.Каждый запрос включает в себя два числа L и R (от 1 до N).Ответом на запрос является сумма чисел в массиве начиная с
Слайды и текст этой презентации
Слайд 2Задача
Задан массив чисел A длинной N и M запросов.
Каждый запрос
Ответом на запрос является сумма чисел в массиве начиная с позиции номер L и заканчивая позицией номер R.
Вам необходимо ответить на все запросы.
Слайд 3Решение через префикс-суммы
Составим массив S размером N + 1:
Тогда ответом
на каждый запрос будет результат выражения: SR – SL-1
Слайд 4Решение через префикс-суммы
Для составления массива S посмотрим на схему:
Заметим, что
S0 = 0, а каждый следующий элемент Si = Si-1
+ Ai-1
