Constructing a Fenwick Tree
To construct a Fenwick Tree from an input array, follow these steps:
Initialize the Fenwick Tree with 0 for all elements.
TEXT/X-C++SRC1// Initialize Fenwick Tree with 0 2for (int i = 1; i <= n; i++) { 3 fenwickTree[i] = 0; 4}Construct the Fenwick Tree by iterating through the input array.
TEXT/X-C++SRC1// Construct the Fenwick Tree 2for (int i = 1; i <= n; i++) { 3 int index = i; 4 5 // Update all ancestors of index 6 while (index <= n) { 7 fenwickTree[index] += input[i]; 8 index = index + (index & -index); 9 } 10}
Here's a complete C++ code that demonstrates how to construct a Fenwick Tree from an input array:
TEXT/X-C++SRC
1#include <iostream>
2using namespace std;
3
4void constructFenwickTree(int input[], int fenwickTree[], int n) {
5 // Initialize Fenwick Tree with 0
6 // Construct the Fenwick Tree
7}
8
9int main() {
10 int input[] = {1, 2, 3, 4, 5};
11 int n = sizeof(input) / sizeof(input[0]);
12
13 // Create Fenwick Tree
14 int fenwickTree[n + 1];
15 constructFenwickTree(input, fenwickTree, n);
16
17 // Print Fenwick Tree
18 for (int i = 1; i <= n; i++) {
19 cout << fenwickTree[i] << " ";
20 }
21
22 return 0;
23}xxxxxxxxxx38
}using namespace std;// Construct a Fenwick Tree from an input arrayvoid constructFenwickTree(int input[], int fenwickTree[], int n) { // Initialize Fenwick Tree with 0 for (int i = 1; i <= n; i++) { fenwickTree[i] = 0; } // Construct the Fenwick Tree for (int i = 1; i <= n; i++) { int index = i; // Update all ancestors of index while (index <= n) { fenwickTree[index] += input[i]; index = index + (index & -index); } }}int main() { int input[] = {1, 2, 3, 4, 5}; int n = sizeof(input) / sizeof(input[0]); // Create Fenwick Tree int fenwickTree[n + 1]; constructFenwickTree(input, fenwickTree, n);OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment