Гузариш ба мундариҷа
Мавзӯи 16 аз 18

Суммаҳои префиксӣ

Ин мавзӯъ — аввалин усули алгоритмии ҳақиқии барномасозии варзишӣ аст. Он содда аст, вале ҳалҳоеро, ки соатҳо кор мекарданд, ба ҳалҳои як ҳиссаи сония табдил медиҳад.

Масъала: бисёр суммаҳо дар порчаҳо

Рӯйхати ададҳо ва бисёр саволҳои навъи «суммаи элементҳо аз l то r ба чӣ баробар аст?» дода шудааст. Ҳар дафъа аз нав ҷамъ кардан мумкин аст:

answer = sum(a[l:r + 1])

Вале агар дар рӯйхат 105 адад ва саволҳо ҳам 105 бошанд, порчаҳо бошанд дароз, ин тақрибан 1010 ҷамъ аст — хеле бештар аз он ки ҳар компютер дар як сония ба анҷом расонад.

Суммаҳои префиксӣ

Пешакӣ массиви p-ро ҳисоб мекунем, ки дар он p[i] — суммаи i-тои аввали элементҳост:

a = [5, 2, 7, 1, 3]
p = [0] * (len(a) + 1)
for i in range(len(a)):
    p[i + 1] = p[i] + a[i]
print(p)    # [0, 5, 7, 14, 15, 18]
i 0 1 2 3 4 5
p[i] 0 5 7 14 15 18

p[0] = 0 — суммаи сифр элемент. Ин сифр дар аввал аз ҳолатҳои махсус халос мекунад.

Ҳар p[i + 1] аз пешина бо як ҷамъ ҳосил мешавад, бинобар ин тамоми массив дар як гузариш сохта мешавад.

Сумма дар порча дар як амал

Суммаи элементҳо аз индекси l то r (бо дохил, рақамгузорӣ аз сифр):

s = p[r + 1] - p[l]

Чаро: p[r + 1] — суммаи элементҳои a[0]…a[r], p[l] бошад — суммаи a[0]…a[l-1]. Бо тарҳ кардан аввали зиёдатиро мегирем.

# суммаи a[1] + a[2] + a[3] = 2 + 7 + 1
print(p[4] - p[1])   # 10

Агар дар масъала элементҳо аз як рақамгузорӣ шаванд, формула дигар хел менамояд — индексҳоро бодиққат ҷобаҷо кун. Хатои ба як дар ин ҷо — маъмултарин аст.

Вуруди зуд

Вақте дар вуруд 105 сатр ва бештар бошад, input()-и оддӣ ба таври намоён суст мешавад. Онро чунин тез кардан мумкин аст:

import sys
input = sys.stdin.readline

Пас аз ин input() ҳамон тавр, вале тезтар кор мекунад. Ба назар гир: чунин input() аломати сатри навро дар охир мегузорад — барои ададҳо ин муҳим нест (int онро нодида мегирад), сатрҳоро бошад бо .strip() бур.

Хуруҷро ҳам беҳтар аст ба рӯйхат ҷамъ карда, як бор чоп кард: print("\n".join(map(str, answers))).

Массиви фарқӣ

Масъалаи баръакс: бисёр бор «ба ҳамаи элементҳо аз l то r c-ро илова кардан», ва дар охир ҳамаи қиматҳоро донистан. Дар давра илова кардан боз дароз аст.

Ҳила: массиви d-ро аз сифрҳо месозем ва барои ҳар амал ду сабт мекунем — дар аввали порча ва фавран пас аз охири он:

n = 6
d = [0] * (n + 1)

# ба элементҳо аз индекси 1 то 3 4 илова кардан
d[1] += 4
d[4] -= 4

cur = 0
for i in range(n):
    cur += d[i]
    print(cur, end=" ")   # 0 4 4 4 0 0

Суммаи ҷамъшавандаи cur иловаро дар аввали порча «фаъол мекунад» ва фавран пас аз охир «хомӯш мекунад». Ҳар шумораи амалҳо бо як сабт барои ҳар амал ва як гузариш дар охир коркард мешавад.

Суммаҳои префиксӣ ва массиви фарқӣ баръакси якдигаранд: агар аз массиви фарқӣ суммаҳои префиксӣ созем, худи қиматҳо ҳосил мешаванд.

Ҳолати дученака

Суммаҳои префиксӣ барои ҷадвалҳо ҳам мешаванд: p[i][j] — суммаи росткунҷа аз кунҷи болоии чап то хонаи (i - 1, j - 1). Он гоҳ суммаи ҳар росткунҷаро бо чор муроҷиат ба p ёфтан мумкин аст. Ин дар масъалаҳои мураккабтар ба кор меояд.

Хулоса

  • p[i] — суммаи i элементи аввал, p[0] = 0, дар як гузариш сохта мешавад;
  • сумма дар порчаи [l, r] (аз сифр) — p[r + 1] - p[l];
  • массиви фарқӣ: d[l] += c, d[r + 1] -= c, баъд суммаро ҷамъ кун;
  • ҳангоми вуруди калон sys.stdin.readline-ро истифода бар.