De ce contează?
Ai un șir de becuri numerotate și un teanc de comenzi de tipul „dă mai tare luminozitatea cu 3 la becurile de la 1 la 3”. Ai putea parcurge fiecare bec din interval și să-i adaugi 3 — dar dacă ai mii de comenzi pe intervale lungi, îmbătrânești la întrerupător. Trucul: nu atingi niciun bec acum. Pui un bilețel „de aici începe +3” la capătul stâng și un bilețel „aici se oprește” imediat după capătul drept — atât, două bilețele, oricât de lung ar fi intervalul. La final treci o singură dată prin șir, aduni bilețelele din mers și abia atunci afli luminozitatea fiecărui bec.
Intuiția
Imaginează-ți că în loc să reții valoarea fiecărei poziții, reții doar cât se schimbă valoarea de la o poziție la următoarea. Atunci o adunare pe un interval întreg înseamnă doar două schimbări de pantă: una unde începe creșterea și una unde se oprește. Restul intervalului „moștenește” creșterea automat, când refaci valorile prin adunare cumulativă. Practic, marchezi doar granițele schimbării.
Ideea în două propoziții: marchezi doar granițele unei actualizări pe un interval
de la l la r — pui +val la poziția l și -val imediat după r (la poziția r+1).
La final, o singură sumă prefix peste vectorul de diferențe reconstruiește
vectorul real: fiecare poziție devine suma tuturor marcajelor de până la ea.