Now that we have learned how to calculate prefix sums using a Fenwick Tree, let's explore how we can perform range queries using this data structure.
A range query involves finding the sum of all the elements within a given range of indices in the original array. This can be achieved efficiently using the Fenwick Tree.
To perform a range query, we need to calculate the prefix sum for both the starting index and the ending index of the range. Then, we can subtract the prefix sum of the starting index from the prefix sum of the ending index (inclusive) to get the sum of the elements within the range.
TEXT/X-C++SRC
1int rangeQuery(int BIT[], int start, int end) {
2 int sumStart = prefixSumQuery(BIT, start - 1);
3 int sumEnd = prefixSumQuery(BIT, end);
4 return sumEnd - sumStart;
5}Let's take a look at an example to see how this works.
TEXT/X-C++SRC
1#include <iostream>
2using namespace std;
3
4const int n = 10;
5int arr[n + 1] = {0};
6int BIT[n + 1] = {0};
7
8// Compute the prefix sum up to index i
9int prefixSumQuery(int BIT[], int i) {
10 int sum = 0;
11 while (i > 0) {
12 sum += BIT[i];
13 i -= i & (-i);
14 }
15 return sum;
16}
17
18// Perform a range query
19int rangeQuery(int BIT[], int start, int end) {
20 int sumStart = prefixSumQuery(BIT, start - 1);
21 int sumEnd = prefixSumQuery(BIT, end);
22 return sumEnd - sumStart;
23}
24
25int main() {
26 // Update values in the Fenwick Tree
27 // ... (code for updating values)
28
29 // Perform a range query
30 int start = 3;
31 int end = 7;
32 int rangeSum = rangeQuery(BIT, start, end);
33
34 cout << "Sum of elements in range [" << start << ", " << end << "]: " << rangeSum << endl;
35
36 return 0;
37}xxxxxxxxxx37
}using namespace std;const int n = 10;int arr[n + 1] = {0};int BIT[n + 1] = {0};// Compute the prefix sum up to index iint prefixSumQuery(int BIT[], int i) { int sum = 0; while (i > 0) { sum += BIT[i]; i -= i & (-i); } return sum;}// Perform a range queryint rangeQuery(int BIT[], int start, int end) { int sumStart = prefixSumQuery(BIT, start - 1); int sumEnd = prefixSumQuery(BIT, end); return sumEnd - sumStart;}int main() { // Update values in the Fenwick Tree // ... (code for updating values) // Perform a range queryOUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment