Untitled Diff
建立於 差異永不過期
// Fenwick tree class
// BIT class
class FenwickTree {
class BIT {
// Array to store the Fenwick tree
// Array to store the BIT
vector<int> tree;
vector<int> tree;
public:
public:
// Constructor to create an empty Fenwick tree with the given size
// Constructor to create an empty BIT with the given size
FenwickTree(int size) : tree(size + 1) { }
BIT(int size) : tree(size + 1) { }
// Add the given value at the given index in the Fenwick tree
// Add the given value at the given index in the BIT
void add(int index, int value) {
void add(int index, int value) {
while (index < tree.size()) {
while (index < tree.size()) {
tree[index] += value;
tree[index] += value;
index += index & -index;
index += index & -index;
}
}
}
}
// Query the Fenwick tree for the prefix sum at the given index
// Query the BIT for the prefix sum at the given index
int query(int index) {
int query(int index) {
int sum = 0;
int sum = 0;
while (index > 0) {
while (index > 0) {
sum += tree[index];
sum += tree[index];
index -= index & -index;
index -= index & -index;
}
}
return sum;
return sum;
}
}
};
};