Range Sum Query in a Fenwick Tree
One of the main advantages of Fenwick Trees is their ability to efficiently compute range sum queries. A range sum query involves finding the sum of values in a given range of positions in an input array.
To perform a range sum query using a Fenwick Tree, follow these steps:
Calculate the cumulative sum for the rightmost position in the range.
TEXT/X-C++SRC1// Compute the cumulative sum 2int sum = 0; 3int index = rightmost_position; 4while (index > 0) { 5 sum += fenwickTree[index]; 6 index = index - (index & -index); 7}Calculate the cumulative sum for the leftmost position in the range.
TEXT/X-C++SRC1// Compute the cumulative sum 2int index = leftmost_position - 1; 3while (index > 0) { 4 sum -= fenwickTree[index]; 5 index = index - (index & -index); 6}Return the difference between the two cumulative sums.
TEXT/X-C++SRC1// Compute the range sum 2int rangeSum = sum;
Here's a complete C++ code that demonstrates how to perform a range sum query using a Fenwick Tree:
TEXT/X-C++SRC
1#include <iostream>
2using namespace std;
3
4int getRangeSum(int fenwickTree[], int leftmost_position, int rightmost_position) {
5 // Compute the cumulative sum for the rightmost position
6 int sum = 0;
7 int index = rightmost_position;
8 while (index > 0) {
9 sum += fenwickTree[index];
10 index = index - (index & -index);
11 }
12
13 // Compute the cumulative sum for the leftmost position
14 index = leftmost_position - 1;
15 while (index > 0) {
16 sum -= fenwickTree[index];
17 index = index - (index & -index);
18 }
19
20 // Compute the range sum
21 int rangeSum = sum;
22
23 return rangeSum;
24}
25
26int main() {
27 int fenwickTree[] = {0, 1, 3, -2, 4, 6, 1, 2};
28 int leftmost_position = 2;
29 int rightmost_position = 5;
30
31 // Get the range sum
32 int rangeSum = getRangeSum(fenwickTree, leftmost_position, rightmost_position);
33
34 // Print the range sum
35 cout << "Range Sum: " << rangeSum << endl;
36
37 return 0;
38}