A Fenwick-fa vagy Binary Indexed Tree (BIT) egy hatékony adatszerkezet, amely lehetővé teszi a prefix összeg (prefix sum) és az elemek frissítésének gyors kiszámítását. Gyakran használják olyan problémák megoldására, amelyek tömbön végzett módosításokkal és összegszámításokkal kapcsolatosak.
Egy adott (i)-edik pozícióig terjedő prefix összeg kiszámítása: Ehhez az (i)-edik indexről haladunk visszafelé, és mindig a legkisebb jelentős bitet vonjuk ki az indexből.
Egy (i)-edik indexű elem frissítése egy adott (val) értékkel: = + . ] Ehhez az (i)-edik indexről haladunk előre, és a legkisebb jelentős bitet hozzáadva folytatjuk a frissítést.
function query(BIT, i):
sum = 0
amíg i > 0:
sum = sum + BIT
i = i - (i & -i) # Lépés a következő szülőre
térj vissza sum
function update(BIT, n, i, val):
amíg i <= n:
BIT = BIT + val
i = i + (i & -i) # Ugrás a következő releváns indexre
class FenwickTree:
def __init__(self, size):
self.size = size
self.tree = * (size + 1)
def update(self, index, value):
while index <= self.size:
self.tree += value
index += index & -index # Lépés a következő indexre
def query(self, index):
sum_ = 0
while index > 0:
sum_ += self.tree
index -= index & -index # Lépés a szülő indexre
return sum_
def range_query(self, left, right):
return self.query(right) - self.query(left - 1)
# Példa használat
n = 10
fenwick = FenwickTree(n)
# Frissítések
fenwick.update(1, 5)
fenwick.update(4, 7)
fenwick.update(7, 3)
# Prefix összeg
print(f"1-7 prefix összeg: {fenwick.query(7)}") # 15
print(f"4-7 tartomány összeg: {fenwick.range_query(4, 7)}") # 10
Kimenet:
1-7 prefix összeg: 15 4-7 tartomány összeg: 10
#include <iostream>
#include <vector>
using namespace std;
class FenwickTree {
private:
vector<int> tree;
int size;
public:
FenwickTree(int n) {
size = n;
tree.resize(n + 1, 0);
}
void update(int index, int value) {
while (index <= size) {
tree += value;
index += index & -index; // Lépés a következő indexre
}
}
int query(int index) {
int sum = 0;
while (index > 0) {
sum += tree;
index -= index & -index; // Lépés a szülő indexre
}
return sum;
}
int range_query(int left, int right) {
return query(right) - query(left - 1);
}
};
int main() {
int n = 10;
FenwickTree fenwick(n);
// Frissítések
fenwick.update(1, 5);
fenwick.update(4, 7);
fenwick.update(7, 3);
// Prefix összeg
cout << "1-7 prefix összeg: " << fenwick.query(7) << endl; // 15
cout << "4-7 tartomány összeg: " << fenwick.range_query(4, 7) << endl; // 10
return 0;
}
Kimenet:
1-7 prefix összeg: 15 4-7 tartomány összeg: 10
A Fenwick-fa egy erőteljes eszköz a dinamikus lekérdezési problémák gyors megoldására, különösen nagy adathalmazokon.