Fenwick Trees
Fenwick trees, also known as Binary Indexed Trees (BIT), are a data structure that efficiently supports range sum queries and updates in an array of numbers.
Fenwick trees are particularly useful when dealing with problems that involve updating array elements frequently and performing range sum queries.
The main idea behind Fenwick trees is to use the binary representation of the array indexes to store partial sums. Each index of the Fenwick tree corresponds to a range of indexes in the original array.
Here's the basic interface of a Fenwick tree implemented in C++:
TEXT/X-C++SRC
1#include <iostream>
2#include <vector>
3using namespace std;
4
5class FenwickTree {
6private:
7 vector<int> tree;
8
9public:
10 FenwickTree(int n) {
11 tree.resize(n + 1, 0);
12 }
13
14 void update(int index, int value) {
15 while (index < tree.size()) {
16 tree[index] += value;
17 index += index & (-index);
18 }
19 }
20
21 int getPrefixSum(int index) {
22 int sum = 0;
23 while (index > 0) {
24 sum += tree[index];
25 index -= index & (-index);
26 }
27 return sum;
28 }
29
30 int getRangeSum(int start, int end) {
31 return getPrefixSum(end) - getPrefixSum(start - 1);
32 }
33};
34
35int main() {
36 vector<int> arr = {3, 2, -1, 6, 5, 4, -3, 3, 7, 2, 3};
37 int n = arr.size();
38
39 FenwickTree ft(n);
40
41 // Build Fenwick tree
42 for (int i = 0; i < n; i++) {
43 ft.update(i + 1, arr[i]);
44 }
45
46 // Get range sum from index 2 to index 8
47 int rangeSum = ft.getRangeSum(2, 8);
48 cout << "Range Sum: " << rangeSum << endl;
49
50 return 0;
51}The output of the above code would be:
SNIPPET
1Range Sum: 17xxxxxxxxxxusing namespace std;// Fenwick Tree implementationOUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment