Articolele lui Balinga Mihai (Mihai_Balinga)

Se considera urmatoarea cerinta: avem un tablou unidimensional cu n elemente, asupra acestuia se fac doua tipuri de operatii:
1.Update(x, y), elementul de la pozitia x primeste valoarea y.
2.Suma[ST, DR], adica suma elementelor din a cu indicele i, ST≤i≤DR
Prima metoda, elementara, poate solutiona fiecare query de tip suma in O(n) timp si update in O(1) timp, parcurgand efectiv elementele din intervalul dat de query-ul SUMA.
O a doua metoda se bazeaza pe algoritmul de Square Root Decomposition (cunoscut si ca Smenul lui Batog, atat Infoarena, cat si GeeksForGeeks au articole ce explica rationamentul si implementarea). Astfel, complexitatea de timp scade la O(sqrt(n)).
Cea mai eficienta metoda este metoda prin care construim o structura de date arborescenta ce ne garanteaza ca orice operatie de tip update sau suma poate fi executata in O(log n). Modul in care construim acest arbore este urmatorul: la radacina avem intervalul [1, n], descendentii acestuia vor fi [1,n/2] si [n/2+1, n]. Vom mentine aceasta maniera recursiva pana cand ajungem la elemente individuale ale array-ului. Dupa construirea arborelui, trecem la operatia de update. Ideea este ca nu dorim sa actualizam toate nodurile, ci doar parintii nodurilor pana cand ajungem la radacina, astfel operatia va fi logaritmica. Pentru suma ideea este similara: noi impartim recursiv intervalul de cautare in jumatati pana cand gasim un nod ce contine intervalul cautat.
In concluzie, arborii de intervale sunt structuri de date arborescente ce permit rezolvarea eficienta a problemelor unde exista update-uri si query-uri pe intervale. Acestia pot fi implementati intr-o multitudine de probleme din concursuri.
Mai jos va las si implementarea mea a arborilor de intervale:

#include <bits/stdc++.h>
using namespace std;
int v[100], a[401];
void build (int st, int dr, int node) {
    if (st == dr) {
        a[node] = v[st];
    }
    else {
        int mij = (st + dr) / 2;
        build (st, mij, node * 2);
        build (mij + 1, dr, node * 2 + 1);
        a[node] = a[ node * 2 ] + a[ node * 2 + 1 ];
    }
}
void update (int st, int dr, int node, int pos, int val) {
    if (st == dr) {
        a[node] = val;
        v[pos] = val;
    }
    else {
        int mij = (st + dr) / 2;
        if (pos <= mij) {
            update (st, mij, node * 2, pos, val);
        }
        else {
            update (mij + 1, dr, node * 2 + 1, pos, val);
        }
        a[node] = a[node * 2 + 1] + a[node * 2];
    }
}
int sum (int st, int dr, int node, int target_st, int target_dr) {
    if (st>target_dr or dr<target_st) {
        return 0;
    }
    else {
        if (target_st <= st and dr <= target_dr) {
            return a[node];
        }
        int mij = (st + dr) / 2;
        return sum (st, mij, node * 2, target_st, target_dr) + sum (mij + 1, dr, node * 2 + 1, target_st, target_dr);
    }
}

Sper ca v-am ajutat!

Atunci cand avem un vector doar cu elemente pozitive (spre exemplu V⁴={1,3,11,4}) problema determinarii subarray-ul cu suma maxima este elementara, subarray-ul cautat fiind array-ul in sine. Problema devine mult mai interesanta atunci cand se adauga si numere negative. In mod intuitiv se foloseste o structura de tip “for in for” care calculeaza suma tuturor subarray-urilor si determina maximul.
Mai jos se poate vedea algoritmul naiv, ce foloseste aceasta abordare. Complexitatea este una patratica O(n²), lucru ce nu este ideal pentru anumite probleme de concurs unde se dau vectori cu un numar mare de elemente.
#include <iostream> #include <climits> using namespace std; int main() { int n,v[100],s,maxim; cin>>n; for(int i=0;i<n;i++) { cin>>v[i]; } maxim=v[0]; for(int i=0;i<n;i++) { s=0; for(int j=i;j<n;j++) { s=s+v[j]; } maxim=max(maxim,s); } cout<<maxim; return 0; }
Se propune o alta solutie mai eficienta: insumam elementele vectorului pana cand suma este mai mica ca elementul individual din vector. In acel moment suma incepe de la elementul gasit. De fiecare data se verifica daca suma curenta este mai mare ca maximul global. Aceasta maniera de rezolvare va avea timp de compilare O(n) ideal pentru concursuri.
#include <iostream> using namespace std; int main() { int n,v[100],maxim,curent; cin>>n; for(int i=0;i<n;i++) { cin>>v[i]; } maxim=v[0]; curent=v[0]; for(int i=1;i<n;i++) { curent=max(v[i],curent+v[i]); maxim=max(maxim,curent); } cout<<maxim; return 0; }
Folosindu-ne de acest algoritm putem determina si submatricea cu suma maxima, coreland sumele partiale pe linii sau coloane cu aceasta abordare. Complexitatea este O(n²•m). Mai jos este si codul:
#include <iostream> using namespace std; int main() { int n, m; int a[100][100]; cin >> n >> m; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { cin >> a[i][j]; } } int maxim = -1000000; for(int sus = 0; sus < n; sus++) { int v[100] = {0}; for(int jos = sus; jos < n; jos++) { for(int col = 0; col < m; col++) v[col] = v[col] + a[jos][col]; int curent = v[0]; int max_local = v[0]; for(int i = 1; i < m; i++) { curent = max(v[i], curent + v[i]); max_local = max(max_local, curent); } if(max_local > maxim) maxim = max_local; } } cout << maxim; return 0; }
Sper ca v-am ajutat!