Dołącz do konkursu i wysyłaj zadania: https://szkopul.edu.pl/c/oki-olimpiada-od-podstaw
Sumy prefiksowe służą do szybkiego liczenia sumy dowolnego przedziału tablicy.
Aby policzyć sumę na przedziale [l,r], możemy policzyć sumę na przedziale [1,r] i odjąć od niej sumę na przedziale [1,l-1]. Wszystkie sumy postaci [1,i] możemy policzyć na początku programu, przez co zapytanie będzie działać w czasie O(1).
Tekstowe streszczenie sum prefiksowych
Sumy prefiksowe - Algorytmy dla początkujących #1
Introduction to Prefix Sums na usaco.guide
Sumy prefiksowe - Algorytmy dla początkujących #1
Introduction to Prefix Sums na usaco.guide
Zadania na rozgrzewkę. Pozwolą zapoznać Ci się konceptem i przygotują cię do kolejnych zadań.
Wyślij w konkursie
Omówienie
Zadania wymagające, czasami wręcz ostentacyjnie nietrywialnej, ilości pomyślunku, której skala pozostaje niewspółmierna do liczby linijek kodu prowadzących do rozwiązania.
Zadania na rozgrzewkę. Pozwolą zapoznać Ci się konceptem i przygotują cię do kolejnych zadań.