Algoritmi → Strukture podataka → Fenwick stablo (BIT)

Fenwick stablo (BIT)

Problem: zbirovi uz izmene

Dat je niz od n brojeva i q upita dve vrste: promeni element na poziciji i i koliki je zbir na intervalu [l, r]. Običan niz daje izmenu u O(1), a zbir u O(n). Prefiksni zbirovi daju zbir u O(1), ali izmenu u O(n). Za n, q do 2·10⁵ oba pristupa su prespora, a Fenwick stablo radi oba upita u O(log n).

Ideja: lowbit

Pozicije su od 1 do n. Element bit[i] čuva zbir dela niza koji se završava na i, a dužina tog dela je najniži bit broja i: lowbit(i) = i & (-i). Na primer, bit[12] čuva zbir pozicija 9–12 (12 = 1100₂, najniži bit je 4), a bit[7] samo poziciju 7.

• Zbir prvih i: saberi bit[i], pa pređi na i -= lowbit(i), dok i > 0.
• Dodaj x na poziciju i: dodaj x u bit[i], pa pređi na i += lowbit(i), dok i ≤ n.

U oba slučaja broj koraka je najviše broj bitova, tj. O(log n).

#include <iostream>
#include <vector>
using namespace std;

int n;
vector<long long> bit;

void dodaj(int i, long long x) {          // a[i] += x
    for (; i <= n; i += i & (-i)) bit[i] += x;
}

long long prefiks(int i) {                // a[1] + ... + a[i]
    long long s = 0;
    for (; i > 0; i -= i & (-i)) s += bit[i];
    return s;
}

int main() {
    int q;
    cin >> n >> q;
    bit.assign(n + 1, 0);
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) { cin >> a[i]; dodaj(i, a[i]); }
    while (q--) {
        int tip;
        cin >> tip;
        if (tip == 1) {                   // 1 i v : a[i] = v
            int i; long long v;
            cin >> i >> v;
            dodaj(i, v - a[i]);           // dodajemo razliku
            a[i] = v;
        } else {                          // 2 l r : zbir a[l..r]
            int l, r;
            cin >> l >> r;
            cout << prefiks(r) - prefiks(l - 1) << "\n";
        }
    }
    return 0;
}

Izmena „postavi na v“ se pretvara u „dodaj razliku v − a[i]“, pa zato čuvamo i sam niz a.

Kada Fenwick, a kada segmentno stablo?

Fenwick je kraći i brži, ali prirodno radi samo za operacije koje imaju „suprotnu“ (zbir – oduzimanje, XOR). Za minimum, maksimum ili složenije upite na intervalu koristi se segmentno stablo.

Zadaci za vežbu

Za svaki zadatak postoji primer, uputstvo i rešenje. Rešenja su provereno tačna na primerima iz teksta.

Proveri znanje