Querying a Fenwick Tree
After building a Fenwick Tree, we can perform queries on it efficiently. The Fenwick Tree allows us to calculate the prefix sum of a range of elements in O(log n) time, where n is the number of elements in the original array.
To query the Fenwick Tree, we need to follow these steps:
- Initialize a variable
sumwith 0. - Traverse the tree in a bottom-up manner, starting from the given index.
- In each step, add the value at the current index to
sum. - Update the index to its parent index by removing the value of the rightmost set bit.
- Repeat steps 3 to 4 until the index becomes 0.
- Return the value of
sum, which represents the prefix sum of the range of elements.
Let's see an example of how to query a Fenwick Tree in C++:
TEXT/X-C++SRC
1#include <iostream>
2using namespace std;
3
4// Function to query the prefix sum of elements up to a given index
5int getPrefixSum(int bit[], int index) {
6 index++;
7 int sum = 0;
8
9 while (index > 0) {
10 // Adding value at current index to sum
11 sum += bit[index];
12
13 // Update index to its parent
14 index -= index & -index;
15 }
16
17 return sum;
18}
19
20// Usage
21int main() {
22 int arr[] = {1, 3, 2, -5, 4, 6};
23 int n = sizeof(arr) / sizeof(arr[0]);
24 int* bit = buildFenwickTree(arr, n);
25
26 // Query the prefix sum of the range [2, 4]
27 int prefixSum = getPrefixSum(bit, 4) - getPrefixSum(bit, 1);
28
29 cout << "Prefix Sum: " << prefixSum << endl;
30
31 return 0;
32}xxxxxxxxxx32
}using namespace std;// Function to query the prefix sum of elements up to a given indexint getPrefixSum(int bit[], int index) { index++; int sum = 0; while (index > 0) { // Adding value at current index to sum sum += bit[index]; // Update index to its parent index -= index & -index; } return sum;}// Usageint main() { int arr[] = {1, 3, 2, -5, 4, 6}; int n = sizeof(arr) / sizeof(arr[0]); int* bit = buildFenwickTree(arr, n); // Query the prefix sum of the range [2, 4] int prefixSum = getPrefixSum(bit, 4) - getPrefixSum(bit, 1); cout << "Prefix Sum: " << prefixSum << endl;OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment