100din100

Smenul lui Mars (Difference Arrays) in C++

Publicat la 14 martie 2020 · algoritmi olimpiada clasa 9 cpp


Ce este Şmenul lui Mars?

Să zicem că avem un şir a[] cu n elemente. Unele probleme cer efectuarea unor operații de tipul sum(st, dr, val), cu semnificația că adunăm la toate elementele vectorului cu indicii între st şi dr valoarea val. Indexăm, pentru simplitate, vectorul de la 1. Desigur, algoritmul naiv de parcurgerea elementelor aflate între indici poate fi aplicată când dr - st este mic, şi când se fac doar puține operații de acest fel, dar cu ajutorul şmenului lui Mars eficența programului creşte observabil de mult.

Aproape în fiecare an, la clasa a 9-a, apar probleme cu şmenul lui Mars, atât la OJI, cât şi la ONI.

ATENȚIE! Formulele nu trebuie reținute, ci deduse.


Numele de "Şmenul lui Mars" este cunoscut în rândul olimpicilor datorită lui Marius Andrei, şi el un fost olimpic.


RECOMANDAREA AUTORULUI Pentru înțelegerea algoritmului, conspectați şi sumele parțiale.

Cuprinsul lecției

Aplicarea şmenului lui Mars

Observăm că nu este necesară afişarea schimbărilor făcute după fiecare operație. Aşadar, putem construi un alt vector, b[] cu n + 1 elemente, inițial nule. Rolul lui b este ca după ce aplicăm toate operațiile necesare, b[i] să reprezinte cât trebuie să adunăm la numărul inițial a[i].
Observație. Vectorul b[] este un vector de sumele parțiale.


Când efectuăm o operație sum(st, dr, val), vom face următoarele modifcări pe vectorul b[]:

b[st] += val;
b[dr + 1] -= val;

Iar după toate operațiile, parcurgem şirul de la 1 la n, astfel încat b[i] += b[i - 1] şi a[i] (după operații) = a[i] (înainte) + b[i].


Exemplu

Vectorul a[] are n = 6 elemente egale cu 1, şi aplicăm o singură operație sum(2, 5, 3).

i123456
a[i] (inițiale)111111
b[i] (după toate operațiile)03000-3
b[i] (final)033330
a[i] (final)144441 


int n, a[MAX + 1], b[MAX + 2], q, st, dr, val; //Declarăm variabilele; atenție la b!//pentru mai multe detalii: https://100din100.netlify.app

//Citim datele de intrare//pentru mai multe detalii: https://100din100.netlify.app
fin>>n;
for(int i = 1; i <= n; i++)
	fin>>a[i];
fin>>q; //Numărul de operații//pentru mai multe detalii: https://100din100.netlify.app
for(int i = 1; i <= q; i++) { //Citim & prelucrăm fiecare operație în parte//pentru mai multe detalii: https://100din100.netlify.app
	fin>>st>>dr>>val;
	b[st] += val;
	b[dr + 1] -= val;
}

//Prelucrăm în O(n) b[] şi a[]//pentru mai multe detalii: https://100din100.netlify.app
//Afişăm//pentru mai multe detalii: https://100din100.netlify.app
for(int i = 1; i <= n; i++) {
	b[i] += b[i - 1];
	a[i] += b[i];
	fout<<a[i]<<" ";
}

Şmenul lui Mars pe matrice

Extinderea în mai multe dimensiuni nu este chiar atât de dificilă; pentru adunarea valorii val în submatricea determinată de coordonatele stânga-sus (i‎1, j1) şi dreapta-jos (i2, j2), avem acelaşi raționament: când formăm matricea de sume parțiale (b, vezi mai sus), trebuie să ne asigurăm că valoaresa val se adună doar în submatrice. Iată formulele:


//Formare//pentru mai multe detalii: https://100din100.netlify.app
b[i‎1][j1] += val;
b[i2 + 1][j1] -= val;
b[i‎1][j2 + 1] -= val;
b[i2 + 1][j2 + 1] += val;

//Transformarea matricea b în matrice de sume parțiale//pentru mai multe detalii: https://100din100.netlify.app
for(int i = 1; i <= n; i++) {
	for(int j = 1; j <= m; j++) {
		//Vezi acest articol pentru clarificări!//pentru mai multe detalii: https://100din100.netlify.app
		b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
		a[i][j] += b[i][j];
	}
}

Bibliografie

Alte articole

Primul tau program, variabile si operatii - TUTORIAL COMPLET C++

Eşti elev de liceu şi nu înțelegi informatica? Acest clip ar trebui să te ajute să înțelegi cele mai elementare aspecte privind informatica de liceu - algoritmica...

Rezolvări probleme PbInfo

Problemele de informatică pot fi dificile uneori, şi este util să vedem o soluție bună pentru a ne autoverifica. De multe ori sunt necesare doar nişte modificări minore, de aceea este bine să analizăm soluțiile bune cu atenție!

Video - Probleme Rezolvate PbInfo

Aici gasiti rezolvarea mai multor probleme de pe site-ul pbinfo.ro, în format video, pe canalul nostru de YouTube.

Prelucrarea cifrelor unui numar pentru incepatori in C++

Acest articol urmăreşte aplicarea diferitelor aplicații cu cifrele unui număr: suma cifrelor, numărul de cifre, oglinditul unui număr ş.a.m.d. Puteți găsi multe probleme care cer prelucrarea cif…

Sortarea vectorilor si a structurilor (pentru incepatori) in C++

Sortarea în informatică reprezintă procesul de a ordona un şir de obiecte (numere, caractere, sau chiar şiruri) după un anumit criteriu. Spre exemplu, putem ordona crescător sau descrescăto…

Ridicarea la putere in timp logaritmic pentru olimpiada in C++

Un număr de forma b la puterea e nu poate fi calculat precum celelalte operații (adunarea, scăderea, înmulțirea, împărțirea) pur şi simplu. În articolul acesta vom prezenta un mod foarte …

Smenul lui Mars (Difference Arrays) in C++

Ce este Şmenul lui Mars? Să zicem că avem un şir a[] cu n elemente. Unele probleme cer efectuarea unor operații de tipul sum(st, dr, val), cu semnificația că adunăm la …

Afişare cu 2 zecimale exacte, fără şi cu rotunjire - TUTORIAL C++

Tutorialul acesta te învață cum să afişezi un număr real cu mai multe zecimale exacte. Multe probleme cer...

Algoritmi elementari - video

Tutoriale uşor de urmărit, sub forma unor videoclipuri!

Primul program - Operatori si expresii - Tutorial incepatori C++

Alcătuirea unui program pentru rezolvarea unei probleme se rezumă defapt la rezolvarea unor probleme mai mici. Spre exemplu, pentru a afla suma numerelor prime dintr-un şir, trebuie să ştim cum …

Cautarea binara pentru olimpiada in C++

Ce este căutarea binară? Să zicem că ai un vector a[] cu n elemente crescătoare. Căutarea binară este un algoritm eficient care determină dacă orice număr x apare sau n…

Tablelul ASCII - clasa a X-a - char C++

Ce este tabelul ASCII? Calculatorul reține numere (valori de 1 şi de 0), aşadar a fost nevoie de o corespondență între numere şi caractere pentru a putea reprezenta litere, si…

Verifica daca o data este valida in C++

Dându-se o dată (zi lună an), trebuie verificat dacă data este validă sau nu. Exemplu:Intrare zi = 3, luna = 4, an = 2021 Ieşire DA Pentru a verifica da…

Tipuri de date in C++ si C - Tutorial Incepatori

De ce avem nevoie de date? În timp ce lucrăm cu valori, avem nevoie (uneori chiar suntem siliți!) să memorăm datele undeva, în memorie. Prin intermediul variabilelor putem accesa o zonă de …

Parcurgerea matricei in spirala in C++

Cu ce ne ajută parcurgerea matricei pătratice în spirală? În concursuri şi olimpiade apar probleme legate de parcurgerea matricei în spirală. Deşi ideea de bază este destul de uşoară, algor…

Verifica daca un an este bisect in C++

Dându-se un an, trebuie verificat dacă este un an bisect sau nu. Exemplu:Intrare 2021 Ieşire NU Definiția anului bisect Deşi pare evident, anii bis…

Vectori caracteristici si vectori de frecventa - Materie Olimpiada Informatica C++

Ce este un vector de frecvență sau un vector caracteristic? Vectorii caracteristici rețin dacă un element se află într-un vector sau nu. Similar, vectorii de frecvență rețin numărul de apar…

Al doilea cel mai mic/mare element al unui sir in C++

Dându-se un şir de numere naturale distincte, aflați al doilea cel mai mic număr din şir. Exemplu:Intrare 9 5 8 2 4 Ieşire 4 Explicație4 este al doilea cel mai mi…

Creeaza un joc 2D in PYTHON pentru incepatori - Capitolul 0 (Instalare)

Care-i faza? În aceste câteva tutoriale vom învăța cum să îți creezi propriul joc video în Python. Puteți viziona atât pe YouTube, cât şi în format text pe site-ul nostru (aici adică). …

Ciurul lui eratostene - generarea numerelor prime - olimpiada C++

Să zicem că vrem să aflăm dacă mai multe numere sunt sau nu prime. Desigur, putem aplica algoritmul de aflare a numărului de divizori pentru toate numerele, doar că dacă avem foarte multe şi sun…

Divizorii unui numar - tutorial incepatori in C++

Prezentul articol te va ajuta să îndeplineşti diferite aplicații cu divizorii unui număr. Trebuie cunoscută parcurgerea divizorilor unui număr, înainte de toate, ca să ne asigurăm că ştim s…

Ce este coada/queue si cum functioneaza? Tutorial clasa a 10-a

Ce este coada? Coada (Queue din engleză) este o structură de date liniară care funcționează prin inserarea elementelor noi la spate şi prin eliminarea elementelor doar prin față. Altfel spu…

Sume partiale. Suma elementelor dintr-o submatrice in C++

Cu ce ne ajută sumele parțiale? Unele probleme cer aflarea sumei elementelor unei secvențe dintr-un şir dat. Metoda naivă, care face suma tuturor elementelor din secvența cerută, deobicei n…

Citirea si Afisarea in fisiere in C++ - Tutorial Incepatori

De ce citirea din fişier? De multe ori este necesară citirea şi afişarea în fişier, unul din motive fiind faptul că nu trebuie să reintroducem datele de intrare de fiecare dată când rulăm p…

Învață să programezi gratis!

Am lansat InfoAs, o platformă de informatică cu sute de probleme, lecții și concursuri, totul gratuit. Încearcă acum!