De ce contează?
Pictezi pe o pânză cu o pensulă pătrată: de fiecare dată acoperi un dreptunghi întreg cu un strat de vopsea, iar dreptunghiurile se suprapun. La final vrei să știi cât de gros e stratul în fiecare punct. Ai putea trece pensula peste fiecare punct din fiecare dreptunghi — dar cu mii de tușe pe zone mari, îmbătrânești pictând. Trucul: nu vopsești interiorul, ci pui patru bilețele în colțuri care spun „de aici începe stratul, aici se termină”. La sfârșit, o singură trecere peste pânză reconstituie grosimea în fiecare punct.
Intuiția
La 1D, o adunare pe un interval cerea doar două marcaje: unde începe creșterea și unde se oprește. La 2D, un dreptunghi are două dimensiuni, deci „oprirea” trebuie făcută și pe coloane, și pe linii. Ca să nu vopsești decât exact dreptunghiul dorit, marchezi colțul de start, anulezi creșterea dincolo de marginea dreaptă, o anulezi și dincolo de marginea de jos, dar atunci colțul de jos-dreapta a fost scăzut de două ori, așa că îl readaugi. Sunt patru marcaje și restul se deduce printr-o sumă prefix 2D.
Cele patru colțuri sunt incluziune-excluziune curată. Pentru un dreptunghi
(r1,c1)-(r2,c2) cu valoarea val:
+valîn(r1,c1)— pornește creșterea din colțul de start;-valîn(r1,c2+1)— o oprește dincolo de coloana dreaptă;-valîn(r2+1,c1)— o oprește dincolo de linia de jos;+valîn(r2+1,c2+1)— readaugă colțul jos-dreapta, scăzut de ambele opriri.
Apoi o singură sumă prefix 2D (fiecare celulă adună vecinul de sus și pe cel din stânga și scade colțul comun) transformă marcajele înapoi în matricea reală.